Třídění je základní operace, ve které jsou prvky pole uspořádány v určitém konkrétním pořadí, aby se zvýšila jeho prohledatelnost. Jednoduchými slovy se data třídí tak, aby se dala snadno vyhledávat.
Srovnávací graf
| Základ pro srovnání | Druh vložení | Výběr Seřadit |
|---|---|---|
| Základní | Data jsou tříděna vložením dat do existujícího tříděného souboru. | Data jsou tříděna výběrem a umístěním po sobě následujících prvků do tříděného umístění. |
| Příroda | Stabilní | Nestabilní |
| Proces, který má být dodržen | Prvky jsou předem známy, zatímco je umístění vyhledáváno. | Místo je dříve známé, zatímco prvky jsou prohledávány. |
| Okamžitá data | Druh vkládání je živá třídicí technika, která dokáže řešit okamžitá data. | Nemůže řešit okamžitá data, musí být přítomna na začátku. |
| Nejlepší případ složitosti | Na) | O (n 2 ) |
Definice typu vložení
Třídění vkládání funguje tak, že se do existujícího tříděného souboru vloží sada hodnot. Sestavuje seřazené pole vložením jednoho prvku najednou. Tento proces pokračuje, dokud není celé pole tříděno v určitém pořadí. Primárním konceptem za vkládání je vložení každé položky do příslušného místa v konečném seznamu. Metoda vkládání ukládá efektivní množství paměti.
Práce typu vkládání
- Používá dvě sady polí, kde se ukládají tříděná data a další na netříděná data.
- Algoritmus třídění funguje, dokud nejsou prvky v netříděné sadě.
- Předpokládejme, že v poli jsou „n“ číselné prvky. Zpočátku prvek s indexem 0 (LB = 0) existuje v tříděné sadě. Zbývající prvky jsou v netříděném oddílu seznamu.
- První prvek netříděné části má index pole 1 (Pokud LB = 0).
- Po každé iteraci vybere první prvek netříděného oddílu a vloží jej na správné místo v tříděném souboru.
Výhody druhu vkládání
- Snadná implementace a velmi efektivní při použití s malými soubory dat.
- Požadavek přídavného paměťového prostoru pro vkládání je menší (tj. O (1)).
- To je považováno za živou třídicí techniku, protože seznam může být tříděn jak nové elementy jsou přijaty.
- Je rychlejší než jiné třídicí algoritmy.
Příklad:
Definice třídění výběru
Výběr se provádí třídění podle čísla minimální hodnoty a jeho umístění do první nebo poslední pozice podle pořadí (vzestupně nebo sestupně). Proces hledání minimálního klíče a jeho umístění do správné polohy pokračuje, dokud nejsou všechny prvky umístěny na správné pozici.
Práce s výběrem Výběr
- Předpokládejme, že pole ARR s prvky N v paměti.
- V prvním průchodu je nejmenší klíč prohledáván spolu s jeho pozicí, pak je ARR [POS] zaměněn za ARR [0]. ARR [0] je proto seřazen.
- Ve druhém průchodu se opět určuje poloha nejmenší hodnoty v dílčím poli prvků N-1. Výměna ARR [POS] s ARR [1].
- V průchodu N-1 se provádí stejný proces pro třídění N počtu prvků.
Příklad:
Rozdíly klíče mezi řadou vložení a výběrem
- Způsob vkládání obvykle provádí operaci vkládání. Výběrový druh naopak provádí výběr a umístění požadovaných prvků.
- Říká se, že vkládání je stabilní, zatímco výběr není stabilní algoritmus.
- V algoritmu vkládání jsou prvky dříve známy. Oproti tomu výběr obsahuje předem dané místo.
- Druh vkládání je technika živého třídění, kde jsou příchozí prvky okamžitě seřazeny v seznamu, zatímco výběrový typ nemůže s okamžitými daty dobře fungovat.
- Druh vložení má v nejlepším případě dobu běhu O (n). Oproti tomu je nejlepším případem složitosti běhu výběru typu O (n2).
Složitost vkládání
Nejlepším případem složitosti vkládání je doba O (n), tj. Když je pole dříve tříděno. Stejným způsobem, když je pole tříděno v opačném pořadí, musí být první prvek netříděného pole porovnán s každým prvkem v tříděné sadě. V nejhorším případě je tedy doba běhu typu vložení kvadratická, tj. O (n2) . V průměrném případě musí také provést minimální srovnání (k-1) / 2. Průměrný případ má tedy také kvadratickou dobu chodu O (n2).
Složitost výběrového třídění
Vzhledem k tomu, že se jedná o výběr výběru, řazení nezávisí na původním pořadí prvků v poli, takže není velký rozdíl mezi nejvhodnějším a nejhorším případem složitosti výběru.
Výběrový výběr vybere prvek minimální hodnoty, ve výběrovém procesu se skenují všechny 'n' počet prvků; Porovnání n-1 se tedy provádí v prvním průchodu. Potom jsou prvky zaměněny. Podobně v druhém průchodu také k nalezení druhého nejmenšího elementu vyžadujeme skenování zbytkových elementů n-1 a proces pokračuje až do úplného řazení celého pole.
Komplexní doba běhu výběru tedy je O (n2) .
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
Závěr
U obou třídicích algoritmů je způsob vkládání rychlý, účinný a stabilní, zatímco výběrový výběr funguje efektivně pouze tehdy, když je zapojen malý soubor prvků nebo je seznam částečně tříděn. Počet srovnávání provedených výběrovým tříděním je větší než pohyby prováděné, zatímco při vkládání je počet, kolikrát je prvek přemístěn nebo vyměněn, větší než provedená srovnání.
