Vkladanie triedenia je jednoduchý triediaci algoritmus, ktorý funguje tak, ako triedime hracie karty v našich rukách.
Program Python na triedenie vkladania
Funkcia insertionSort berie ako vstup pole arr. Najprv vypočíta dĺžku poľa (n). Ak je dĺžka 0 alebo 1, funkcia sa okamžite vráti, pretože pole s prvkom 0 alebo 1 sa považuje za už zoradené.
V prípade polí s viac ako jedným prvkom funkcia pokračuje v iterácii poľa od druhého prvku. Zoberie aktuálny prvok (označovaný ako kľúč) a porovná ho s prvkami v zoradenej časti poľa, ktoré mu predchádzajú. Ak je kľúč menší ako prvok v zoradenej časti, funkcia posunie tento prvok doprava, čím sa vytvorí priestor pre kľúč. Tento proces pokračuje, kým sa nenájde správna poloha kľúča a potom sa vloží do tejto polohy.
Poskytnutý príklad demonštruje proces triedenia pomocou algoritmu triedenia vloženia. Počiatočné pole [12, 11, 13, 5, 6] sa podrobí funkcii insertionSort. Po zoradení by pole malo byť [5, 6, 11, 12, 13]. Kód vytlačí zoradené pole ako konečný výstup.
aws sns
Python
dátové štruktúry v jazyku Java
def> insertionSort(arr):> >n>=> len>(arr)># Get the length of the array> > >if> n <>=> 1>:> >return> # If the array has 0 or 1 element, it is already sorted, so return> >for> i>in> range>(>1>, n):># Iterate over the array starting from the second element> >key>=> arr[i]># Store the current element as the key to be inserted in the right position> >j>=> i>->1> >while> j>>=> 0> and> key # Move elements greater than key one position ahead arr[j+1] = arr[j] # Shift elements to the right j -= 1 arr[j+1] = key # Insert the key in the correct position # Sorting the array [12, 11, 13, 5, 6] using insertionSort arr = [12, 11, 13, 5, 6] insertionSort(arr) print(arr)> |
>
>
Výkon:
Sorted array is: [5, 6, 11, 12, 13]>
Časová zložitosť: O(N2)
Pomocný priestor: O(1)
Pozrite si celý článok na Triedenie vloženia pre viac detailov!