Сортировка методом вставок

Содержание

 

 

Сортировка  методом вставок

И последний  алгоритм из первого рассматриваемого нами набора - сортировка методом вставок, или сортировка простыми вставками (insertion sort). Этот алгоритм покажется знакомым всем, кто играет в такие карточные игры, как вист или бридж, поскольку большинство игроков сортирует свои карты именно так .Начинаем с левого края колоды. Сравниваем две первые карты и располагаем их в правильном порядке. Смотрим на третью карту. Вставляем ее в требуемое место по отношению к первым двум картам. Смотрим на четвертую карту и вставляем ее в требуемое место по отношению к первым трем картам. Те же операции выполняем с пятой, шестой, седьмой и всеми последующими картами. При перемещении слева направо левая часть колоды будет отсортированной. В приведенной реализации сортировки методом вставок имеется одна очень интересная особенность: значение текущего элемента сохраняется в локальной переменной, а затем при поиске нужного места его вставки (внутренний цикл) мы перемещаем каждый элемент, значение которого больше текущего, на одну позицию вправо, тем самым, перемещая "дыру" в списке влево. В конце концов, мы находим нужное место и помещаем сохраненное значение в освободившееся место. Давайте посмотрим на внутренний цикл. Его выполнение завершается при соблюдении одного из двух условий: достигнуто начало списка, т.е. текущее значение меньше значений всех уже отсортированных элементов, или обнаружено значение, меньшее текущего. Тем не менее, обратите внимание, что первое условие проверяется при каждом выполнении внутреннего цикла, несмотря на то что оно соблюдается достаточно редко, когда текущее значение меньше, чем значения всех уже отсортированных элементов, однако оно предотвращает выход за пределы списка. Традиционным методом исключения этой дополнительной проверки является введение в начало списка сигнального элемента, который меньше любого другого элемента в списке. К сожалению, в общем случае минимальный элемент в списке заранее неизвестен и, кроме того, в списке нет места для вставки дополнительного элемента. (Теоретически потребуется скопировать весь список в другой, размер которого больше на один элемент, установить значение первого элемента в этом новом списке равным минимальному значению из сортируемого списка, а затем после сортировки скопировать элементы в исходный список. И все это ради того, чтобы исключить одну проверку. Нет уж, спасибо.) Существует более эффективный метод оптимизации: просмотреть весь список, найти элемент с наименьшим значением и переставить его на первое место (фактически это выполнение первого цикла Сортировки методом «выбора). Теперь, когда первый элемент находится в требуемой позиции, можно выполнять стандартную процедуру метода вставок и игнорировать возможность выхода за начало списка. Хотите верьте, хотите нет, но предварительная установка наименьшего значения в первую позицию и исключение дополнительной проверки выхода за границы списка при тестировании дала увеличение быстродействия примерно на 7%. Как и три предыдущие рассмотренные нами алгоритма, сортировка методом вставок принадлежит к классу алгоритмов О(п2). Как и в случае с пузырьковой, сортировкой, если исходный список уже отсортирован, сортировка методом вставок практически не выполняет никаких действий помимо сравнения пар двух соседних элементов. Худшим случаем для сортировки методом вставок является ситуация, когда исходный список отсортирован в обратном порядке (как и для пузырьковой сортировки) - для попадания в требуемое место каждому элементу нужно пройти максимальное расстояние. Тем не менее, если список частично отсортирован, и каждый элемент находится недалеко от требуемого места, сортировка методом вставок будет выполняться очень быстро. Фактически она превращается в алгоритм класса О(л). (Другими словами, внешний цикл выполняется n-1 раз, а внутренний - всего несколько раз, что соответствует небольшому расстоянию элементов от их позиции в отсортированном списке.) Таким образом, во внутреннем цикле выполняется некоторое постоянное количество проходов (т.е. сравнений и перемещений), скажем, d. Для внешнего цикла, как мы уже говорили, количество проходов равно n - 1. Следовательно, общее количество сравнений и перемещений будет выражаться значением d(n- 1) (алгоритм класса О(n)). Несмотря на то что на практике частично отсортированные списки встречаются достаточно редко, тем не менее, возможна ситуация, когда с частично отсортированными списками можно сталкиваться гораздо чаще. Мы рассмотрим эту ситуацию немного ниже. Сортировка методом вставок (любая ее вариация) принадлежит к группе устойчивых алгоритмов. Она сохраняет относительное положение элементов с равными значениями, поскольку поиск требуемой позиции для элемента завершается, когда найден элемент, значение которого меньше или равно значению текущего элемента. Следовательно, относительное положение элементов с равными значениями сохраняется. Как и при пузырьковой сортировке, при сортировке методом вставок элементы попадают в нужные позиции только за счет смены позиций с соседними элементами. Если элемент находится далеко от требуемой позиции, его перемещение занимает много времени. Если бы только мы могли перемещать элементы не через соседние элементы, а сразу в некоторый диапазон, где текущий элемент должен находиться!

