Простейшие алгоритмы сортировки, закрепление навыков работы с массивами, освоение простейших алгоритмов сортировки
Теоретические сведения
Сортировка выбором
Алгоритм упорядочивания по возрастанию:
1. Найти минимальное значение в текущем списке.
2. Найденное минимальное значение меняется местом с элементом на первой позиции.
3. Повторяем сортировку, исключив из рассмотрения уже отсортированный первый элемент, то есть, начиная со второй позиции.
Последовательность шагов при n=7 показана на рисунке.
Алгоритм не использует дополнительной памяти: все операции происходят «на месте».
Метод простого обмена (метод пузырька).
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Алгоритм сортировки методом пузырька
1. Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.
2. Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами.
3. …
4. Сравниваем предпоследний (N-1) и последний (N) элементы массива. Если предпоследний элемент больше, чем последний, то меняем их местами.
В результате самым последним элементом в массиве у нас окажется самый большой элемент.
Второй шаг сортировки методом пузырька — повторяем вышеуказанные действия для части массива, начиная с 1 позиции до N-1:
1. Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.
2. Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами.
3. …
4. Сравниваем элемент N-2 и элемент N-1 массива. Если (N-2)-й элемент больше, чем элемент N-1, то меняем их местами.
В результате предпоследний элемент в массиве у нас тоже будет на своем, «отсортированном» месте.
На последующих шагах сортировки методом пузырька вышеуказанные действия повторяются для части массива, начиная с 1 позиции до N-2 (шаг 3), а потом для диапазона 1..N-3 и так далее до диапазона 1..2.
После завершения последнего шага массив будет отсортирован по возрастанию.
Среднее число сравнений и обменов имеют квадратичный порядок роста, отсюда можно заключить, что алгоритм пузырька достаточно медленен, однако он прост и его можно улучшить простыми средствами.
Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. Одно из возможных улучшений алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет — алгоритм заканчивает работу.
Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседних элементов с индексами, большими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.