Insertion sort je jednoduchý třídící algoritmus, který funguje tak, jak třídíme hrací karty v našich rukou.
Program Python pro třídění vkládání
Funkce insertionSort bere jako vstup pole arr. Nejprve vypočítá délku pole (n). Pokud je délka 0 nebo 1, funkce se vrátí okamžitě, protože pole s prvkem 0 nebo 1 je považováno za již seřazené.
U polí s více než jedním prvkem funkce pokračuje v iteraci pole počínaje druhým prvkem. Vezme aktuální prvek (označovaný jako klíč) a porovná jej s prvky v seřazené části pole, které mu předcházejí. Pokud je klíč menší než prvek v seřazené části, funkce posune tento prvek doprava a vytvoří prostor pro klíč. Tento proces pokračuje, dokud není nalezena správná pozice klíče, a poté je do této pozice vložen.
Uvedený příklad ukazuje proces řazení pomocí algoritmu řazení vložení. Počáteční pole [12, 11, 13, 5, 6] je podrobeno funkci insertionSort. Po seřazení by pole mělo být [5, 6, 11, 12, 13]. Kód vytiskne seřazené pole jako konečný výstup.
obrácený řetězec v jazyce Java
Krajta
int v řetězci
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ýstup:
Sorted array is: [5, 6, 11, 12, 13]>
Časová složitost: O(N2)
Pomocný prostor: O(1)
Přečtěte si prosím celý článek na Řazení vkládání Více podrobností!