[Powered by Google Translate] [Vkladanie Triediť] [Tommy MacWilliam] [Harvard University] [To je CS50.TV] Poďme sa pozrieť na vloženie radiť, algoritmus pre prijatie zoznamu čísel a triedenie. Algoritmus, pamätajte, je jednoducho krok-za-krokom postup pre dosiahnutie úlohy. Základnou myšlienkou vloženie radiť, je rozdeliť na náš zoznam na dve časti, sú zoradené časť a netriedené časť. 

Na každom kroku algoritmu, je presunutá číslo z netriedeného časti do triedeného časti až nakoniec je zoradená celý zoznam. Tu je zoznam šiestich netriedených čísel - 23, 42, 4, 16, 8, a 15. Vzhľadom k tomu, že tieto čísla nie sú všetko vo vzostupnom poradí, to netriedený oni. Vzhľadom k tomu, sme sa začali radenie doteraz, budeme uvažovať o všetkých šiestich prvkov našej netriedeného časť. 

Akonáhle začneme triedenie, dáme tieto zoradené čísla vľavo od nich. Takže, poďme začať s 23, prvý prvok v našom zozname. Nemáme žiadne prvky v našej zoradené časti ešte, takže sa poďme jednoducho považujú 23 za začiatok a koniec našej triedeného časti. Teraz, naše zoradené časť má jedno číslo, 23, a naše netriedeného časť má týchto päť čísel. Poďme sa teraz vložiť ďalšie číslo v našom netriedeného časti, 42, do triedeného časti. 

Ak chcete tak urobiť, budeme musieť porovnať 42 k 23 - jediný prvok v našom zoradené časti tak ďaleko. Štyridsaťdva je väčší ako 23, takže sa môže jednoducho pripojiť 42 až do konca z triedeného časti zoznamu. Výborne! Teraz náš zoradené časť má dva prvky, a naše rôzne časť má štyri prvky. Takže, poďme sa teraz presunúť do 4, ďalší prvok v netriedeného časti. Tak by kde sa tento umiestni do triedeného časti? 

Pamätajte si, že chceme umiestniť toto číslo v zoradené poradí takže naše zoradené časť zostáva správne zoradené za všetkých okolností. Ak umiestnime 4 na pravej strane 42, potom sa náš zoznam bude mimo prevádzky. Takže, poďme pokračovať v pohybe sprava doľava v našom druhu porciu. Ako sme sa presťahovať, poďme posunúť každé číslo nadol na miesto, aby sa priestor pre nové číslo. Dobre, 4 je tiež menej ako 23, takže nemôžeme umiestniť ani tu. Poďme sa 23 vpravo o jedno miesto. 

To znamená, že by sme chceli umiestniť 4 do prvého slotu v zoradené časti. Všimnite si, ako tento priestor v zozname bola už prázdna, pretože sme boli pohybuje zoradené prvky dole, ako sme sa stretol s nimi. Dobrá. Takže, sme v polovici cesty. Poďme pokračovať v našej algoritmus vložením 16 do triedeného časti. Šestnásť je menší ako 42, takže sa poďme posunúť 42 na pravej strane. Šestnásť je tiež menej ako 23, takže sa poďme tiež posunúť tento prvok. 

Teraz, 16 je väčší ako 4. Takže to vyzerá, že by sme chceli vložiť 16 medzi 4 a 23. Pri pohybe cez zoradené časti zoznamu sprava doľava, 4 je prvé číslo sme vidieť, že je menšie, než je počet snažíme vložiť. Tak, teraz môžeme vložiť 16 do tohto prázdneho slotu, ktoré, pamätajte, sme vytvorili pohybliv prvky v radenia časti nad ako sme sa stretli je. 

Dobrá. Teraz, máme štyri zoradené prvky a dve netriedené prvky. Takže, poďme presunúť 8 do triedeného časti. Osem je menší ako 42. Osem je menší ako 23. A 8 je menší ako 16. Ale 8 je väčšia ako 4. Takže by sme chceli vložiť 8 medzi 4 a 16. A teraz máme len jednu väčšiu zostáva prvok k radeniu - The 15. Pätnásť je nižší ako 42, Pätnásť je menší ako 23. A 15 je menší ako 16. Ale 15 je väčší ako 8. 

