[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.