Programování v Pythonu
Přihlásit se
Programování v Pythonu (19/21) · 7:52

Řadící algoritmus "Insertion Sort" Názorný grafický popis algoritmu pro řazení seznamu prvků známého jako Insertion Sort. Není to nejrychlejší algoritmus, ale lehce se na něm pochopí principy řadících algoritmů.

Co bych chtěl v tomto videu ukázat — je o čem si myslím, že je jedna z více intuitivních cest jak seřadit seznam. Pokud bych měl řadit seznam manuálně, dělal bych to asi takhle. Ale je důležité říct, že to není nejefektivnější metoda jak seřadit seznam. Ale — Myslím, že to je dobrý začátek na kterém pochopíte o čem řazení seznamů vůbec je. Jmenuje se to "Insertion Sort". Ukáži vám grafickou ukázku tohoto algoritmu. A jenom abyste věděli, "algoritmus" zní jako hodně vznešené slovo. Ale algoritmus je vlastně jenom způsob řazení, nebo proces jak něco dělat, nebo metoda jak to dělat. Program je konkrétní implementace algoritmu, nebo může být konkrétní implementací algoritmu. Jakmile mám obecný algoritmus, Můžu ho implementovat v Pythonu, můžu ho implementovat v Céčku, můžu ho implementovat v Javě. To jsou všechno konkrétní programy, ale všechny by implementovaly stejný způsob jak řadit. A to je co nyní popisuji — algoritmus "Insertion Sort". Takže pojďme začít s jednoduchým příkladem: Řekněme že mám seznam — Řekněme že mám seznam v Pythonu, protože na tomhle budeme dál dělat v Pythonu, a tento seznam je — třeba [7,3,1,2,4,6]. Takže způsob jakým se dělá Insertion Sort je že jdete prvek po prvku, a potom prvek porovnáte s prvky před ním, a přitom hledáte první element, kde ten váš prvek je menší a prostě ho tam šoupnete. Pojďme si ukázat o čem mluvím: Mohli byste začít se sedmičkou, nultým prvkem, ale když se na něj podíváte— když chcete začít nultým prvkem, říkáte si "Hej, nemám ho s čím porovnávat" takže nemá úplně smysl začínat s nultým prvkem. Takže, když to budete implementovat, začali byste s třetím prvkem— Promiňte! Začali byste s— Tohle je nultý prvek, začali byste s prvním prvkem tady. Tohle je nultý, tohle je první. Vím, tohle může být trochu matoucí když tomuhle říkáte první prvek ale tohle je nultý. Takže začnete s touhle trojkou tady a začnete jí porovnávat se všemi prvky před tím a jakmile najdete prvek kde trojka je menší tak jí šoupnete do té části seznamu. Takže se zeptáte: "OK, je trojka menší než sedmička?" "Jo, je menší než sedmička" Takže chcete posunout— chcete posunout sedmičku tam kde je trojka. Napíšu to sem— Teď— teď se snažíme porovnat trojku se vším před ní. teď se snažíme porovnat trojku se vším před ní. Takže si řekněte: "OK, je trojka menší než sedmička?" "Jo, je menší než sedmička" Takže pojďme šoupnout sedmičku na místo trojky a trojku na místo sedmičky. A protože už není s čím porovnávat trojku, není tam nic menšího— nejsou tam žádné prvky před nultým prvkem, takže pojďme šoupnout trojku přesně sem. Takže náš seznam teď vypadá takhle náš seznam teď vypadá: [3,7,1,2,4,6] A jedna věc která je zajímavá— na kterou byste se měli soustředit— je že jak tvoříme ten seznam— nultý prvek je nyní určitě menší než první prvek a všechno až do prvního prvku je nyní seřazeno. všechno až do prvního prvku je nyní seřazeno. A to bude platit jak budeme pokračovat— jak budeme zpracovávat vyšší a vyšší indexy, až do toho indexu potom co doděláme běh pro ten prvek, bude seřazeno. Budu se to snažit vypíchnout v průběhu videa. Takže udělali jsme první index, teď se můžeme přesunout na druhý prvek, což je tady ta jednička. Takže vezmete tuhle jedničku— Napíšu jí tady na stranu— vezmete jedničku a porovnáte jí ... ... se všemi prvky před ní: "OK, je jednička menší než sedmička?" "Jasně, jednička je menší než sedmička" Takže pojďme šoupnout sedmičku kde byla jednička. A potom můžete buď pokračovat porovnávání, nebo můžete šoupnout jedničku kde byla sedmička. A pak si řeknete: "OK, je jednička menší než trojka?" "Jo jasně, je menší než trojka." Takže pojďme šoupnout trojku na místo jedničky a jedničku na místo trojky. Takže jak teď vypadá náš seznam? Náš seznam nyní bude vypadat takto— Náš seznam nyní bude vypadat [1,3,7,2,4,6] Všimněte si, že potom co jsme se dostali na ntý index— v tomto případě index 2 tam kde před tím byla jednička— všechno až do toho indexu je nyní seřazené. Takhle část tady je seřazená. Bude to— Více prvků tam přibyde jak budeme pokračovat, ale zatím tahle část je seřazená. Takže můžete vidět, že až se dostaneme na konec seznamu, všechno bude seřazené. Takže nyní pojďme na další index, nebo další prvek v seznamu, a to je tady ta dvojka. To je tahlencta dvojka. A tak, porovnáme dvojku se sedmičkou dvojka je určitě menší než sedmička, takže pojďme dát sedmičku na místo dvojky, a dvojku na místo sedmičky. Nyní porovnáte dvojku s trojkou. dvojka je menší než trojka, takže dejme trojku na místo dvojky, a dvojku na místo trojky. Potom porovnejme dvojku s jedničkou. "Je dvojka menší než jednička?" "Ne, není menší než jednička." Takže nemusíme dělat nic dalšího. Nemusíme se dívat víc doleva. A nyní po tomto běhu— v dalším běhu budeme porovnávat tuto dvojku se vším před ní— Takže po tomto běhu, náš seznam bude vypadat takhle: nás seznam bude vypadat: [1,2,3,7,4,6]. Všimněte si, že všechno až do třetího prvku— tedy nultý, první, druhý a třetí prvek— je nyní seřazeno. A teď se můžeme podívat tady na— další prvek ze seznamu. Jedna věc co chci ujasnit: když to budete implementovat, je více cest jak to dělat. Nemusíte vždycky— v tomhle příkladu jsme vždy říkali: "Hey, je dvojka menší než sedmička?" a dali jste sedmičku na místo dvojky což byste měli udělat. A potom jste dali dvojku na místo sedmičky. Ale reálně, můžete jít dolů dokud nenajdete správné místo kam šoupnout dvojku, posunou všechno mezi tím doprava a až pak tam šoupnout dvojku. Ačkoli tenhle způsob je trochu přehlednější. Možná vám ukážu různé způsoby jak to dělat, až když budeme opravdu implementovat ten algoritmus. No nic, pojďme se podívat tady na čtyřku. Stejný postup: 4 je menší než 7, takže šoupneme sedmičku na místo čtyřky a čtyřku na místo trojky. "Je čtyřka menší než trojka?" "Ne, není menší než trojka" A tady přestaneme, jsme hotovi. Nyní, všechno až do čtvrtého indexu takže seznam [0,1,2,3,4] je nyní sežazený. A teď náš seznam vypadá— jenom kousek odscrolluji— Nyní náš seznam vypadá— Napíšu to— Je to [1,2,3,4,7,6]. A nyní poslední prvek ze seznamu— To je šestka kterou porovnáváme— A to je naposled co jsme to dělali to byla čtyřka, která nás zajímala. Ale teď nás zajímá šestka. "Je šestka menší než sedmička?" "Jasně že je". Takže pojďme dát sedmičku na místo šestky, a šestku na místo sedmičky. "Je šestka menší než čtyřka?" "Ne, není" A tam skončíme. Protože víme že to bude seřazené. Pokud půjdeme dále, budeme vědět že dostaneme prvky, které jsou menší nebo rovné 4. Tak jsme hotovi, máme seřazený seznam. List je nyní seřazen: [1,2,3,4,6,7] V dalším videu se pokusím implementovat algoritmus který jsem právě popsal. A implementuji ho jako jednoduchou funkci v Pythonu.
video