[Powered by Google Translate] Tommy: Poďme sa pozrieť na výber druhu, algoritmus pre prijatie zoznamu čísel a triedenie. Algoritmus, pamätajte, je jednoducho krok-za-krokom Postup pre dosiahnutie úlohy. Základnou myšlienkou výberu druhu je rozdeliť náš zoznam na dve časti - sú zoradené časť a netriedené časť. Na každom kroku algoritmu, je číslo presunutá zo netriedeného časť do triedeného časti až nakoniec Celý zoznam je zoradený. Takže tu je zoznam šiestich čísel - 23, 42, 4, 16, 8, a 15. Práve teraz celý zoznam sa považuje za netriedený. Aj keď počet ako 16 už môže byť v jeho správne zaradenie, náš algoritmus nemá spôsob, ako zistiť, že do Celý zoznam je zoradený. Takže budeme považovať každé číslo má byť netriedené, kým triedime to sami. Vieme, že chceme, aby zoznam, ktorý bude vo vzostupnom poradí. Takže budeme chcieť vybudovať zoradená časť nášho zoznamu zľava doprava, najmenšie k najväčšej. K tomu, budeme musieť nájsť minimálne zmiešaný prvok a dať na konci triedeného časti. Vzhľadom k tomu, tento zoznam nie je zoradený, jediný spôsob, ako to urobiť, je pozrieť sa na každý prvok v netriedeného časti, spomenul , Ktorá zložka je najnižšia a porovnávanie každý prvok k tomu. Takže budeme sa pozrieť na prvý 23. Toto je prvý prvok sme videli, takže budeme pamätať to ako minimum. Ďalej sa pozrieme na 42. 42 je väčší ako 23, takže 23 je ešte minimálne. Ďalšia je 4, čo je menej ako 23, takže budeme pamätať 4 ako nový minimum. Ďalej je 16, ktorý je väčší ako 4, takže 4 je stále minimálne. 8 je väčší ako 4 a 15, je väčší ako 4, takže 4 musí byť najmenšie netriedeného element. Takže aj keď ako ľudia môžeme okamžite vidieť, že 4 je minimálny prvok, náš algoritmus potrebuje pozrieť na každý netriedený element, aj potom, čo sme našli 4 - minimálny prvok. Takže teraz, že sme našli minimálne prvok, 4, budeme chcieť pohybovať do triedeného časti zoznamu. Vzhľadom k tomu, je prvý krok, to znamená, že chceme dať 4 na začiatok zoznamu. V súčasnej dobe je 23 na začiatku zoznamu, tak poďme vymeniť 4 a 23. Takže teraz náš zoznam vyzerá takto. Je známe, že 4 musí byť v konečnej polohe, pretože je to ako najmenší prvok a prvok na začiatku zoznamu. Takže to znamená, že sme sa nikdy potrebovať presunúť znova. Takže poďme zopakovať tento proces pridať ďalší prvok do zoradené časť zoznamu. Vieme, že nepotrebujeme sa pozrieť na 4, pretože je to už je zoradený. Takže môžeme začať na 42, čo budeme pamätať ako minimálny prvok. Takže nabudúce sa pozrieme na 23, čo je menej ako 42, takže sme pamätať 23 je nové minimálne. Ďalej vidíme 16, ktorý je nižší ako 23, tak 16 je nová minimum. Teraz sa pozrieme na 8, čo je menej ako 16, tak 8 je nová minimum. A konečne 8 je menší ako 15, takže vieme, že 8 je minimálna netriedeného element. Takže to znamená, že by sme mali pripojiť 8 do zoradená časť zoznamu. Práve teraz 4 je jediným zoradená prvok, a tak chceme umiestniť 8 vedľa 4. Vzhľadom k tomu, 42 je prvý prvok v netriedeného časti Zoznam, budeme chcieť vymeniť 42 a 8. Takže teraz náš zoznam vyzerá takto. 4 a 8 predstavujú zoradená časť zoznamu, a Zvyšné čísla predstavujú netriedeného časť zoznamu. Takže poďme pokračovať s ďalšie iterácie. Začneme s 23 tentoraz, pretože nepotrebujeme sa pozerať na je 4 a 8 už preto, že som už zoradené. 16 je nižší ako 23, takže sa budeme pamätať 16 ako nové minimum. 16 je nižší ako 42, ale 15 je menší ako 16, takže 15 musí byť minimálny netriedeného element. Takže teraz chceme vymeniť 15 a 23, aby sa nám tento zoznam. Zoradené časť zoznamu sa skladá zo 4, 8 a 15, a tieto prvky sú stále netriedené. Ale to len tak sa stane, že ďalšie netriedený prvok, 16, už je zoradený. Avšak, neexistuje žiadny spôsob, ako pre náš algoritmus vedieť, že 16 je už vo svojej správne miesto, takže musíme ešte opakovať presne rovnaký postup. Takže vidíme, že 16 je nižší ako 42, a 16 je nižší ako 23, takže 16 musí byť minimálne prvok. Je možné vymeniť tento prvok sám so sebou, takže môžeme proste nechať to v tomto mieste. Takže potrebujeme ešte jeden priechod nášho algoritmu. 42 je väčší ako 23, takže 23 musí byť Minimálna netriedeného element. Akonáhle sme prestavenie 23 a 42, skončíme s naším konečným zoradený zoznam - 4, 8, 15, 16, 23, 42. Vieme, že 42 musí byť na správnom mieste, pretože je to Jediný prvok doľava, a to je výber sort. Poďme sa teraz formalizovať náš algoritmus s niektorými pseudokód. Na prvom riadku, môžeme vidieť, že potrebujeme integrovať cez každý prvok zoznamu. Okrem posledného prvku, pretože 1 prvok Zoznam už je zoradený. Na druhej linke, považujeme prvý prvok netriedeného Časť zoznamu byť minimálny, ako sme s našou Napríklad, takže máme niečo pre porovnanie na. Riadok tri začína druhý cyklus, v ktorom sa iterácii Každý netriedeného element. Vieme, že potom, čo som iteráciách, sú zoradené časť nášho zoznamu musí mať aj prvky v ňom od každého kroku druhy jeden prvok. Takže prvý netriedeného prvok musí byť v polohe I plus 1. Na radový štvorvalec, porovnáme aktuálny prvok na minimum prvok, ktorý sme videli doteraz. Ak je aktuálna prvok je menší ako minimálny prvok, potom by sme mať na pamäti aktuálne element ako nové minimum na linke päť. Napokon, na tratiach šesť a sedem, vymeníme minimálne prvok s prvým netriedeného prvku, a tým pridaním do triedeného časti zoznamu. Akonáhle budeme mať algoritmus, dôležitá otázka sa opýtať sami seba ako programátorov je, ako dlho to trvalo? Ukážeme si klásť otázku, ako dlho to trvá, než to algoritmus bežať v najhoršom prípade? Spomínam si, že sme reprezentovať tento beh čas s veľkým O notácie. Aby bolo možné určiť minimálnu zmiešaný prvok, sme v podstate musel porovnať každý prvok v zozname na každý iný prvok v zozname. Intuitívne, toto znie ako O n na druhú operáciu. Pri pohľade na našom pseudokódu, máme tiež slučky vnorené vo vnútri ďalšie slučka, ktorá naozaj znie ako O z n štvorcový prevádzky. Pamätajte však, že sme nemuseli pozerať na Celý zoznam pri stanovení minimálnej zmesný element? Akonáhle sme vedeli, že 4 bola zoradená, napríklad, my nie treba sa na to pozrieť znova. Takže to robí nižšiu prevádzkovú dobu? Pre nášho zoznamu dĺžky 6, potrebovali sme robia päť porovnaní za prvý prvok, štyri porovnanie pre druhý prvok, a tak ďalej. To znamená, že celkový počet krokov je súčet celé čísla 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 krát n mínus 1 nad 2. Alebo ekvivalentne, n narovnal nad 2 mínus n nad 2. Keď sa hovorí o asymptotickej behu, to n squared termín bude ovládať tento n termín. Takže výber sort O z n na druhú. Pripomeňme si, že v našom príklade, výber sort stále potrebné skontrolujte, či číslo, ktoré bolo už je zoradený potrebné k presunu. Takže to znamená, že ak sme bežali výber druhu cez už zoradený zoznam, vyžadovalo by to rovnaký počet krokov ako to by pri jazde na úplne netriedeného zoznamu. Takže výber spôsob má najlepšiu prípadovú výkon n na druhú, ktoré predstavujú s omega n mocninou. A to je pre výber druhu. Iba jeden z mnohých algoritmov sa môžeme použiť na zoradenie zoznamu. Moje meno je Tommy, a to je cs50.