Klíčový rozdíl – řazení vložení vs. řazení výběru
Třídění vložení a řazení výběru jsou dva třídicí algoritmy používané k řazení kolekce dat. Někdy je potřeba uspořádat data v konkrétním pořadí. Třídicí algoritmy jsou mechanismy pro třídění sady dat. Při řazení jsou data uspořádána podle číselného nebo lexikografického pořadí. Pokud jsou data setříděna správně, pak by bylo snadné vyhledávat data rychleji. Pokud nejsou telefonní čísla v telefonním seznamu seřazená, pak by bylo těžké najít konkrétní telefonní číslo. Stejně tak, pokud by slova ve slovníku nebyla uspořádána v abecedním pořadí, bylo by velmi těžké najít slova. Proto je třídění užitečné v každodenním životě. V informatice existují třídicí algoritmy pro třídění kolekce dat. Dva takové algoritmy jsou řazení vložení a řazení výběru. Vložení řazení je třídicí algoritmus, který třídí pole přesouváním prvků jeden po druhém. Třídění výběru je třídicí algoritmus, který najde nejmenší prvek v poli a vymění prvek s první pozicí, poté najde druhý nejmenší prvek a vymění ho s prvkem na druhé pozici a pokračuje v procesu, dokud není setříděno celé pole.. Klíčový rozdíl mezi řazením vložení a řazením výběru je v tom, že řazení vložení porovnává dva prvky najednou, zatímco řazení výběru vybere minimální prvek z celého pole a seřadí ho.
Co je řazení vložení?
Řazení vložením je třídicí algoritmus založený na porovnávání. Při této metodě se pole prohledává krok za krokem. Netříděné položky se přesunou a vloží do seřazeného podseznamu pole. Algoritmus řazení vložení lze vysvětlit pomocí následujícího příkladu.
Například vezměte počáteční pole jako 77, 33, 44, 11, 88. V tomto třídicím algoritmu je prvním krokem výběr aktuálního prvku.
Aktuální prvek je 77. Aktuální prvek je porovnán se všemi prvky na levé straně. 77 je prvním prvkem a na levé straně nejsou žádné prvky. Index aktuální pozice je 0.
Potom se index aktuální pozice zvýší o 1. Nyní je index 1 a aktuální prvek je 33. Při porovnání s prvkem vlevo je menší než 77. Potom obě tyto hodnoty jsou vyměněny. Nyní je 33 v indexu 0 a 77 je v indexu 1.
Pole je nyní 33, 77, 44, 11, 88.
Index se opět zvýší. Index je 2 a aktuální prvek je 44. Porovnává se s prvky na levé straně. 44 je menší než 77. Tyto dvě hodnoty jsou tedy prohozeny. Nyní je pole 33, 44, 77, 11, 88. Je nutné porovnat všechny prvky vlevo.44 je tedy porovnáno s 33. 33 je menší než 44. Tyto prvky tedy není třeba vyměňovat.
Pole je nyní 33, 44, 77, 11, 88.
Index se opět zvýší. Index je 3 a aktuální prvek je 11. Porovná se se všemi prvky vlevo. 11 je méně než 77, takže tyto dva jsou prohozeny. Nyní je pole 33, 44, 11, 77, 88. Při porovnání 11 a 44 je 11 menší než 44. Takže tyto dva jsou prohozeny. Nyní jsou pole 33, 11, 44, 77, 88. Opět je 11 porovnáno s 33. 11 je menší než 33, takže tyto dvě hodnoty jsou prohozeny.
Pole je nyní 11, 33, 44, 77, 88.
Zvýšení indexu způsobí, že index bude 4. Hodnota je 88. Je vyšší než 77. Není tedy potřeba swapování. Nakonec je seřazené pole 11, 33, 44, 77, 88.
Obrázek 01: Příklad řazení vložení
Implementace řazení vkládání je jako výše. Počáteční pole bylo 77, 33, 44, 11, 88. Po seřazení dává výstup 11, 33, 44, 77, 88.
Co je třídění výběru?
Selection sort je místní třídicí algoritmus založený na porovnání. Pole jsou rozdělena do sekcí. Seřazená část je na levém konci. Netříděná část je na pravém konci. Nejprve by měla být nalezena nejmenší hodnota. Poté se prohodí s levým prvkem. Nyní je tento prvek v seřazeném poli. Tento proces pokračuje v přesouvání netříděné hranice pole z jednoho prvku doprava. Algoritmus řazení výběru lze vysvětlit pomocí následujícího příkladu.
Například vezměte počáteční pole jako 77, 33, 44, 11, 88, 22. V tomto třídicím algoritmu se najde nejmenší pole. Nejmenší prvek je 11. Je prohozen s prvkem v indexu 0 pole.
Pole je nyní 11, 33, 44, 77, 88, 22.
Nejmenší prvek je v indexu 0, takže 11 je nyní seřazeno. Ze zbývajících prvků je nejmenší 22. Je zaměněn za indexový prvek 1st.
Pole je nyní 11, 22, 44, 77, 88, 33.
Prvky 11 a 22 jsou již seřazeny. Ze zbytku je nejmenší hodnota 33. Je zaměněna za indexový prvek 2nd.
Pole je nyní 11, 22, 33, 77, 88, 44.
Prvky 11, 22 a 33 jsou již seřazeny. Ze zbytku je nejmenší hodnota 44. Je zaměněna za indexový prvek 3rd.
Pole je nyní 11, 22, 33, 44, 88, 66.
Prvky 11, 22, 33, 44 jsou již seřazeny. Zbývající prvky jsou 88 a 66. Prvek 66 je zaměněn za indexový prvek 4th.
Pole je nyní 11, 22, 33, 44, 66, 88.
Je to seřazené pole pomocí algoritmu řazení výběru.
Obrázek 02: Příklad řazení výběru
Implementace řazení vkládání je jako výše. Počáteční pole bylo 77, 33, 44, 11, 88. Po seřazení dává výstup 11, 33, 44, 77, 88.
Jaká je podobnost mezi řazením vložení a řazením výběru?
Řazení vložení i řazení výběru jsou algoritmy řazení
Jaký je rozdíl mezi řazením vložení a řazením výběru?
Řazení vložení vs řazení výběru |
|
| Řazení vložení je třídicí algoritmus, který třídí pole posouváním prvků jeden po druhém. | Seřazení výběru je třídicí algoritmus, který najde nejmenší prvek v poli a vymění prvek s první pozicí, pak najde druhý nejmenší prvek a vymění ho s prvkem na druhé pozici a pokračuje v procesu, dokud celé pole je seřazeny. |
| Proces | |
| Třídění vkládáním je seřadit podseznam porovnáním dvou prvků, dokud není seřazeno celé pole. | Seřazení výběru vybere minimální prvek a zamění ho s první pozicí, znovu vyberte minimum pro zbytek a prohoďte ho na druhou pozici a pokračujte v tomto procesu až do konce. |
| Stabilita | |
| Vložení řazení je stabilní třídicí algoritmus. | Řazení výběru není stabilní algoritmus řazení. |
Shrnutí – řazení podle vložení vs. řazení podle výběru
Někdy je potřeba data třídit. V informatice existují algoritmy pro třídění dat. Tento článek pojednává o dvou třídicích algoritmech, kterými jsou řazení vložení a řazení výběru. Vložení řazení je třídicí algoritmus, který třídí pole přesouváním prvků jeden po druhém. Třídění výběru je třídicí algoritmus, který najde nejmenší prvek v poli a vymění prvek s první pozicí, poté najde druhý nejmenší prvek a vymění ho s prvkem na druhé pozici a pokračuje v procesu, dokud není setříděno celé pole.. Rozdíl mezi řazením vložení a řazením výběru je ten, že řazení vložení porovnává dva prvky najednou, zatímco řazení výběru vybere minimální prvek z celého pole a seřadí ho.
Stáhněte si PDF s řazením vložení vs. řazením výběru
Verzi tohoto článku si můžete stáhnout ve formátu PDF a použít ji pro offline účely podle citace. Stáhněte si prosím verzi PDF zde: Rozdíl mezi řazením vložení a řazením výběru
