Сортировка массива пузырьком. Метод пузырька. Pascal, Delphi.

Допустим, у нас есть массив a размером в 1000 элементов. И мы хотим его отсортировать. Для массива такой размерности подходит метод пузырька.

В чем заключается этот метод? Программа пропихивает самый большой элемент в конец(сравнивая соседние элементы и меняя их местами) и больше не возвращается к нему. И так на каждом шаге.

Например: у нас есть массив 3, 4, 5, 2, 1.

1 шаг: массив станет 3, 4, 2, 1, 5.
2 шаг: 3, 2, 1, 4, 5.
3 шаг: 2, 1, 3, 4, 5.
4 шаг: 1, 2, 3, 4, 5.

Вот наш массив отсортирован.

Код:


For i := n - 1 downto 1 do
    For j := 1 to i do
    begin
      if a[j] > a[j + 1] then swap(a[j], a[j + 1]);
    end;


Процедура swap меняет элементы местами, ее нужно писать отдельно.

Удачи!

А зачем применяется downto?
раньше никогда с ним не встречалась

Downto - это то же самое, что и to, только задом наперед.
То есть 100 downto 1 пройдется циклом со 100 до 1.

спасибо, теперь понятно

Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab")достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место.
Единственное, только по-моему этот способ уже называется челночным, но это так для общего сведения

В любом случае, QSort намного быстрее любой из этих квадратичных сортировок

Aster пишет:В любом случае, QSort намного быстрее любой из этих квадратичных сортировок

а вот с этим не поспоришь

Да действительно, запомнить QSort не так уж и сложно и удобно... а если просто нужно побыстрому написать сортировочку, то можно использовать и линейную.