Takže, tu je miesto, kde chceme, aby sa naše konečné vloženie. A sme hotoví. Nemáme žiadne ďalšie prvky v netriedeného časti, a naše zoradené časť je v správnom poradí. Čísla sú zoradené od najmenšej k najväčšej. Takže, poďme sa pozrieť na niektoré pseudokódu, ktorý popisuje kroky, sme práve vykonali. 

Na riadku 1, môžeme vidieť, že budeme musieť iteráciu každý prvok v zozname okrem prvej, bude od prvého prvku v netriedeného časti jednoducho sa prvý prvok v triedenom časti. Na riadkoch 2 a 3, sme sledovaní nášho súčasného miesta v netriedeného časti. Element reprezentuje číslo v súčasnej dobe pohybuje do triedeného časti, a j reprezentuje náš index do netriedeného časti. 

Na riadku 4, sme iterácie sú zoradené časti sprava doľava. Chceme zastaviť iterácie, akonáhle prvku na ľavej strane našej súčasnej pozície je menšia ako prvok sa snažíme vložiť. Na riadku 5, sme presúva každý prvok my sa stretneme o jedno miesto vpravo. Tak, budeme mať voľný priestor pre vloženie do kedy nájdeme prvý prvok menej ako prvku Sťahujeme. Na riadku 6, sme aktualizáciu nášho počítadla naďalej pohybovať doľava cez zoradené časť. A konečne, na riadku 7, sme vkladanie prvku do triedeného časti zoznamu. 

Vieme, že je to v poriadku vložiť do polohy j, preto, že sme už presťahovali prvok, ktorý býval tam jedno miesto vpravo. Pamätajte si, že ideme cez zoradené časť sprava doľava, ale ideme cez netriedeného časť zľava doprava. Dobrá. Poďme sa teraz pozrieť na to, ako dlho beží, že algoritmus sa. Ukážeme si klásť otázku, ako dlho to trvá, než to algoritmus bežať v najhoršom prípade. Pripomeňme si, že zastupujeme tento bežiaci čas s Big O notácie. Pokiaľ ich chcete zoradiť náš zoznam, museli sme iteráciu prvky v netriedeného časti, a pre každý z týchto prvkov, prípadne cez všetky prvky v usporiadanej časti. Intuitívne, to znie ako O (n ^ 2) prevádzky. 

Pri pohľade na našom pseudokódu, máme slučku vnorené vo vnútri inej slučky, , Ktorá napokon znie ako O (n ^ 2) prevádzky. Avšak, sú zoradené časť zoznamu neobsahovala celý zoznam až do samého konca. Napriek tomu by sme mohli potenciálne vložiť nový prvok na samom začiatku triedeného časti na každej iterácii algoritmu, čo znamená, že by sme sa pozrieť na každý prvok v súčasnej dobe v triedenom časti. Takže, to znamená, že by mohli vytvoriť jednu porovnaní pre druhý prvok, dve porovnaní na tretí prvok, a tak ďalej. Takže, celkový počet krokov je súčet celých čísel od 1 do dĺžky zoznamu mínus 1. Môžeme reprezentovať to s sumácia. 

Nebudeme zachádzať do summations tu, ale ukazuje sa, že toto zhrnutie je rovná n (n - 1) v priebehu 2, ktorý je ekvivalentný n ^ 2/2 - n / 2. Keď sa hovorí o asymptotickej behu, tento n ^ 2 termín bude ovládať tento n termín. Takže, vloženie sort Big O (n ^ 2). Čo keď sme bežali vloženie Radiť už triedenom zozname. V tomto prípade by sme jednoducho vybudovať zoradená časť zľava doprava. Takže, budeme potrebovať len na poradie krokov n 

To znamená, že vkladanie spôsob má najlepšie prípadu výkon n, ktoré predstavujú s Ω (n). A to je pre vloženie radiť, len jeden z mnohých algoritmov môžeme použiť na zoradenie zoznamu. Moje meno je Tommy, a to je CS50. [CS50.TV] Oh, si jednoducho nemôže prestať, že akonáhle začne. Oh, sme urobili - >> Boom!