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

Лекция

Привет, сегодня поговорим про сортировка вставками, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое сортировка вставками , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

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

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

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

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

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

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

Ниже на анимированном изображении показан еще один пример работы алгоритма сортировки вставками. Об этом говорит сайт https://intellect.icu . Здесь, как и в предыдущем примере, последовательность сортируется по возрастанию.

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include "stdafx.h"
#include <iostream>
using namespace std;
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 ()
{
setlocale(LC_ALL, "Rus");
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;
system("pause>>void");
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

program InsertionSort;
uses crt;
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); {вызов функции}
readkey;
end.

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

На этом все! Теперь вы знаете все про сортировка вставками, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое сортировка вставками и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов

Из статьи мы узнали кратко, но содержательно про сортировка вставками

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

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

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

Комментарии

Оставить комментарий

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов