Sortowanie przez wstawianie to prosty algorytm sortowania, który działa w taki sam sposób, w jaki sortujemy karty do gry, które mamy w rękach.
Program w Pythonie do sortowania przez wstawianie
Funkcja InsertionSort przyjmuje jako dane wejściowe tablicę arr. Najpierw oblicza długość tablicy (n). Jeśli długość wynosi 0 lub 1, funkcja zwraca natychmiast, ponieważ tablica zawierająca element 0 lub 1 jest uważana za już posortowaną.
W przypadku tablic zawierających więcej niż jeden element funkcja kontynuuje iterację po tablicy, zaczynając od drugiego elementu. Pobiera bieżący element (zwany kluczem) i porównuje go z elementami w posortowanej części tablicy, które go poprzedzają. Jeśli klucz jest mniejszy niż element w posortowanej części, funkcja przesuwa ten element w prawo, tworząc miejsce na klucz. Proces ten trwa do momentu znalezienia właściwej pozycji klucza, po czym zostaje on włożony w tę pozycję.
Podany przykład ilustruje proces sortowania przy użyciu algorytmu sortowania przez wstawianie. Początkowa tablica [12, 11, 13, 5, 6] poddawana jest funkcji InsertionSort. Po posortowaniu tablica powinna wynosić [5, 6, 11, 12, 13]. Kod wypisuje posortowaną tablicę jako wynik końcowy.
typy drzew binarnych
Pyton
znak do ciągu 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)> |
>
>
Wyjście:
Sorted array is: [5, 6, 11, 12, 13]>
Złożoność czasowa: O(N2)
Przestrzeń pomocnicza: O(1)
Proszę zapoznać się z pełnym artykułem na temat Sortowanie przez wstawianie po więcej szczegółów!