Рисунок 1.  Выборочная сортировка. В массиве слева  значение 1 в исходном состоянии занимает 4-й  элемент. Массив справа показывает результат обмена элемента 0 (т. e. начального элемента массива) с элементом 4 (наименьшим в массиве).

Если подвергнуть  выборочной сортировке массив на рис. 1, то алгоритм сортировки также будет  просматривать подмассивы, отыскивая  каждый раз минимальное значение. Однако вместо обмена пар соседних значений, стоящих не в том порядке, алгоритм просто записывает индекс минимального значения и затем производит единственный обмен его со значением, которое занимает в данный момент верхнюю позицию в подмассиве. Первый проход по массиву на рис. 1  находит, что минимальное значение, равное 1, занимает 4-й элемент. Как только это определено, элементы нулевой и четвертый обмениваются значениями. Результат показан на рис. 2. Затем выборочная сортировка сканирует все меньшие и меньшие подмассивы, аналогично пузырьковой сортировке.

Код сортировки 

#include "sort.h"

// Файл ss.cpp реализует шаблон функции selectionjsort( ),

// которая сортирует элементы своего входного массива

// в восходящем порядке.  Тип Т должен поддерживать

// operator=( ) и operator<( ). Для инициализации

// может потребоваться  копирование. Если  требуется печать,

// необходима operator<<( ). Аргумент array содержит подлежащие

// сортировке элементы, size является числом элементов

// этого массива. Сортировка производится "по месту." Допускаются

// повторяющиеся элементы.

// Get_min_index( ) возвращает индекс массива, соответствующий // минимальному значению подмассива, определяемому

// left и right. 

template <class Т>

inline int get__min_index(T array[], int left, int right)

{

int min_index = left;

int i; 

for (i = left; i <= right; ++i) {

if (array[i] < array[min_index]) min_index = i;

  }

return min_index;

} 

// Selectionjsort( ) выбирает нужный элемент для каждого

// индекса массива, начиная с нулевого индекса и

// двигаясь вверх. 

template <class Т>

inline void selection_sort(Т array[], int size)

{

int i;

  int min_index; 

// Верхний предел  внешнего цикла  равен size-1, а не

// size, так как если все прочие элементы заняли свои места,

// наибольший автоматически  оказывается в  нужной позиции. 

for (i=0; i < size-1; ++i) {

min_index = get_min_index(array, i, size-1);

if (min_index != i) swap (array, i, min_index) ;

 }

}

int main( )

{

int array_l[] = {7, 3, 8, 2, 1, 5, 4};

print(array_l, 7);

selection_sort(array_l, 7);

print(array_l, 7);

cout << endl; 

int array_2[] = {7, 3, 8, 2, 1, 5, 4, 9, 75, -5};

print(array_2, 10);

selection_sort(array_2, 10);

print(array_2, 10);

cout << endl; 

int array_3[] = {1, 2, 3};

print(array_3, 3) ;

  selection_sort(array_3, 3);

print(array_3, 3);

cout << endl; 

int array_4[] = {3, 2,1};

print(array_4, 3);

selection__sort(array_4, 3);

print(array_4, 3) ;

  cout << endl; 

int array_5[] = {3, 2, 1, 3};

print (array_5, 4) ;

selection_sort(array_5, 4);

print(array_5, 4) ;

cout << endl; 

int array_6[] = {3, 3, 3};

print(array_6, 3);

selection_sort(array_6, 3);

print (array_6, 3) ;

cout << endl;

return 0;

} 

Упражнения 

1. В стиле рис. 1показать, как сортируется набор  символов ЦМАРОБДН методом вставок.

2. Является ли  сортировка вставками устойчивой?

3а. Есть восемь  целых чисел 1, 7, 3, 2, 0, 5, 0, 8. Выполните  их упорядочивание 

с помощью метода сортировки вставками.

3б. Есть шестнадцать  целых чисел 22, 36, 6, 79, 26, 45, 75, 13, 31, 62, 27, 76, 33,

16, 62, 47. Трактуя каждое  число как пару цифр из интервала  0-9, выполните 

их упорядочивание, используя сортировку вставками.

4.