[Powered by Google Translate] [Vkládání Třídit]
[Tommy MacWilliam] [Harvard University]
[To je CS50.TV]
Pojďme se podívat na vložení řadit, 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 vložení řadit, je rozdělit na náš seznam na dvě části,
jsou seřazena část a netříděné část.
>> Na každém kroku algoritmu, je přesunuta číslo
z netříděného části do tříděného části
až nakonec je seřazena celý seznam.
Zde je seznam šesti netříděných čísel - 23, 42, 4, 16, 8, a 15.
Vzhledem k tomu, že tato čísla nejsou vše ve vzestupném pořadí, to netříděný oni.
Vzhledem k tomu, jsme se začali řazení dosud, budeme uvažovat o všech šesti prvků naší netříděného část.
>> Jakmile začneme třídění, dáme tyto seřazené čísla vlevo od nich.
Takže, pojďme začít s 23, první prvek v našem seznamu.
Nemáme žádné prvky v naší seřazeny části ještě,
takže se pojďme prostě považují 23 za začátek a konec naší tříděného části.
Nyní, naše seřazeny část má jedno číslo, 23,
a naše netříděného část má těchto pět čísel.
Pojďme se nyní vložit další číslo v našem netříděného části, 42, do tříděného části.
>> Chcete-li tak učinit, budeme muset porovnat 42 k 23 - jediný prvek v našem seřazeny části tak daleko.
Dvaačtyřicet je větší než 23, takže se může jednoduše připojit 42 až do konce
z tříděného části seznamu. Výborně!
Nyní náš seřazeny část má dva prvky, a naše různě část má čtyři prvky.
Takže, pojďme se teď přesunout do 4, další prvek v netříděného části.
Tak by kde se tento umístí do tříděného části?
>> Pamatujte si, že chceme umístit toto číslo v seřazeném pořadí
takže naše seřazeny část zůstává správně seřazeny za všech okolností.
Pokud umístíme 4 na pravé straně 42, pak se náš seznam bude mimo provoz.
Takže, pojďme pokračovat v pohybu zprava doleva v našem druhu porci.
Jak jsme se přestěhovat, pojďme posunout každé číslo dolů na místo, aby se prostor pro nové číslo.
Dobře, 4 je také méně než 23, takže nemůžeme umístit ani zde.
Pojďme se 23 vpravo o jedno místo.
>> To znamená, že bychom chtěli umístit 4 do prvního slotu v seřazeny části.
Všimněte si, jak tento prostor v seznamu byla již prázdná,
protože jsme byli pohybuje seřazené prvky dolů, jak jsme se setkal s nimi.
Dobrá. Takže, jsme v půli cesty.
Pojďme pokračovat v naší algoritmus vložením 16 do tříděného části.
Šestnáct je menší než 42, takže se pojďme posunout 42 na pravé straně.
Šestnáct je také méně než 23, takže se pojďme také posunout tento prvek.
>> Nyní, 16 je větší než 4. Takže to vypadá, že bychom chtěli vložit 16 mezi 4 a 23.
Při pohybu přes seřazeny části seznamu zprava doleva,
4 je první číslo jsme vidět, že je menší, než je počet
snažíme vložit.
Tak, teď můžeme vložit 16 do tohoto prázdného slotu,
které, pamatujte, jsme vytvořili pohybliv prvky v řazení části nad
jak jsme se setkali je.
>> Dobrá. Nyní, máme čtyři seřazené prvky a dvě netříděné prvky.
Takže, pojďme přesunout 8 do tříděného části.
Osm je menší než 42.
Osm je menší než 23.
A 8 je menší než 16.
Ale 8 je větší než 4.
Takže bychom chtěli vložit 8 mezi 4 a 16.
A teď máme jen jednu větší zbývá prvek k řazení - The 15.
Patnáct je nižší než 42,
Patnáct je menší než 23.
A 15 je menší než 16.
Ale 15 je větší než 8.
>> Takže, tady je místo, kde chceme, aby se naše konečné vložení.
A jsme hotovi.
Nemáme žádné další prvky v netříděného části,
a naše seřazeny část je ve správném pořadí.
Čísla jsou seřazeny od nejmenší k největší.
Takže, pojďme se podívat na některé pseudokódu, který popisuje kroky, jsme právě provedli.
>> Na řádku 1, můžeme vidět, že budeme muset iteraci každý prvek v seznamu
kromě první, bude od prvního prvku v netříděného části jednoduše se
první prvek v tříděném části.
Na řádcích 2 a 3, jsme sledování našeho současného místa v netříděného části.
Element reprezentuje číslo v současné době pohybuje do tříděného části,
a j reprezentuje náš index do netříděného části.
>> Na řádku 4, jsme iterace jsou seřazeny části zprava doleva.
Chceme zastavit iterace, jakmile prvku na levé straně naší současné pozice
je menší než prvek se snažíme vložit.
Na řádku 5, jsme přesouvá každý prvek my se setkáme o jedno místo vpravo.
Tak, budeme mít volný prostor pro vložení do kdy najdeme první prvek
méně než prvku Stěhujeme.
Na řádku 6, jsme aktualizaci našeho počítadla nadále pohybovat doleva přes seřazeny část.
A konečně, na řádku 7, jsme vkládání prvku do tříděného části seznamu.
>> Víme, že je to v pořádku vložit do polohy j,
proto, že jsme již přestěhovali prvek, který býval tam jedno místo vpravo.
Pamatujte si, že jdeme přes seřazeny část zprava doleva,
ale jdeme přes netříděného část zleva doprava.
Dobrá. Pojďme se teď podívat na to, jak dlouho běží, že algoritmus se.
Ukážeme si klást otázku, jak dlouho to trvá, než to algoritmus běžet v nejhorším případě.
Připomeňme si, že zastupujeme tento běžící čas s Big O notace.
Pokud je chcete seřadit náš seznam, museli jsme iteraci prvky v netříděného části,
a pro každý z těchto prvků, případně přes všechny prvky v uspořádané části.
Intuitivně, to zní jako O (n ^ 2) provozu.
>> Při pohledu na našem pseudokódu, máme smyčku vnořené uvnitř jiné smyčky,
, která ostatně zní jako O (n ^ 2) provozu.
Nicméně, jsou seřazeny část seznamu neobsahovala celý seznam až do samého konce.
Přesto bychom mohli potenciálně vložit nový prvek na samém počátku tříděného části
na každé iteraci algoritmu,
což znamená, že bychom se podívat na každý prvek v současné době v tříděném části.
Takže, to znamená, že by mohly vytvořit jednu srovnání pro druhý prvek,
dvě srovnání na třetí prvek, a tak dále.
Takže, celkový počet kroků je součet celých čísel 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 (n - 1) v průběhu 2, který je ekvivalentní n ^ 2/2 - n / 2.
Když se mluví o asymptotické běhu,
tento n ^ 2 termín bude ovládat tento n termín.
Takže, vložení sort Big O (n ^ 2).
Co když jsme běželi vložení Řadit již tříděném seznamu.
V tomto případě bychom jednoduše vybudovat seřazena část zleva doprava.
Takže, budeme potřebovat pouze na pořadí kroků n.
>> To znamená, že vkládání způsob má nejlépe případu výkon n,
které představují s Ω (n).
A to je pro vložení řadit,
jen jeden z mnoha algoritmů můžeme použít k seřazení seznamu.
Mé jméno je Tommy, a to je CS50.
[CS50.TV]
Oh, si prostě nemůže přestat, že jakmile začne.
Oh, jsme udělali - >> Boom!