На первом этапе сравниваются два начальных элемента

На первом этапе сравниваются два начальных элемента. Поскольку второй элемент меньше первого, он перемещается на место первого элемента, который сдвигается вправо на одну позицию. Остальная часть последовательности остаётся без изменения. На втором этапе из неупорядоченной последовательности выбирается элемент и сравнивается с двумя упорядоченными ранее элементами. Так как он больше предыдущих, то остаётся на месте. Затем анализируются четвёртый, пятый и последующие элементы – до тех пор, пока весь список не будет упорядоченным, что имеет место на последнем (седьмом) этапе.

Разновидностью сортировки вставкой является метод фон Неймана. Пусть заданы два упорядоченных по возрастанию элементов одномерных массива:   а  размерности n  и  b размерности m. Требуется получить третий массив с размерности n+m, который содержал бы все элементы исходных массивов, упорядоченных по возрастанию.

Алгоритм решения этой задачи ,известный как «сортировка фон Неймана» или сортировка слиянием,  состоит в следующем: сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив. Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый массив. Полученный новый массив упорядочен таким же образом, как исходные.

Сложность метода сортировки вставкой порядка O(n²).

Сортировка обменом

 

Сортировка обменом – метод, в котором элементы списка последовательно сравниваются между собой и меняются местами в том случае, если предшествующий элемент больше последующего.

Требуется, например, провести сортировку списка методом стандартного обмена или методом ’пузырька’ :

Ссылка на основную публикацию
Adblock detector