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.
![](https://cdn.wiki-base.com/2133874/insertion_sort_algorithm.png.webp)
- Prvý prvok v poli sa považuje za zoradený. Vezmite druhý prvok a uložte ho osobitne do
key
.
Porovnajkey
s prvým prvkom. Ak je prvý prvok väčší akokey
, 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(n2)
(n-1)
n*(n-1) ~ n2
- Najlepšia zložitosť prípadu:
O(n)
Keď je pole už zoradené, vonkajšia slučka bežín
niekoľkokrát, zatiaľ čo vnútorná slučka nefunguje vôbec. Existuje teda iban
niekoľ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(n2)
Zložitosť vesmíru
Zložitosť priestoru spočíva v tom, O(1)
že sa používa ďalšia premenná key
.
Aplikácie na triedenie vloženia
Triedenie vloženia sa používa, keď:
- pole má malý počet prvkov
- zostáva len pár prvkov na triedenie