Algorytm sortowania przez wstawianie

W tym samouczku dowiesz się, jak działa sortowanie przez wstawianie. Znajdziesz również działające przykłady sortowania przez wstawianie w językach C, C ++, Java i Python.

Sortowanie przez wstawianie działa podobnie do sortowania kart w ręce w grze karcianej.

Zakładamy, że pierwsza karta jest już posortowana, więc wybieramy kartę niesortowaną. Jeśli niesortowana karta jest większa niż karta w ręku, jest umieszczana po prawej stronie, w przeciwnym razie po lewej stronie. W ten sam sposób inne niesortowane karty są pobierane i umieszczane we właściwych miejscach.

Podobne podejście jest stosowane przy sortowaniu przez wstawianie.

Sortowanie przez wstawianie to algorytm sortowania, który umieszcza nieposortowany element w odpowiednim miejscu w każdej iteracji.

Jak działa sortowanie przez wstawianie?

Załóżmy, że musimy posortować następującą tablicę.

Tablica początkowa

Zakłada się, że pierwszy element tablicy jest posortowany. Weź drugi element i przechowuj go osobno w key.
Porównaj keyz pierwszym elementem. Jeśli pierwszy element jest większy niż key, to klucz jest umieszczany przed pierwszym elementem. Jeśli pierwszy element jest większy niż klucz, klucz jest umieszczany przed pierwszym elementem.
Teraz pierwsze dwa elementy są posortowane.
Weź trzeci element i porównaj go z elementami po lewej stronie. Umieścił go tuż za elementem mniejszym od niego. Jeśli nie ma elementu mniejszego od niego, umieść go na początku tablicy. Umieść 1 na początku
Podobnie, umieść każdy nieposortowany element we właściwej pozycji. Umieść 4 za 1 Umieść 3 za 1, a tablica zostanie posortowana

Algorytm sortowania przez wstawianie

 insertionSort (tablica) zaznacz pierwszy element jako posortowany dla każdego nieposortowanego elementu X 'wyodrębnij' element X dla j X przesuń posortowany element w prawo o 1 pętlę przerywającą i wstaw X tutaj end insertionSort

Przykłady w Pythonie, Javie i C / C ++

Python Java C C ++

 # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)

  // Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )

 // Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )

Złożoność

Złożoność czasowa

Złożoność najgorszego przypadku: Załóżmy, że tablica jest w porządku rosnącym i chcesz posortować ją w porządku malejącym. W takim przypadku występuje najgorsza złożoność przypadku. Każdy element musi być porównany z każdym innym elementem, więc dla każdego n-tego elementu dokonuje się wielu porównań. Zatem całkowita liczba porównań =O(n²)

(n-1)
n*(n-1) ~ n²
Najlepsza złożoność O(n)
przypadku : gdy tablica jest już posortowana, zewnętrzna pętla działa nwiele razy, podczas gdy wewnętrzna pętla w ogóle nie działa. Tak więc jest tylko nliczba porównań. Zatem złożoność jest liniowa.
Średnia złożoność wielkości liter: występuje, gdy elementy tablicy są pomieszane (ani rosnąco, ani malejąco).O(n²)