Algoritmus zoradenia vloženia

V tomto výučbe sa dozviete, ako funguje triedenie vkladania. Nájdete tiež pracovné príklady triedenia vloženia v jazykoch C, C ++, Java a Python.

Triedenie podľa vloženia funguje podobne, ako keď v kartovej hre triedime karty v ruke.

Predpokladáme, že prvá karta je už zoradená, potom vyberieme netriedenú kartu. Ak je netriedená karta väčšia ako karta v ruke, je umiestnená vpravo, inak vľavo. Rovnakým spôsobom sa zoberú aj ďalšie netriedené karty a umiestnia sa na správne miesto.

Podobný prístup sa používa pri triedení vloženia.

Insertion sort je algoritmus triedenia, ktorý umiestňuje netriedený prvok na vhodné miesto v každej iterácii.

Ako funguje triedenie vloženia?

Predpokladajme, že musíme zoradiť nasledujúce pole.

Počiatočné pole

Prvý prvok v poli sa považuje za zoradený. Vezmite druhý prvok a uložte ho osobitne do key.
Porovnaj keys prvým prvkom. Ak je prvý prvok väčší ako key, potom sa kláves umiestni pred prvý prvok. Ak je prvý prvok väčší ako kľúč, potom sa kľúč umiestni pred prvý prvok.
Teraz sú prvé dva prvky zoradené.
Vezmite tretí prvok a porovnajte ho s prvkami na jeho ľavej strane. Umiestnil ho hneď za prvok menší ako on. Ak nie je žiadny prvok menší ako tento, umiestnite ho na začiatok poľa. Na začiatok položte 1
Podobne umiestnite každý netriedený prvok do správnej polohy. Miesto 4 za 1 Miesto 3 za 1 a pole je zoradené

Algoritmus zoradenia vloženia

 insertionSort (pole) označiť prvý prvok ako zoradený pre každý netriedený prvok X 'extrahovať' prvok X pre j X presunúť zoradený prvok doprava o 1 prerušovaciu slučku a vložiť X sem koniec insertionSort

Príklady jazyka Python, Java a 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); )

Zložitosť

Časové zložitosti

Najhoršia zložitosť: Predpokladajme, že pole je vo vzostupnom poradí a chcete ho zoradiť zostupne. V tomto prípade nastáva najhoršia zložitosť. Každý prvok musí byť porovnaný s každým z ostatných prvkov, takže pre každý n-tý prvok je vykonaný určitý počet porovnaní. Celkový počet porovnaní teda =O(n²)

(n-1)
n*(n-1) ~ n²
Najlepšia zložitosť prípadu: O(n)
Keď je pole už zoradené, vonkajšia slučka beží nniekoľkokrát, zatiaľ čo vnútorná slučka nefunguje vôbec. Existuje teda iba nniekoľko porovnaní. Zložitosť je teda lineárna.
Priemerná zložitosť prípadov: Vyskytuje sa, keď sú prvky poľa v neusporiadanom poradí (ani vzostupne, ani zostupne).O(n²)