«

»

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

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

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

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

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

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

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

Ниже на анимированном изображении показан еще один пример работы алгоритма сортировки вставками. Здесь, как и в предыдущем примере, последовательность сортируется по возрастанию.

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

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

 

Код программы на 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.

2 комментария

  1. Андрей

    key=i+1;
    var=mas[key];
    for (j=i+1; j>=0; j—)
    {
    if (var<mas[j-1])
    {
    mas[j]=mas[j-1];
    key=j-1;

    что реализовано в этом цикле и за что отвечает переменная key и var?

    1. А. С. Третьяков

      Вся статья (в том числе и код программ) была переписана. Прочитайте ее и если возникнут вопросы, то, пожалуйста, задавайте их.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Проверка на человечность *