Menu

Zoradenie vloženia v C ++ s príkladmi

insertion sort c with examples

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Hĺbkový pohľad na triedenie vloženia s klasickými príkladmi.

Insertion sort je technika triedenia, na ktorú sa dá pozerať tak, že hráme karty po ruke. Spôsob, akým vložíme ľubovoľnú kartu do balíčka alebo ju odstránime, funguje podobne.

Technika algoritmu triedenia vloženia je efektívnejšia ako techniky triedenia pomocou Bubble a Selection, ale je menej efektívna ako iné techniky, ako napríklad Quicksort a Merge.

=> Vyskúšajte tu najlepšie výukové programy pre C ++.

INSERTION SORT

Čo sa dozviete:

Prehľad

V technike triedenia vkladania vychádzame z druhého prvku a porovnáme ho s prvým prvkom a umiestnime ho na správne miesto. Potom vykonáme tento proces pre nasledujúce prvky.

Porovnáme každý prvok so všetkými jeho predchádzajúcimi prvkami a vložíme alebo vložíme prvok do správnej polohy. Technika triedenia vloženia je uskutočniteľnejšia pre polia s menším počtom prvkov. Je to užitočné aj na triedenie prepojených zoznamov.

inicializácia statickej premennej v c ++

Prepojené zoznamy majú ukazovateľ na nasledujúci prvok (v prípade jednotlivo prepojeného zoznamu) a tiež ukazovateľ na predchádzajúci prvok (v prípade dvojnásobne prepojeného zoznamu). Preto je jednoduchšie implementovať triedenie vloženia pre prepojený zoznam.

Poďme si v tomto výučbe preskúmať všetko o triedení vkladania.

Všeobecný algoritmus

Krok 1 : Opakujte kroky 2 až 5 pre K = 1 až N-1
Krok 2 : nastavená teplota = A [K]
Krok 3 : nastavenie J = K - 1
Krok 4 : Opakujte pri tepl<=A[J]
množina A [J + 1] = A [J]
množina J = J - 1
[koniec vnútornej slučky]
Krok 5 : sada A [J + 1] = tepl
[koniec slučky]
Krok 6 : východ

V technike triedenia vkladania teda vychádzame z druhého prvku, pretože predpokladáme, že prvý prvok je vždy zoradený. Potom od druhého prvku k poslednému prvku porovnáme každý prvok so všetkými jeho predchádzajúcimi prvkami a dáme tento prvok do správnej polohy.

Pseudokód

Pseudokód pre triedenie vloženia je uvedený nižšie.

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

Vyššie je uvedený pseudokód pre triedenie vloženia, ďalej si túto techniku ​​ilustrujeme v nasledujúcom príklade.

Ilustrácia

Pole, ktoré sa má zoradiť, je nasledovné:

najlepší bezplatný blokovanie automaticky otváraných okien pre chróm

pole na triedenie

Teraz pre každý prechod porovnávame aktuálny prvok so všetkými jeho predchádzajúcimi prvkami. Takže pri prvom prechode začneme druhým prvkom.

Triedenie vloženia - ilustrácia

Preto potrebujeme N počet prechodov na úplné triedenie poľa obsahujúceho N počet prvkov.

Vyššie uvedenú ilustráciu je možné zhrnúť do tabuľky:

PrejditeNetriedený zoznamporovnanieZoradený zoznam
1{12,3,5,10,8,1}{12.3}{3,12,5,10,8,1}
dva{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}

Ako je znázornené na vyššie uvedenej ilustrácii, začneme číslom 2ndprvok, pretože predpokladáme, že prvý prvok je vždy zoradený. Začneme teda porovnaním druhého prvku s prvým a zameníme pozíciu, ak je druhý prvok menší ako prvý.

Toto porovnanie a proces výmeny zamieňajú dva prvky na správne miesta. Ďalej porovnáme tretí prvok s jeho predchádzajúcimi (prvým a druhým) prvkom a rovnakým postupom vykonáme umiestnenie tretieho prvku na správne miesto.

Týmto spôsobom pre každý prechod umiestnime jeden prvok na jeho miesto. Pri prvom prechode umiestnime na jeho miesto druhý prvok. Všeobecne teda platí, že na umiestnenie N prvkov na ich správne miesto potrebujeme N-1 priechodov.

