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

 

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

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

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

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

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

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

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

Перестановки в первом просмотре

13 19

5 19

1 31

26 31

7 31

После первого просмотра

13 5 19 1 26 7 31

5 13

Перестановки во втором просмотре

1 19

После второго просмотра

7 26

5 13 1 19 7 2631

Перестановки в третьем просмотре После третьего просмотра

1 13

7 19

5 1 13 7 192631

Перестановки в четвертом просмотре После четвертого просмотра

1 5

7 13

1 5 7 13192631

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

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

 

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