Zvažte následující čísla:
50 60 30 10 80 70 20 40
Pokud je tento seznam seřazen vzestupně, bude to:
10 20 30 40 50 60 70 80
Pokud je seřazeno sestupně, bude to:
80 70 60 50 40 30 20 10
Třídění vložení je třídicí algoritmus, který se používá k řazení seznamu ve vzestupném nebo sestupném pořadí. Tento článek se zabývá pouze řazením ve vzestupném pořadí. Řazení v sestupném pořadí se řídí stejnou logikou jako v tomto dokumentu. Cílem tohoto článku je vysvětlit řazení vkládání. Programování je provedeno v následujícím příkladu v C. Řazení vkládání je zde vysvětleno pomocí jednoho pole.
Algoritmus pro řazení vložení
Je uveden neseřazený seznam. Cílem je seřadit seznam vzestupně pomocí stejného seznamu. Řazení neseřazeného pole pomocí stejného pole se nazývá řazení na místě. Zde se používá indexování založené na nule. Postup je následující:
-
- Seznam se skenuje od začátku.
- Zatímco skenování probíhá, jakékoli číslo menší než u předchůdce je zaměněno za předchůdce.
- Tato výměna pokračuje v seznamu, dokud ji již není možné zaměnit.
- Když skenování dosáhne konce, třídění je dokončeno.
Vložení Seřadit Ilustrace
Při řešení časové složitosti je to nejhorší případ, který se běžně bere v úvahu. Nejhorší uspořádání pro předchozí seznam je:
80 70 60 50 40 30 20 10
Existuje osm prvků s indexy od nuly do 7.
Při indexu nula se skenování dostane na 80. Toto je jeden pohyb. Tento jediný pohyb je operace. Operace je zatím celkem jedna (jeden pohyb, žádné srovnání a žádná výměna). Výsledek je:
| 80 70 60 50 40 30 20 10
Na indexu jedna dochází k pohybu na 70. 70 je porovnáno s 80. 70 a 80 jsou prohozeny. Jeden pohyb je jedna operace. Jedno srovnání je také jedna operace. Jedna výměna je také jedna operace. Tato část poskytuje tři operace. Operace jsou zatím celkem čtyři (1 + 3 = 4). Výsledek je následující:
70 | 80 60 50 40 30 20 10
Na indexu 2 dojde k pohybu na 60. 60 je porovnáno s 80, poté jsou 60 a 80 vyměněny. 60 je porovnáno se 70, poté jsou 60 a 70 prohozeny. Jeden pohyb je jedna operace. Dvě srovnání jsou dvě operace. Dva swapy jsou dvě operace. Tato část obsahuje pět operací. Operací je zatím celkem devět (4 + 5 = 9). Výsledek je následující:
60 70 | 80 50 40 30 20 10
Na indexu tři dojde k pohybu na 50. 50 se porovná s 80, poté se vymění 50 a 80. 50 je porovnáno se 70, poté jsou 50 a 70 prohozeny. 50 se porovná s 60, pak se 50 a 60 vymění. Jeden pohyb je jedna operace. Tři srovnání jsou tři operace. Tři swapy jsou tři operace. Tato část obsahuje sedm operací. Operací je zatím celkem šestnáct (9 + 7 = 16). Výsledek je následující:
50 60 70 | 80 40 30 20 10
Na indexu 4 dojde k pohybu na 40. 40 je porovnáno s 80, poté jsou 40 a 80 prohozeny. 40 je porovnáno se 70, poté jsou 40 a 70 prohozeny. 40 je porovnáno s 60, poté jsou 40 a 60 prohozeny. 40 je porovnáno s 50, poté jsou 40 a 50 prohozeny. Jeden pohyb je jedna operace. Čtyři srovnání jsou čtyři operace. Čtyři swapy jsou čtyři operace. Tato část obsahuje devět operací. Celkem je zatím dvacet pět operací (16 + 9 = 25). Výsledek je následující:
40 50 60 70 80 | 30 20 10
U indexu 5 dojde k pohybu na 30. 30 je porovnáno s 80, poté jsou 30 a 80 prohozeny. 30 je porovnáno se 70, poté jsou 30 a 70 prohozeny. 30 je porovnáno s 60, poté jsou 30 a 60 prohozeny. 30 je porovnáno s 50, poté jsou 30 a 50 prohozeny. 30 je porovnáno se 40, poté jsou 30 a 40 prohozeny. Jeden pohyb je jedna operace. Pět srovnání je pět operací. Pět swapů je pět operací. Tato část obsahuje jedenáct operací. Celkem je zatím třicet šest operací (25 + 11 = 36). Výsledek je následující:
30 40 50 60 70 80 | 20 10
Na indexu šest dochází k pohybu na 20. 20 je porovnána s 80, poté jsou 20 a 80 vyměněny. 20 je porovnáno se 70, poté jsou 20 a 70 prohozeny. 20 se porovná s 60, pak se 20 a 60 vymění. 20 se porovná s 50, pak se 20 a 50 vymění. 20 je porovnáno se 40, poté jsou 20 a 40 prohozeny. 20 se porovná s 30, pak se 20 a 30 vymění. Jeden pohyb je jedna operace. Šest srovnání je šest operací. Šest swapů je šest operací. Tato sekce obsahuje třináct operací. Celkem je zatím 49 operací (36 + 13 = 49). Výsledek je následující:
20 30 40 50 60 70 80 | 10
Na indexu sedm dojde k pohybu na 10. 10 se porovná s 80, poté se vymění 10 a 80. 10 je porovnáno se 70, poté jsou 10 a 70 prohozeny. 10 je porovnáno s 60, poté jsou 10 a 60 prohozeny. 10 je porovnáno s 50, poté jsou 10 a 50 prohozeny. 10 je porovnáno s 30, poté jsou 10 a 40 prohozeny. 10 je porovnáno s 30, poté jsou 10 a 30 prohozeny. 10 je porovnáno s 20, poté jsou 10 a 20 prohozeny. Jeden pohyb je jedna operace. Sedm srovnání je sedm operací. Sedm swapů je sedm operací. Tato část obsahuje patnáct operací. Celkem je zatím 64 provozů (49 + 15 = 64). Výsledek je následující:
10 20 30 40 50 60 70 80 10 |
Práce je hotová! Bylo zapojeno 64 operací.
64 = 8 x 8 = 8 dva
Časová složitost pro řazení vložení
Pokud existuje n prvků k řazení pomocí řazení vložením, maximální počet možných operací by byl n2, jak bylo ukázáno dříve. Složitost doby řazení vložení je:
Na dva )
Toto používá notaci Big-O. Zápis Big-O začíná písmenem O velkým písmenem, za nímž následují závorky. Uvnitř závorek je výraz pro maximální možný počet operací.
Kódování v C
Na samém začátku skenování nemůže první prvek změnit svou polohu. Program je v podstatě následující:
#includevoid insertSort ( int A [ ] , int N ) {
pro ( int i = 0 ; i < N; i++ ) {
int j = i;
zatímco ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
int teplota = A [ j ] ; A [ j ] = A [ j- 1 ] ; A [ j- 1 ] = teplota; // vyměnit
j--;
}
}
}
Definice funkce insertionSort() používá popsaný algoritmus. Všimněte si podmínek pro smyčku while. Vhodná hlavní funkce C pro tento program je:
{
int n = 8 ;
int A [ ] = { padesáti , 60 , 30 , 10 , 80 , 70 , dvacet , 40 } ;
insertionSort ( A, n ) ;
pro ( int i = 0 ; i < n; i++ ) {
printf ( '%i' , A [ i ] ) ;
}
printf ( ' \n ' ) ;
vrátit se 0 ;
}
Závěr
Časová složitost pro řazení vložení je dána takto:
Na dva )
Čtenář možná slyšel o časové složitosti v horším případě, časové složitosti průměrného případu a časové složitosti v nejlepším případě. Tyto variace časové složitosti řazení vložení jsou popsány v dalším článku na našem webu.