Odporúčaná, 2019

Redakcia Choice

Rozdiel medzi triedením vloženia a triedením výberu

Typ triedenia a typ výberu sú techniky, ktoré sa používajú na triedenie údajov. Veľký druh triedenia a triedenie výberu je možné rozlišovať podľa metódy, ktorú používajú na triedenie údajov. Trieda vloženia vkladá hodnoty do súboru s predvoľbou na zoradenie množiny hodnôt. Na druhú stranu výberové číslo nájde minimálny počet zo zoznamu a usporiada ho v nejakom poradí.

Triedenie je základná operácia, pri ktorej sú prvky poľa usporiadané v určitom špecifickom poradí, aby sa zvýšila jeho prehľadávateľnosť. Jednoducho povedané, údaje sú roztriedené tak, aby bolo možné ich jednoducho vyhľadávať.

Porovnávacia tabuľka

Základ pre porovnanieTriedenie vloženiaTriedenie výberu
základné
Údaje sa zoradia vložením údajov do existujúceho triedeného súboru.Údaje sú zoradené výberom a umiestnením nasledujúcich prvkov do triedenej polohy.
príroda
stabilnýnestály
Postup, ktorý treba dodržiavať
Prvky sú známe vopred, kým sa vyhľadávajú miesta na ich umiestnenie.Miesto bolo predtým známe pri vyhľadávaní prvkov.
Okamžité údaje
Inserčný sortiment je technológia živého triedenia, ktorá dokáže riešiť okamžité dáta.Nemôže sa zaoberať okamžitými údajmi, musí byť prítomná na začiatku.
Najlepšia zložitosť prípadovO (n)O (n2)

Definícia triedenia vloženia

Inserčné triedenie funguje vložením množiny hodnôt do existujúceho triedeného súboru. Vytvára triedené pole vložením jedného prvku naraz. Tento proces pokračuje, kým celé pole nie je usporiadané v určitom poradí. Primárnym konceptom za triedenie vloženia je vloženie každej položky do jej príslušného miesta v konečnom zozname. Metóda triedenia vloženia ukladá efektívne množstvo pamäte.

Práca s triedou vloženia

  • Používa dve sady polí, v ktorých sa ukladajú triedené údaje a iné na netriedené údaje.
  • Algoritmus triedenia funguje dovtedy, kým nie sú prvky v netriedenej množine.
  • Predpokladajme, že v poli sú prvky "n". Spočiatku prvok s indexom 0 (LB = 0) existuje v triedenej množine. Zostávajúce prvky sú v nerozdelenom oddiele zoznamu.
  • Prvý prvok netriedenej časti má index poľa 1 (ak LB = 0).
  • Po každej iterácii si vyberie prvý prvok nerozdeleného oddielu a vloží ho do správneho miesta v triedenej množine.

Výhody zoraďovania

  • Ľahko implementované a veľmi efektívne pri použití s ​​malými súbormi údajov.
  • Dodatočná pamäťová požiadavka na triedenie vkladania je menšia (tj O (1)).
  • Predpokladá sa, že je to technológia živého triedenia, pretože zoznam je možné zoradiť podľa nových prvkov.
  • Je rýchlejší ako iné triediace algoritmy.

Príklad:

Definícia triedenia výberu

Sortiment triedenia vykoná triedenie vyhľadaním čísla minimálnej hodnoty a umiestnením do prvej alebo poslednej pozície podľa poradia (vzostupne alebo zostupne). Proces vyhľadávania minimálneho kľúča a jeho umiestnenie do správnej polohy pokračuje, kým všetky prvky nebudú umiestnené v správnej polohe.

Práca s triedením výberu

  • Predpokladajme, že pole ARR s prvkami N v pamäti.
  • Pri prvom prechode sa hľadá najmenší kľúč spolu s jeho pozíciou, potom sa ARR [POS] vymenia s ARR [0]. Preto je ARR [0] zoradený.
  • Pri druhom prechode sa opäť určuje poloha najmenšej hodnoty v subarray N-1 prvkov. Vymeňte ARR [POS] s ARR [1].
  • V priechode N-1 sa vykoná rovnaký proces na zoradenie počtu N prvkov.

Príklad:

Kľúčové rozdiely medzi triedením vkladania a triedením výberu

  1. Trieda vloženia zvyčajne vykonáva operáciu vloženia. Na druhej strane selekčné triedenie uskutočňuje výber a umiestnenie požadovaných prvkov.
  2. Typ insertion sa považuje za stabilný, zatiaľ čo selekčný sortiment nie je stabilný algoritmus.
  3. V algoritme triedenia vloženia sú prvky známe. Na rozdiel od toho výber výberu obsahuje miesto vopred.
  4. Inserčný sortiment je metóda živého triedenia, pri ktorej prichádzajúce prvky sú okamžite roztriedené v zozname, zatiaľ čo triedenie výberu nemôže fungovať správne s okamžitými údajmi.
  5. Typ vkladania má v najlepšom prípade O (n) bežiaci čas. Naopak, najlepší časový priebeh zložitosti tried výberu je O (n2).

Zložitosť vloženia

Najlepšia zložitosť prípadu vkladania je O (n) krát, tj keď je pole predtým zoradené. Rovnako, ak je pole zoradené v opačnom poradí, prvý prvok neporiadeného poľa sa má porovnať s každým prvkom v zoradenej množine. Takže v najhoršom prípade je doba chodu Insertion sort kvadratická, tj O (n2) . V priemernom prípade musí tiež urobiť minimálne (k-1) / 2 porovnanie. Preto má priemerný prípad aj kvadratický čas chodu O (n2).

Zložitosť triedenia výberu

Ako funguje selekcia, triedenie nezávisí na pôvodnom poradí prvkov v poli, takže nie je veľký rozdiel medzi najlepšími a najhoršími zložitosťami selekčného triedenia.

Zoradenie výberu vyberie prvok minimálnej hodnoty, v procese výberu sa skenuje celý počet 'n' prvkov; preto sa pri prvom prechode urobia n-1 porovnania. Potom sa prvky vymieňajú. Podobne v druhom priechode nájdeme aj druhý najmenší prvok, ktorý požadujeme skenovanie zvyškov n-1 prvkov a proces pokračuje až do triedenia celého poľa.

Preto je zložitosť výberu času O (n2) .
= (n-1) + (n-2) + ......... .. + 2 + 1
= n (n-1) / 2 = 0 (n2)

záver

Medzi obidvoma triediacim algoritmom je druh vkladania rýchly, účinný, stabilný, zatiaľ čo triedenie výberu funguje efektívne iba vtedy, keď je zahrnutá malá sada prvkov alebo je zoznam čiastočne predtým zoradený. Počet porovnaní vykonaných selekčným triedením je väčší ako vykonané pohyby, zatiaľ čo pri vložení zoradiť počet premiestnení alebo výmeny prvku je väčší ako porovnanie.

Top