Задача сортировки

Сортировка – это расположение чисел в порядке возрастания или убывания.

Наиболее распространенный и простой метод сортировки – метод "пузырька". Он требует минимального объема памяти для данных, но затраты времени на реализацию этого метода велики. Суть метода "пузырька" в следующем.

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

1) числа сравниваются попарно: первое со вторым; второе с третьим; i-тое – с (i+1) - тым;

2) если меньшее стоит в паре на втором месте (числа в паре не упорядочены по возрастанию), то сравниваемые числа меняются местами.

За один такой просмотр массива минимальное число "вытолкнется", по крайней мере, на одно место вверх (вперед), а максимальное – переместится в самый конец (вниз), т.е. минимальное число как легкий пузырек воздуха в жидкости постепенно "всплывает" в начало последовательности. Отсюда – название метода. За n-1 просмотр произойдет полное упорядочение массива при любом исходном расположении чисел в нем. Рассмотрим работу метода на примере, приведенном на рис. 2.8.

19 13 5 31 1 26 7Исходный массив

5 19

1 31

26 31

7 31

5 13

5 13 1 19 7 2631

7 19

5 1 13 7 192631

7 13

1 5 7 13192631

В пятом просмотре перестановок нет. Сортировка окончена.

1 5 7 13 19 26 31 Отсортированный массив

Рис. 2.8. Иллюстрация метода сортировки "пузырьком"