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

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

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

1. первая и вторая карта меньше третьей;

2. первая и вторая карта больше третьей;

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

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

В первом случае не происходит никаких перестановок. Во втором – вторая карта смещается на место третьей, первая на место второй, а третья карта занимает позицию первой. В предпоследнем случае первая карта остается на своем месте, в то время как вторая и третья меняются местами. Ну и наконец, последний случай требует рокировки лишь первой и третьей карт. Все последующие шаги полностью аналогичны расписанным выше.

Рассмотрим на примере числовой последовательности процесс сортировки методом вставок (рис. 6.3). Клетка, выделенная темно-серым цветом – активный на данном шаге элемент, ему также соответствует i -ый номер. Светло-серые клетки это те элементы, значения которых сравниваются с i -ым элементом. Все, что закрашено белым – не затрагиваемая на шаге часть последовательности.

Рисунок 6.3 – Пример сортировки вставками

Таким образом, получается, что на каждом этапе выполнения алгоритма сортируется некоторая часть массива, размер которой с шагом увеличивается, и в конце сортируется весь массив целиком.

Код программы на C++:

int i, j, key=0, temp=0;

void InsertSort(int *mas, int n) //сортировка вставками

{

for (i=0; i<n-1; i++)

{

key=i+1;

temp=mas[key];

for (j=i+1; j>0; j--)

{

if (temp<mas[j-1])

{

mas[j]=mas[j-1];

key=j-1;

}

}

mas[key]=temp;

}

cout<<endl<<"Результирующий массив: ";

for (i=0; i<n; i++) //вывод массива

cout<<mas[i]<<" ";

}

void main () //главная функция

{

int n;

cout<<"Количество элементов в массиве > "; cin>>n;

int *mas=new int[n];

for (i=0; i<n; i++) //ввод массива

{

cout<<i+1<<" элемент > ";

cin>>mas[i];

}

InsertSort(mas, n); //вызов функции

delete[] mas;

}

Код программы на Pascal:

type arr=array[1..1000] of integer;

var mas: arr;

i, j, temp, nom, n: integer;

procedure InsertSort(mas: arr; n: integer); {процедура сортировки вставками}

begin

for i:=1 to n-1 do

begin

nom:=i+1;

temp:=mas[nom];

for j:=i+1 downto 2 do

begin

if (temp<mas[j-1]) then

begin

mas[j]:=mas[j-1];

nom:=j-1;

end;

end;

mas[nom]:=temp;

end;

write('Результирующий массив: ');

for i:=1 to n do write(mas[i], ' '); {вывод массива}

end;

begin {основной блок программы}

write('Количество элементов в массиве > '); read(n);

for i:=1 to n do {ввод массива}

begin

write(i,' элемент > ');

read(mas[i]);

end;

InsertSort(mas, n); {вызов функции}

end.

Обе программы сортируют массив по возрастанию. В их основной части выполняются три операции: определение количества элементов в массиве, ввод этих элементов и вызов подпрограммы. Подпрограмма состоит из алгоритма сортировки и цикла, выводящего результирующую упорядоченную последовательность. Алгоритм включает в себя классическую для многих алгоритмов сортировки структуру вложенных циклов. Количество итераций внешнего цикла не превышает n -1, где n – число элементов в массиве; внутренний цикл, начиная с шага i +1, заканчивает свое выполнение при j =0 (значение переменной-счетчика j уменьшается с каждым шагом на 1). Переменным key и temp на i -ом шаге присваиваются значения, зависящие от шага и значения элемента массива mas на этом шаге. В переменной temp храниться значение элемента массива mas[ i +1], оно во внутреннем цикле сравнивается со значениями других элементов. Key запоминает индекс элемента, который последним был больше temp, и ему, по завершению работы внутреннего цикла, присваивается значение переменной temp.