Меню

Сортиране по вмъкване в C ++ с примери

insertion sort c with examples

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

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

Техниката за алгоритъм за сортиране при вмъкване е по-ефективна от техниките за сортиране на мехурчета и сортиране по избор, но е по-малко ефективна от другите техники като сортиране с бързо сортиране и обединяване.

=> Вижте най-добрите уроци за обучение на C ++ тук.

СОРТИРАНЕ НА ВЪВЕЖДАНЕ

Какво ще научите:

Общ преглед

В техниката за сортиране на вмъкване започваме от втория елемент и го сравняваме с първия елемент и го поставяме на подходящо място. След това изпълняваме този процес за следващите елементи.

Сравняваме всеки елемент с всички предишни елементи и поставяме или вмъкваме елемента в правилното му положение. Техниката за сортиране на вмъкване е по-осъществима за масиви с по-малък брой елементи. Също така е полезно за сортиране на свързани списъци.

Свързаните списъци имат указател към следващия елемент (в случай на единично свързан списък) и указател към предишния елемент (в случай на двойно свързан списък). Следователно става по-лесно да се приложи сортиране на вмъкване за свързан списък.

c ++ инициализира статична променлива

Нека разгледаме всичко за вмъкването в този урок.

Общ алгоритъм

Етап 1 : Повторете стъпки 2 до 5 за K = 1 до N-1
Стъпка 2 : задайте temp = A [K]
Стъпка 3 : задайте J = K - 1
Стъпка 4 : Повторете, докато темп<=A[J]
задайте A [J + 1] = A [J]
задайте J = J - 1
[край на вътрешния цикъл]
Стъпка 5 : задайте A [J + 1] = темп
[край на цикъла]
Стъпка 6 : изход

По този начин, в техниката за сортиране на вмъкване, ние започваме от втория елемент, тъй като приемаме, че първият елемент винаги е сортиран. След това от втория елемент до последния елемент, ние сравняваме всеки елемент с всички негови предишни елементи и поставяме този елемент в правилната позиция.

Псевдокод

Псевдо кодът за сортиране при вмъкване е даден по-долу.

procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //locate free position to insert the element whilefreePosition> 0 and array[freePosition -1] >insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //insert the number at free position array [freePosition] = insert_val end for end procedure

По-горе е даден псевдо кодът за сортиране на вмъкване, след това ще илюстрираме тази техника в следващия пример.

Илюстрация

Масивът за сортиране е както следва:

масив за сортиране

Сега за всеки проход сравняваме текущия елемент с всички предишни елементи. Така че при първото преминаване започваме с втория елемент.

Сортиране при вмъкване - илюстрация

По този начин се изисква N брой проходи, за да се сортира напълно масив, съдържащ N брой елементи.

Горната илюстрация може да бъде обобщена в таблична форма:

ПодайтеНесортиран списъксравнениеСортиран списък
1{12,3,5,10,8,1}{12.3}{3,12,5,10,8,1}
две{3,12,5,10,8,1}{3,12,5}{3,5,12,10,8,1}
3{3,5,12,10,8,1}{3,5,12,10}{3,5,10,12,8,1}
4{3,5,10,12,8,1}{3,5,10,12,8}{3,5,8,10,12,1}
5{3,5,8,10,12,1}{3,5,8,10,12,1}{1,3,5,8,10,12}
6{}{}{1,3,5,8,10,12}

Както е показано на горната илюстрация, започваме с 2ndелемент, тъй като приемаме, че първият елемент винаги е сортиран. И така, започваме с сравняването на втория елемент с първия и разменяме позицията, ако вторият елемент е по-малък от първия.

Този процес на сравнение и размяна позиционира два елемента на подходящите им места. След това сравняваме третия елемент с предишните му (първи и втори) елементи и изпълняваме същата процедура, за да поставим третия елемент на правилното място.

