Obsah[Skryť][Šou]
Informatika je o pochopení zložitosti algoritmov a dátových štruktúr.
Máte zoznam položiek, ktoré je potrebné triediť, ale nemáte čas ani zdroje na použitie zložitejšieho triediaceho algoritmu.
Triedenie vkladania je jedným z najjednoduchších triediacich algoritmov, ale pri veľkých zoznamoch môže byť pomalé.
Jednoduchá implementácia a pochopenie urobili z tejto metódy obľúbenú medzi programátormi. Je ideálny pre malé zoznamy alebo keď potrebujete rýchle riešenie.
V tomto blogovom príspevku sa pozrieme na časovú náročnosť triedenia vkladania. Tento algoritmus sa používa na triedenie polí a má runtime O(n2). To znamená, že časová zložitosť rastie s veľkosťou poľa.
Tento algoritmus však môže byť často rýchlejší ako iné triediace algoritmy, ako napríklad quicksort.
Pozrime sa bližšie na to, ako funguje triedenie vkladania!
Čo je algoritmus triedenia vkladania?
Zoradenie vkladania po jednom prvku generuje zoraditeľné pole, ktoré sa často nazýva zoznam.
Triedenie sa napríklad používa v zložitých počítačových programoch, ako sú kompilátory, kde je poradie tokenov dôležité pre interpretáciu programu.
Ako funguje triedenie vkladania?
Keď na triedenie poľa použijeme triedenie vložením, algoritmus začína nájdením najmenšej položky v zozname a jej vložením na správnu pozíciu.
Potom nájde ďalšiu najmenšiu položku a vloží ju na správnu pozíciu atď.
Algoritmus funguje tak, že prechádza zoznamom a porovnáva každú položku s tou, ktorá je pred ňou.
Ak sú položky v nesprávnom poradí, algoritmus ich vymení. Potom skontroluje, či je zoznam zoradený, a ak áno, algoritmus skončí.
V praxi sa triedenie vkladania často implementuje pomocou niekoľkých riadkov kódu, čo z neho robí populárnu voľbu na triedenie malých polí. Pri použití tohto algoritmu je však potrebné zvážiť časovú zložitosť.
Príklad:
Tu je príklad toho, ako funguje triedenie vkladania. Použijeme nasledujúce pole:
1, 2, 3, 4, 5, 6
Algoritmus začína nájdením najmenšej položky v zozname, ktorou je 1. Potom ju vloží na správnu pozíciu, prvú pozíciu. Potom nájde ďalšiu najmenšiu položku, ktorou je 2. Vloží ju na správnu pozíciu, ktorou je druhá pozícia.
Potom nájde ďalšiu najmenšiu položku, ktorou je 3. Vloží ju na správnu pozíciu, ktorou je tretia pozícia.
Potom nájde ďalšiu najmenšiu položku, ktorou je 4. Vloží ju na správnu pozíciu, ktorou je štvrtá pozícia atď. Zoznam je teraz zoradený!
Z príkladu vidíme, že algoritmus vykoná šesť porovnaní a vymení, aby zoradil zoznam. Je to preto, že trvá n2 porovnania a výmeny na zoradenie zoznamu n položiek. V tomto prípade n=6.
Ako zlepšiť časovú zložitosť triedenia vkladania?
Zatiaľ čo triedenie vkladania má dobu spustenia O(n2), možno ho vylepšiť použitím lepšieho triediaceho algoritmu, ako je quicksort.
Quicksort má runtime O(n log n), ktoré je oveľa rýchlejšie ako O(n2).
V niektorých prípadoch však môže byť triedenie vkladov rýchlejšie ako rýchle triedenie.
Napríklad, ak je zoznam už v poriadku, triedenie vložením zaberie menej času ako rýchle triedenie.
V praxi sa triedenie vkladania často implementuje pomocou niekoľkých riadkov kódu, čo z neho robí populárnu voľbu na triedenie malých polí.
Pri použití tohto algoritmu je však potrebné zvážiť časovú zložitosť.
Časová zložitosť
Zložitosť najhoršieho prípadu O(č2):
Časová zložitosť sa zvyšuje s veľkosťou poľa. Trvá n2 porovnania a výmeny na zoradenie zoznamu n položiek.
Napríklad, ak máme pole veľkosti 1000 1,000,000, algoritmus vykoná XNUMX XNUMX XNUMX porovnaní a zámien, aby pole zoradil.
Zložitosť najlepšieho prípadu O(n):
Časová zložitosť je rovnaká ako veľkosť vstupného poľa. ja
t vyžaduje n porovnaní a zámien na zoradenie zoznamu n položiek. Uvažujme napríklad pole veľkosti 5. Algoritmus vykoná päť porovnaní a vymení pole, aby zoradil pole.
Priemerná zložitosť prípadu O(č2):
Časová zložitosť je v tomto prípade medzi zložitosťou najhoršieho a najlepšieho prípadu.
Trvá n2 porovnania a výmeny na zoradenie zoznamu n položiek.
Vloženie triedenia je teda stabilný triediaci algoritmus.
Prečo je zoradenie vkladania stabilné?
Zoradenie vloženia je stabilné, pretože zachováva poradie rovnakých prvkov vo vstupnom poli.
To je dôležité pre mnohé aplikácie, ako je vyhľadávanie údajov alebo finančná analýza. Ak máme napríklad dva zoznamy čísel a chceme ich porovnať, musíme sa uistiť, že poradie prvkov je zachované.
Ak zoznamy nie sú zoradené, nebudeme ich presne porovnávať.
Nechaj odpoveď