Блог о программировании

Алгоритм сортировки пузырьком

Категория: Алгоритмы
 10 декабря 2016 г. 23:29

Данный алгоритм является простейшим для сортировки как в плане понимания, так и в плане реализации. Алгоритм считается учебным, поскольку практически не применяется на практике ввиду существования более эффективных алгоритмов.

Пузырьковая сортировка предполагает следующее: если массив не отсортирован, то любые ва смежных элемента могут находиться в неправильном положении, соответственно, чтобы это исправить, алгоритм перебирает все смежные пары массива от начала и до его конца, по пути меняя неправильно расположенные элементы. Итерация прохождения массива от начала и до конца происходит до тех пор, пока массив не будет отсортирован.


Псевдокод

На псевдокоде сортировка выглядит так:

bubblesort:(values[])
    //Флаг отсортированности массива
    Boolean: not_sorted = true;
   
    //Повторояем до тех пор, пока массив не отсортирован
    while(not_sorted)
        //Предполагаем, что нет неправильных пар
        not_sorted = false;
       
        // Определяем количество элементов в массиве
        Integer count = count(values);
       
        // Пробегаемся по всем элементам массива
        For i = 1 To count - 1
       
            // Проверяем, стоят ли смежные элементы в правильном положении
            If (values[i] < values[i - 1]) Then
                //Меняем их местами
                Integer: temp = values[i];
                values[i] = values[i - 1];
                values[i - 1] = temp;
               
                // Указываем, что массив все еще не отсортирован
                not_sorted = true;
            End If
        Next i
    End while
End bubblesort

Для детального понимания работы алгоритма предлагается анимация:

Скорость: 1

Способы улучшения алгоритма

Способ 1

Стоит заметить, что сейчас алгоритм пробегает массив от начала и до конца. В таком случае, если наименьший элемент расположен в конце массива, то элемент очень долго будет перебираться в начало. Отсюда возникает очевидное решение улучшения алгоритма: чередовать проходы алгоритма, один от начала до конца, а второй от конца и до начала. Таким образом при первом варианте прохода наибольшие элементы массива будут быстрее занимать свою позицию, а при втором варианте - наименьшие.

Способ 2

Еще один способ ускорить работу алгоритма - выполнять несколько перестановок за проход. Например, при движении вниз по массиву элемент(пусть будет E) может сменить свою позицию нескольк раз прежде чем займет свое место. Проще не передвигать его по массиву, а сохранить в памяти, сместить другие элементы вверх, найти целевую позицию для E, вставить его туда и продолжить прохождение.


Эффективность алгоритма

Даже с учетом описанных модификаций данный алгоритм является очень медленным в работе. Единственный случай, когда его можно использовать - для сортировки небольших массивов(5-20 элементов). В реальной же жизни проще пользоваться уже готовыми алгоритмами сортировки, поставляемыми с ядром языка программирования, на котором вы пишите код.

Поделиться статьей

Оставить комментарий