Задача сортировки
Сортировка – это расположение чисел в порядке возрастания или убывания. Наиболее распространенный и простой метод сортировки – метод " пузырька". Он требует минимального объема памяти для данных, но затраты времени на реализацию этого метода велики. Суть метода " пузырька" в следующем. Пусть дано 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
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. Иллюстрация метода сортировки " пузырьком"
|
5 13
