Kľúčový rozdiel – zoradenie podľa vloženia a zoradenie podľa výberu
Vloženie triedenia a triedenie výberu sú dva triediace algoritmy používané na triedenie kolekcie údajov. Niekedy je potrebné usporiadať údaje v konkrétnom poradí. Algoritmy triedenia sú mechanizmy na triedenie súboru údajov. Pri triedení sú údaje usporiadané podľa číselného alebo lexikografického poradia. Ak sú údaje správne zoradené, bolo by ľahké ich rýchlejšie vyhľadávať. Ak telefónne čísla v telefónnom zozname nie sú zoradené, potom by bolo ťažké nájsť konkrétne telefónne číslo. Rovnako tak, ak slová v slovníku nie sú usporiadané v abecednom poradí, bude veľmi ťažké nájsť slová. Preto je triedenie užitočné v každodennom živote. V informatike existujú triediace algoritmy na triedenie kolekcie údajov. Dva takéto algoritmy sú triedenie vkladania a triedenie výberu. Triedenie vloženia je triediaci algoritmus, ktorý triedi pole posúvaním prvkov jeden po druhom. Triedenie výberu je triediaci algoritmus, ktorý nájde najmenší prvok v poli a vymení prvok s prvou pozíciou, potom nájde druhý najmenší prvok a vymení ho s prvkom na druhej pozícii a pokračuje v procese, kým sa nezotriedi celé pole.. Kľúčový rozdiel medzi zoradením vložením a zoradením výberu je v tom, že zoradenie vložením porovnáva dva prvky naraz, zatiaľ čo zoradenie výberu vyberie minimálny prvok z celého poľa a zoradí ho.
Čo je triedenie vloženia?
Vloženie triedenia je miestny algoritmus triedenia založený na porovnaní. Pri tejto metóde sa pole prehľadáva krok za krokom. Nezoradené položky sa presunú a vložia do zoradeného podzoznamu poľa. Algoritmus triedenia vloženia možno vysvetliť pomocou nasledujúceho príkladu.
Počiatočné pole vezmite napríklad ako 77, 33, 44, 11, 88. V tomto triediacom algoritme je prvým krokom výber aktuálneho prvku.
Aktuálny prvok je 77. Aktuálny prvok sa porovná so všetkými prvkami na ľavej strane. 77 je prvý prvok a na ľavej strane nie sú žiadne prvky. Index aktuálnej pozície je 0.
Potom sa index aktuálnej pozície zvýši o 1. Teraz je index 1 a aktuálny prvok je 33. Pri porovnaní s prvkom vľavo je menší ako 77. Potom obe tieto hodnoty sú vymenené. Teraz je 33 v indexe 0 a 77 je v indexe 1.
Pole je teraz 33, 77, 44, 11, 88.
Index sa opäť zvýši. Index je 2 a aktuálny prvok je 44. Porovnáva sa s prvkami na ľavej strane. 44 je menej ako 77. Takže tieto dve hodnoty sú zamenené. Teraz je pole 33, 44, 77, 11, 88. Je potrebné porovnať všetky prvky vľavo. Takže 44 sa porovnáva s 33. 33 je menšie ako 44. Takže tieto prvky nie je potrebné vymieňať.
Pole je teraz 33, 44, 77, 11, 88.
Index sa opäť zvýši. Index je 3 a aktuálny prvok je 11. Porovnáva sa so všetkými prvkami vľavo. 11 je menej ako 77, takže tieto dva sú vymenené. Teraz je pole 33, 44, 11, 77, 88. Pri porovnaní 11 a 44 je 11 menej ako 44. Takže tieto dva sú zamenené. Teraz sú polia 33, 11, 44, 77, 88. Opäť sa porovná 11 s 33. 11 je menej ako 33, takže tieto dve hodnoty sú zamenené.
Pole je teraz 11, 33, 44, 77, 88.
Zvýšením indexu sa index dostane na 4. Hodnota je 88. Je vyššia ako 77. Takže nie je potrebné prehadzovať. Nakoniec je zoradené pole 11, 33, 44, 77, 88.
Obrázok 01: Príklad zoradenia vloženia
Implementácia triedenia vkladania je ako je uvedené vyššie. Počiatočné pole bolo 77, 33, 44, 11, 88. Po zoradení dostane výstup 11, 33, 44, 77, 88.
Čo je triedenie výberu?
Selection sort je miestny algoritmus triedenia založený na porovnaní. Polia sú rozdelené do sekcií. Zoradená časť je na ľavom konci. Nevytriedená časť je na správnom konci. Najprv by ste mali nájsť najmenšiu hodnotu. Potom sa vymení za ľavý prvok. Teraz je tento prvok v triedenom poli. Tento proces pokračuje v posúvaní netriedenej hranice poľa z jedného prvku doprava. Algoritmus triedenia výberu možno vysvetliť pomocou nasledujúceho príkladu.
Napríklad vezmite počiatočné pole ako 77, 33, 44, 11, 88, 22. V tomto triediacom algoritme sa nájde najmenšie pole. Najmenší prvok je 11. Je zamenený s prvkom v indexe 0 poľa.
Pole je teraz 11, 33, 44, 77, 88, 22.
Najmenší prvok je v indexe 0, takže 11 je teraz zoradené. Zo zvyšku prvkov je najmenší 22. Je zamenený za indexový prvok 1st.
Pole je teraz 11, 22, 44, 77, 88, 33.
Prvky 11 a 22 sú už zoradené. Zo zvyšku je najmenšia hodnota 33. Je vymenená za indexový prvok 2nd.
Pole je teraz 11, 22, 33, 77, 88, 44.
Prvky 11, 22 a 33 sú už zoradené. Zo zvyšku je najmenšia hodnota 44. Je vymenená za indexový prvok 3rd.
Pole je teraz 11, 22, 33, 44, 88, 66.
Prvky 11, 22, 33, 44 sú už zoradené. Zostávajúce prvky sú 88 a 66. Prvok 66 je zamenený za indexový prvok 4th.
Pole je teraz 11, 22, 33, 44, 66, 88.
Je to triedené pole pomocou triediaceho algoritmu výberu.
Obrázok 02: Príklad zoradenia výberu
Implementácia triedenia vkladania je ako je uvedené vyššie. Počiatočné pole bolo 77, 33, 44, 11, 88. Po zoradení dostane výstup 11, 33, 44, 77, 88.
Aká je podobnosť medzi triedením vloženia a triedením výberu?
Tradenie vloženia aj triedenie výberu sú algoritmy triedenia
Aký je rozdiel medzi triedením vloženia a triedením výberu?
Vloženie vs. zoradenie výberu |
|
| Triedenie vkladania je triediaci algoritmus, ktorý triedi pole posúvaním prvkov jeden po druhom. | Selekčné triedenie je triediaci algoritmus, ktorý nájde najmenší prvok v poli a vymení prvok s prvou pozíciou, potom nájde druhý najmenší prvok a vymení ho za prvok na druhej pozícii a pokračuje v procese, kým celé pole je zoradené. |
| Proces | |
| Zoraďovanie vkladania je na zoradenie podzoznamu porovnaním dvoch prvkov, kým sa nezoradí celé pole. | Triedenie výberu vyberie minimálny prvok a vymení ho s prvou pozíciou, znova vyberte minimum za zvyšok a prehoďte ho na druhú pozíciu a pokračujte v tomto procese až do konca. |
| Stabilita | |
| Vloženie triedenia je stabilný triediaci algoritmus. | Zoraďovanie podľa výberu nie je stabilný algoritmus triedenia. |
Súhrn – zoradenie podľa vloženia verzus zoradenie podľa výberu
Niekedy je potrebné dáta triediť. V informatike existujú algoritmy na triedenie údajov. Tento článok diskutoval o dvoch triediacich algoritmoch, ktorými sú triedenie vkladania a triedenie výberu. Triedenie vkladania je triediaci algoritmus, ktorý triedi pole posúvaním prvkov jeden po druhom. Triedenie výberu je triediaci algoritmus, ktorý nájde najmenší prvok v poli a vymení prvok s prvou pozíciou, potom nájde druhý najmenší prvok a vymení ho s prvkom na druhej pozícii a pokračuje v procese, kým sa nezotriedi celé pole.. Rozdiel medzi triedením vložením a triedením výberu je v tom, že zoradenie vložením porovnáva dva prvky naraz, zatiaľ čo triedenie výberu vyberie minimálny prvok z celého poľa a zoradí ho.
Stiahnite si PDF zoradenie vloženia vs triedenie výberu
Verziu tohto článku si môžete stiahnuť vo formáte PDF a použiť ju na offline účely podľa citácie. Stiahnite si verziu PDF tu: Rozdiel medzi triedením vloženia a triedením výberu
