Сортиране чрез пряко вмъкване

Този метод се използва широко от картоиграчите. Преглеждат се картите една по една. Всяка карта, която не си е на мястото се вади и се вмъква на подходящото място. Останалите карти се изместват.

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

Пример:

Блокова схема на алгоритъма:

Търсенето на подходящото място започва с втория елемент на масива (с индекс 1), тъй като първият няма с кого да се сравнява. Вторият елемент, в случая със стойност 55 се сравнява с първия(стойност 44). 55>44 следователно частичната подредба е добра и няма да настъпва вмъкване. След това се взима третия елемент от масива(стойност 12). Той се сравнява с втория елемент(стойност 55). 12<55 следователно 55 се измества с една позиция вдясно(индекс 2). Индекс 1 е свободен. 12 се сравнява със следващия елемент отляво(стойност 44). 12<44 следователно 44 се измества една позиция вдясно(индекс 1). Индекс 0 е свободен, така че вляво вече няма елементи за сравняване, 12 се записва на първо място в масива(индекс 0). До третият елемент масива е частично подреден. Взима се четвъртият елемент от масива(стойност 42) и се сравнява с лявостоящият от него(55 с индекс 2). 42<55 - следва изместване на 55 с един елемент вдясно(индекс 3). Индекс 2 е свободен. 42 се сравнява със следващия елемент отляво - 44(индекс 1). 42<44 - следва изместване на 44 с един елемент вдясно(индекс 2). Индекс 1 е свободен. 42 се сравнява със следващия елемент отляво - 12(индекс 0). 42>12 - няма изместване. 42 се записва в свободния индекс 1. Масивът е частично подреден до четвъртия елемент. Операцията се повтаря до изчерпване на масива.

Алгоритъм 1:

Бихме могли да разделим задачата на три подзадачи:

1) Намираме подходящо място(елемента след който трябва да се вмъкне числото х). Това може да се реализира като х се сравнява последователно с всеки елемент стоящ отляво на него в редицата.

2) Изместваме подмасива, заключен между “подходящото място” и текущото място на х, с един елемент в дясно.

3) Записваме х на “подходящото място”.

Но този подход предполага две обхождания на подредената част на масива, първо за намиране на подходящо място и второ за изместването. Би могъл да се намери и по-бърз алгоритъм, с едно обхождане на подмасива като се съвместят във времето процесът на търсене и преместване.

Алгоритъм 2:

Елемента х се сравнява с елемента, стоящ отляво в масива. Ако х е с по-малка стойност от този елемент, то той се премества една позиция вдясно в масива (редицата), ако ли пък не следователно х се намира на подходящото си място в подмасива. Сравняването се прекратява. След напускане на цикъла х се записва в елемента с индекс [j+1] – свободният елемент.

Този алгоритъм има два съществени недостатъка.

1. В случай, че х се намира на подходящото си място, се извършва едно паразитно записване на х върху себе си.

2. Преместването на елементите от подмасива изисква много време, особено в случаите, когато елемент от края на масива трябва да се вмъкне в неговото начало.

Алгоритъм за вмъкване на х:

Пълният алгоритъм за сортиране чрез пряко вмъкване се описва със следната блокова схема:

//Листинг 1.

//Сортиране чрез пряко вмъкване

# include <iostream.h>

void input(float a[100], int &n)

{

int i;

cout<<"n=";

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

{

cout<<"a["<<i<<"]=";

cin>>a[i];

}

}

void output (float a[100], int n)

{

int i;

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

{

cout<<a[i]<<'\t';

}

}

void sort(float a[100], int n)

{

int i,j;

float x;

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

{

x=a[i];

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

{ if(x<a[j]) a[j+1]=a[j];

else break;

}

a[j+1]=x;

}

}

void main(void)

{

int n;

float a[100];

input (a,n) ;

sort (a,n) ;

output (a,n) ;

}