Мени

Сортирање уметања у Ц ++ са примерима

insertion sort c with examples

Испробајте Наш Инструмент За Елиминисање Проблема

Детаљни поглед на сортирање уметања на класичним примерима.

Сортирање уметањем је техника сортирања која се може гледати на начин на који играмо карте при руци. Начин на који убацујемо било коју карту у шпил или је уклањамо, сортирање уметањем делује на сличан начин.

Техника алгоритма сортирања уметањем ефикаснија је од техника сортирања облачића и селекције, али је мање ефикасна од осталих техника попут брзе сортирања и спајања.

=> Овде погледајте најбоље туторијале за Ц ++.

ИНСЕРТИОН СОРТ

Шта ћете научити:

Преглед

У техници сортирања уметања почињемо од другог елемента и упоређујемо га са првим елементом и постављамо на одговарајуће место. Затим изводимо овај поступак за наредне елементе.

Упоређујемо сваки елемент са свим претходним елементима и стављамо или убацујемо елемент у његов одговарајући положај. Техника сортирања уметањем изводљивија је за низове са мањим бројем елемената. Такође је корисно за сортирање повезаних листа.

пц алати за скенирање и поправку прозори 10

Повезане листе имају показивач на следећи елемент (у случају појединачно повезане листе) и показивач на претходни елемент (у случају двоструко повезане листе). Стога постаје лакше применити сортирање уметања за повезану листу.

Истражимо све о сортирању уметања у овом водичу.

Општи алгоритам

Корак 1 : Поновите кораке 2 до 5 за К = 1 до Н-1
Корак 2 : постављена темп = А (К)
3. корак : скуп Ј = К - 1
4. корак : Поновите док је темп<=A(J)
скуп А (Ј + 1) = А (Ј)
скуп Ј = Ј - 1
(крај унутрашње петље)
Корак 5 : поставите А (Ј + 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

Горе наведени псеудо код за сортирање уметања, следеће ћемо илустровати ову технику у следећем примеру.

Илустрација

Низ који ће се сортирати је следећи:

низ који се сортира

који је најбољи бесплатни музички довнлоадер?

Сада за сваки пролаз упоређујемо тренутни елемент са свим претходним елементима. Дакле, у првом додавању почињемо са другим елементом.

Сорта уметања - илустрација

Стога нам је потребан Н број пролаза да бисмо у потпуности сортирали низ који садржи Н број елемената.

Горња илустрација може се резимирати у табеларном облику:

ПассНесортирана листаупоређивањеСортирана листа
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}

Као што је приказано на горњој илустрацији, започињемо са 2нделемент јер претпостављамо да је први елемент увек сортиран. Дакле, започињемо упоређивањем другог елемента са првим и заменимо позицију ако је други елемент мањи од првог.

Овај поступак поређења и замене поставља два елемента на њихова одговарајућа места. Затим упоређујемо трећи елемент са претходним (првим и другим) елементима и изводимо исти поступак да трећи елемент поставимо на одговарајуће место.

На тај начин, за сваки пролаз, постављамо један елемент на своје место. За прво додавање постављамо други елемент на његово место. Тако нам је генерално потребан Н-1 пролаз да бисмо поставили Н елемената на њихово одговарајуће место.

Даље, демонстрираћемо примену технике сортирања уметањем на језику Ц ++.

Пример Ц ++

#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

Даље, видећемо Јава примену технике сортирања Инсертион.

Пример Јаве

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

сортирана листа елемената ...

1 2 3 4 10 12 15 21 33 45

У обе примене видимо да започињемо сортирање од 2нделемент низа (променљива петље ј = 1) и више пута упоређујте тренутни елемент са свим претходним елементима, а затим сортирајте елемент тако да га постави у исправну позицију ако тренутни елемент није у реду са свим претходним елементима.

Сортирање уметања најбоље функционише и може се довршити за мање пролаза ако је низ делимично сортиран. Али како листа расте, његове перформансе опадају. Још једна предност сортирања уметањем је што је стабилна сорта, што значи да одржава редослед једнаких елемената на листи.

шта радити са торрент датотеком

Анализа сложености алгоритма сортирања уметања

Из псеудо кода и горње илустрације сортирање уметања је ефикасан алгоритам у поређењу са сортирањем облачића или сортирањем избора. Уместо да користи фор лооп и тренутне услове, користи вхиле петљу која не извршава више додатних корака када се низ сортира.

Међутим, чак и ако сортирани низ проследимо техници сортирања Инсертион, он ће и даље извршавати спољну фор петљу, захтевајући тако н број корака за сортирање већ сортираног низа. Ово чини најбољу временску сложеност уметања сортирањем линеарном функцијом Н где је Н број елемената у низу.

Стога су у наставку дате разне сложености технике сортирања уметањем:

Најгора временска сложеностО (н 2)
Најбоља временска сложеностНа)
Просечна временска сложеностО (н 2)
Сложеност простораО (1)

Упркос овим сложеностима, још увек можемо закључити да је сортирање уметањем најефикаснији алгоритам у поређењу са осталим техникама сортирања попут мехурића сортирања и сортирања селекције.

Закључак

Сортирање уметања је најефикаснија од све три технике о којима смо до сада разговарали. Овде претпостављамо да је први елемент сортиран, а затим узастопно упоређујемо сваки елемент са свим претходним елементима, а затим тренутни елемент постављамо на његов тачан положај у низу.

У овом водичу, док смо разговарали о сортирању уметања, приметили смо да упоређујемо елементе помоћу повећања од 1, а такође су и суседни. Ова функција резултира потребом за више пролаза за добијање сортиране листе.

У нашем предстојећем упутству разговараћемо о „сортирању шкољке“, што је напредак у односу на сортирање избора.

У сортирању љуске уводимо променљиву познату као „прираштај“ или „празнина“ помоћу које делимо листу на подлисте које садрже несаседне елементе који се „раздвајају“. Сортирање шкољке захтева мање пролаза у поређењу са сортирањем уметања и такође је брже.

У нашим будућим водичима научићемо о две технике сортирања, „Куицксорт“ и „Мергесорт“ које користе стратегију „Подели и освоји“ за сортирање листа података.

=> Овде припазите на водич за обуку за почетнике Ц ++.

Препоручено читање

^