Програма Python для сортування вставкою
Сортування за допомогою вставки – це простий алгоритм сортування, який працює так само, як ми сортуємо гральні карти в наших руках.
Програма Python для сортування вставкою
Функція insertionSort приймає масив arr як вхідні дані. Спочатку обчислюється довжина масиву (n). Якщо довжина дорівнює 0 або 1, функція негайно повертає, оскільки масив з 0 або 1 елементом вважається вже відсортованим.
Для масивів з більш ніж одним елементом функція переходить до масиву, починаючи з другого елемента. Він бере поточний елемент (званий ключем) і порівнює його з елементами у відсортованій частині масиву, які йому передують. Якщо ключ менший за елемент у відсортованій частині, функція зміщує цей елемент праворуч, створюючи простір для ключа. Цей процес триває до тих пір, поки не буде знайдено правильне положення для ключа, після чого він буде вставлений у це положення.
Наведений приклад демонструє процес сортування за допомогою алгоритму сортування вставкою. Початковий масив [12, 11, 13, 5, 6] піддається функції insertionSort. Після сортування масив має бути [5, 6, 11, 12, 13]. Код друкує відсортований масив як кінцевий результат.
Python
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)> |
Вихід:
Sorted array is: [5, 6, 11, 12, 13]
Часова складність: O(N 2 )
Допоміжний простір: O(1)
Перегляньте повну статтю Сортування вставкою для більш детальної інформації!