Ďalej si ukážeme implementáciu techniky triedenia Insertion v jazyku C ++.

Príklad 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 <

Výkon:

Zoznam vstupov je

12 4 3 1 15 45 33 21 10 2

Zoradený zoznam je

1 2 3 4 10 12 15 21 33 45

Ďalej uvidíme implementáciu Javy techniky triedenia Insertion.

Príklad 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] + ' '); } } }

Výkon:

Zadajte zoznam prvkov…

12 4 3 1 15 45 33 21 10 2

triedený zoznam prvkov ...

1 2 3 4 10 12 15 21 33 45

najlepšie miesto na pozeranie anime online

V obidvoch implementáciách vidíme, že začneme triediť od dvojkyndprvok poľa (premenná slučky j = 1) a opakovane porovnajte aktuálny prvok so všetkými jeho predchádzajúcimi prvkami a potom ho zoraďte tak, aby ho umiestnil do správnej polohy, ak aktuálny prvok nie je v poriadku so všetkými svojimi predchádzajúcimi prvkami.

Najlepšie funguje triedenie vloženia, ktoré je možné dokončiť za menej prechodov, ak je pole čiastočne zoradené. Ale ako sa zoznam zväčšuje, jeho výkonnosť klesá. Ďalšou výhodou zaradenia je to, že ide o stabilné triedenie, čo znamená, že udržuje poradie rovnakých prvkov v zozname.

Analýza zložitosti algoritmu triedenia vloženia

Z pseudokódu a ilustrácie vyššie je triedenie vloženia efektívnym algoritmom v porovnaní s triedením podľa bublín alebo výberom. Namiesto použitia pre cyklus a súčasné podmienky používa cyklus while, ktorý pri triedení poľa už nevykonáva žiadne ďalšie kroky.

Avšak aj keď odovzdáme zoradené pole technike triedenia Insertion, bude stále vykonávať vonkajšiu slučku for, čo si vyžaduje n počet krokov na zoradenie už zoradeného poľa. Toto robí najlepšiu časovú zložitosť vkladania triedením lineárnej funkcie N, kde N je počet prvkov v poli.

Nižšie sú uvedené rôzne zložitosti techniky triedenia vloženia:

Najhoršia časová zložitosťO (n 2)
Najlepšia časová zložitosť prípaduO (n)
Priemerná časová zložitosťO (n 2)
Zložitosť priestoruO (1)

Napriek týmto zložitostiam môžeme stále dospieť k záveru, že zoradenie podľa vloženia je najefektívnejším algoritmom v porovnaní s inými technikami triedenia, ako je triedenie podľa bubliniek a výber.

Záver

Vkladanie je najefektívnejšie zo všetkých troch doteraz diskutovaných techník. Tu predpokladáme, že prvý prvok je zoradený a potom opakovane porovnávame každý prvok so všetkými jeho predchádzajúcimi prvkami a potom aktuálny prvok umiestnime na správne miesto v poli.

V tomto tutoriáli, keď sme diskutovali o triedení vloženia, sme si všimli, že prvky porovnávame s prírastkom 1 a tiež sú na seba nadväzujúce. Výsledkom tejto funkcie je získanie ďalších priechodov na získanie zoradeného zoznamu.

V našom pripravovanom výučbe sa budeme zaoberať témou „Shell sort“, čo je vylepšenie oproti Selection sort.

Pri škrupinovom usporiadaní zavedieme premennú známu ako „prírastok“ alebo „medzera“, pomocou ktorej rozdelíme zoznam na podlisty obsahujúce nesúvislé prvky, ktoré od seba „oddeľujú“. Triedenie shellu vyžaduje v porovnaní s vložením menej prechodov a je tiež rýchlejšie.

V našich budúcich tutoriáloch sa dozvieme o dvoch technikách triedenia, „Quicksort“ a „Mergesort“, ktoré na triedenie dátových zoznamov používajú stratégiu „Divide and conquer“.

=> Tu si pozrite na Sprievodcu tréningom pre C ++ pre začiatočníkov.

Odporúčané čítanie

^