[Powered by Google Translate] Tommy: Pojďme se podívat na výběr druhu, algoritmus
pro přijetí seznamu čísel a třídění.
Algoritmus, pamatujte, je prostě krok-za-krokem
Postup pro dosažení úkolu.
Základní myšlenkou výběru druhu je rozdělit
náš seznam na dvě části -
jsou seřazena část a netříděné část.
Na každém kroku algoritmu, je číslo přesunuta ze
netříděného část do tříděného části až nakonec
Celý seznam je seřazen.
Takže tady je seznam šesti čísel -
23, 42, 4, 16, 8, a 15.
Právě teď se celý seznam se považuje za netříděný.
I když počet jako 16 již může být v jeho správné
zařazení, náš algoritmus nemá způsob, jak zjistit, že do
Celý seznam je seřazen.
Takže budeme považovat každé číslo má být netříděné, dokud třídíme
to sami.
Víme, že chceme, aby seznam, který bude ve vzestupném pořadí.
Takže budeme chtít vybudovat seřazena část našeho seznamu
zleva doprava, nejmenší k největší.
K tomu, budeme muset najít minimální směsný prvek
a dát na konci tříděného části.
Vzhledem k tomu, tento seznam není seřazen, jediný způsob, jak to udělat, je
podívat se na každý prvek v netříděného části, vzpomněl
, která složka je nejnižší a porovnávání
každý prvek k tomu.
Takže budeme se podívat na první 23.
Toto je první prvek jsme viděli, takže budeme pamatovat
to jako minimum.
Dále se podíváme na 42.
42 je větší než 23, takže 23 je ještě minimální.
Další je 4, což je méně než 23, takže budeme pamatovat 4
jako nový minimum.
Dále je 16, který je větší než 4, takže 4
je stále minimální.
8 je větší než 4 a 15, je větší než 4, takže 4 musí být
nejmenší netříděného element.
Takže i když jako lidé můžeme okamžitě vidět, že 4 je
minimální prvek, náš algoritmus musí se dívat na
každý netříděný element, i poté, co jsme našli 4 -
minimální prvek.
Takže teď, že jsme našli minimální prvek, 4, budeme chtít
pohybovat do tříděného části seznamu.
Vzhledem k tomu, je první krok, to znamená, že chceme dát 4 na
začátek seznamu.
V současné době je 23 na začátku seznamu, tak
pojďme vyměnit 4 a 23.
Takže teď náš seznam vypadá takto.
Je známo, že 4 musí být v konečné poloze, protože je to
jak nejmenší prvek a prvek na začátku
seznamu.
Takže to znamená, že jsme se nikdy potřebovat přesunout znovu.
Takže pojďme zopakovat tento proces přidat další prvek na
seřazeny část seznamu.
Víme, že nepotřebujeme se podívat na 4, protože je to
již řazeno.
Takže můžeme začít na 42, což budeme pamatovat jako
minimální prvek.
Takže příště se podíváme na 23, což je méně než 42, takže jsme
pamatovat 23 je nové minimální.
Dále vidíme 16, který je nižší než 23, tak
16 je nový minimální.
Teď se podíváme na 8, což je méně než 16, tak
8 je nová minimum.
A konečně 8 je menší než 15, takže víme, že 8 je minimální
netříděného element.
Takže to znamená, že bychom měli připojit 8 do seřazena
část seznamu.
Právě teď 4 je jediným seřazena prvek, a tak chceme umístit
8 vedle 4.
Vzhledem k tomu, 42 je první prvek v netříděného části
Seznam, budeme chtít vyměnit 42 a 8.
Takže teď náš seznam vypadá takto.
4 a 8 představují seřazena část seznamu, a
Zbývající čísla představují netříděného
část seznamu.
Takže pojďme pokračovat s další iterace.
Začneme s 23 tentokrát, protože nepotřebujeme se dívat na
je 4 a 8 už proto, že jsem
již seřazeny.
16 je nižší než 23, takže se budeme pamatovat
16 jako nové minimum.
16 je nižší než 42, ale 15 je menší než 16, takže 15 musí být
minimální netříděného element.
Takže teď chceme vyměnit 15 a 23, aby se
nám tento seznam.
Pořadí seřazených část seznamu se skládá ze 4, 8 a 15, a
tyto prvky jsou stále netříděné.
Ale to jen tak se stane, že další netříděný prvek, 16,
je již řazeno.
Nicméně, neexistuje žádný způsob, jak pro náš algoritmus na to, že 16
je již ve své správné místo, takže musíme ještě
opakovat přesně stejný postup.
Takže vidíme, že 16 je nižší než 42, a 16 je nižší než 23, takže
16 musí být minimální prvek.
Je nemožné vyměnit tento prvek sám se sebou, takže můžeme
prostě nechat to v tomto místě.
Takže potřebujeme ještě jeden průchod našeho algoritmu.
42 je větší než 23, takže 23 musí být
Minimální netříděného element.
Jakmile vyměníme na 23 a 42, skončíme s naším konečným
seřazený seznam -
4, 8, 15, 16, 23, 42.
Víme, že 42 musí být na správném místě, protože je to
Jediný prvek doleva, a to je výběr sort.
Pojďme se nyní formalizovat náš algoritmus s některými
pseudokód.
Na prvním řádku, můžeme vidět, že potřebujeme integrovat přes
každý prvek seznamu.
Kromě posledního prvku, protože 1 prvek
Seznam je již řazeno.
Na druhé lince, považujeme první prvek netříděného
Část seznamu být minimální, jak jsme s naší
Například, takže máme něco pro porovnání na.
Řádek tři začíná druhý cyklus, ve kterém se iteraci
Každý netříděného element.
Víme, že poté, co jsem iteracích, jsou seřazeny část
našeho seznamu musí mít i prvky v něm od každého kroku
druhy jeden prvek.
Takže první netříděného prvek musí být v poloze I plus 1.
Na řadový čtyřválec, srovnáme aktuální prvek na minimum
prvek, který jsme viděli doposud.
Pokud aktuální prvek je menší než minimální
prvek, pak bychom mít na paměti aktuální element jako nové
minimum na lince pět.
Konečně, na tratích šest a sedm, vyměníme minimální
prvek s prvním netříděného prvku, a tím
přidáním do tříděného části seznamu.
Jakmile budeme mít algoritmus, důležitá otázka se zeptat
sami sebe jako programátory je, jak dlouho to trvalo?
Ukážeme si klást otázku, jak dlouho to trvá, než to
algoritmus běžet v nejhorším případě?
Vzpomínám si, že jsme reprezentovat tento běh
čas s velkým O notace.
Aby bylo možné určit minimální směsný prvek, jsme
v podstatě musel srovnat každý prvek v seznamu na
každý jiný prvek v seznamu.
Intuitivně, toto zní jako O n na druhou operaci.
Při pohledu na našem pseudokódu, máme také smyčky vnořené uvnitř
další smyčka, která opravdu zní jako O
z n čtvercový provozu.
Pamatujte však, že jsme nemuseli dívat na
Celý seznam při stanovení minimální směsný element?
Jakmile jsme věděli, že 4 byla seřazena, například, my ne
je třeba se na to podívat znovu.
Takže to dělá nižší provozní dobu?
Pro našeho seznamu délky 6, potřebovali jsme dělají pět
srovnání za první prvek, čtyři srovnání pro
druhý prvek, a tak dále.
To znamená, že celkový počet kroků je součet
celá čísla od 1 do délky seznamu mínus 1.
Můžeme reprezentovat to s sumace.
Nebudeme zacházet do summations zde.
Ale ukazuje se, že toto shrnutí je rovna n krát
n minus 1 nad 2.
Nebo ekvivalentně, n narovnal nad 2 minus n nad 2.
Když se mluví o asymptotické běhu, to n squared termín
bude ovládat tento n termín.
Takže výběr sort O z n na druhou.
Připomeňme si, že v našem příkladu, výběr sort stále potřeba
zkontrolujte, zda číslo, které bylo již řazeno
potřebné k přesunu.
Takže to znamená, že pokud jsme běželi výběr druhu přes již
seřazený seznam, vyžadovalo by to stejný počet kroků jako to
by při jízdě na zcela netříděného seznamu.
Takže výběr způsob má nejlepší případovou výkon n na druhou,
které představují s omega n mocninou.
A to je pro výběr druhu.
Pouze jeden z mnoha algoritmů se můžeme
použít k seřazení seznamu.
Mé jméno je Tommy, a to je cs50.