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