8.6. Сортировка массива

Пример 11. Есть массив: 5 4 3 2 1. На примере этого массива подсчитаем количество элементарных действий в вычислительном процессе алгоритма сортировки методом «пузырька»:

1-я итерация: 4 3 2 1 5 (4 сравнения, 4 обмена);
2-я итерация: 3 2 1 4 5 (3 сравнения, 3 обмена);
3-я итерация: 2 1 3 4 5 (2 сравнения, 2 обмена);
4-я итерация: 1 2 3 4 5 (1 сравнение, 1 обмен).

Алгоритм закончил работу. Было сделано 10 сравнений и 10 обменов (4 + 3 + 2 + 1).

Этот алгоритм легко запоминается, но на практике он используется достаточно редко из-за квадратичной сложности, означающей, что в общем случае количество выполненных сравнений и обменов сопоставимо с n², где n — количество элементов массива.

Попытайтесь самостоятельно запрограммировать алгоритм сортировки методом «пузырька».

Сортировка выбором

Сортировка выбором (в порядке неубывания) осуществляется следующим образом:

1) в массиве выбирается минимальный элемент;

2) минимальный и первый элементы меняются местами (первый элемент считается отсортированным);

3) в неотсортированной части массива снова выбирается минимальный элемент и меняется местами с первым неотсортированным элементом массива;

4) действия, описанные в пункте 3, повторяются с неотсортированными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет максимальным).

Пример 12. Есть массив: 5 4 3 2 1.

1- я итерация: 1 4 3 2 5 (4 сравнения, 1 обмен).

2- я итерация: 1 2 3 4 5 (3 сравнения, 1 обмен).

3- я итерация: 1 2 3 4 5 (2 сравнения, 0 обменов).

4- я итерация: 1 2 3 4 5 (1 сравнение, 0 обменов).

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

Приведём фрагмент программы, реализующей описанный выше алгоритм:

Запишите полный текст программы и выполните её на компьютере для рассмотренного выше массива.

<<< К началу