По този начин за всеки проход поставяме по един елемент на негово място. За първото преминаване поставяме втория елемент на негово място. По този начин като цяло, за да поставим N елемента на правилното им място, ни трябват N-1 проходи.

как да превърна видео от youtube в wav файл

След това ще демонстрираме изпълнението на техниката за сортиране на вмъкване на език C ++.

Пример за C ++

#include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout<<' Input list is '; for(int i=0;i<10;i++) { cout <

Изход:

Списъкът за въвеждане е

12 4 3 1 15 45 33 21 10 2

Сортираният списък е

1 2 3 4 10 12 15 21 33 45

След това ще видим изпълнението на Java на техниката за сортиране Insertion.

Пример за Java

public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println('Input list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray[i] + ' '); } for(int k=1; k=0 && temp <= myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println(' sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray[i] + ' '); } } }

Изход:

Входен списък с елементи ...

12 4 3 1 15 45 33 21 10 2

сортиран списък с елементи ...

как да видите .swf файлове

1 2 3 4 10 12 15 21 33 45

И в двете реализации можем да видим, че започваме сортирането от 2ndелемент на масива (циклична променлива j = 1) и многократно сравнява текущия елемент с всички негови предишни елементи и след това сортира елемента, за да го постави в правилното му положение, ако текущият елемент не е в ред с всичките му предишни елементи.

Сортирането по вмъкване работи най-добре и може да бъде завършено за по-малко проходи, ако масивът е частично сортиран. Но тъй като списъкът се увеличава, производителността му намалява. Друго предимство на Insertion sort е, че е стабилно сортиране, което означава, че поддържа реда на равни елементи в списъка.

Анализ на сложността на алгоритъма за сортиране на вмъкването

От псевдо кода и илюстрацията по-горе сортирането при вмъкване е ефективният алгоритъм в сравнение с сортирането на балончета или сортирането по селекция. Вместо да използва за цикъл и настоящи условия, той използва цикъл while, който не извършва повече допълнителни стъпки, когато масивът е сортиран.

Въпреки това, дори ако предадем сортирания масив на техниката за сортиране Insertion, той пак ще изпълни външния цикъл for, като по този начин ще изисква n брой стъпки за сортиране на вече сортиран масив. Това прави най-добрата сложност по време на вмъкване сортира линейна функция на N, където N е броят на елементите в масива.

По този начин различните сложности на техниката за сортиране на вмъкване са дадени по-долу:

Най-лошата времева сложностO (n 2)
Най-добрата сложност във времетоНа)
Средна времева сложностO (n 2)
Космическа сложностO (1)

Въпреки тези сложности, все още можем да заключим, че Insertion sort е най-ефективният алгоритъм в сравнение с другите техники за сортиране като Bubble sort и Selection sort.

Заключение

Сортирането с вмъкване е най-ефективното от всичките три дискутирани досега техники. Тук приемаме, че първият елемент е сортиран и след това многократно сравняваме всеки елемент с всичките му предишни елементи и след това поставяме текущия елемент в правилната му позиция в масива.

В този урок, докато обсъждаме сортирането на вмъкването, забелязахме, че сравняваме елементите, като използваме стъпка от 1, а също така те са съседни. Тази функция води до изискване на повече пропуски, за да се получи сортираният списък.

В нашия предстоящ урок ще обсъдим “Сортиране на черупки”, което е подобрение спрямо сортирането на селекцията.

При сортиране на черупки въвеждаме променлива, известна като „инкремент“ или „празнина“, с помощта на която разделяме списъка на подлисти, съдържащи несвързани елементи, които „празнина“ разделят. Сортирането на черупки изисква по-малко проходи в сравнение с вмъкването и също така е по-бързо.

В нашите бъдещи уроци ще научим за две техники за сортиране, „Quicksort“ и „Mergesort“, които използват стратегия „Разделяй и владей“ за сортиране на списъци с данни.

=> Внимавайте тук за начинаещи ръководства за обучение на C ++.

Препоръчително четене

^