Program w Pythonie do sortowania przez wstawianie
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.
Pyton
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(N 2 )
Przestrzeń pomocnicza: O(1)
Proszę zapoznać się z pełnym artykułem na temat Sortowanie przez wstawianie po więcej szczegółów!
