Programování v Pythonu
Přihlásit se
Programování v Pythonu (20/21) · 8:36

Insertion Sort v Pythonu

V tomto videu se pokusím vytvořit implementaci "insertion sort" algoritmu (řazení vkládáním) o kterém jsme mluvili v posledním videu. Udělám to jako funkci v Pythonu. Tuto funkci nazvu "insertion_sort()"... a bude brát seznam... takže "list" je její parametr v definici funkce a my jí budeme muset předávat seznam jako argument. A co teď uděláme je, projdeme všechny pozice v seznamu. Tak by se tomu dalo říkat. Řekneme "for index in range():". Můžeme začít na levém konci seznamu. Můžeme říct "len(list)"... "len" prostě znamená "délka" [zkratka pro "length"], délka seznamu. Toto tedy začne "index"... řekněme, že seznam "list" má čtyři prvky, potom "len(list)", tady, by bylo 4, vyhodnotilo by se jako 4. "range(4)" by vyrobilo seznam, který má prvky [0, 1, 2, 3]. Proměnná "index" by procházela přes různé indexy prvků v tomto seznamu přímo tady. A tak bychom to mohli udělat, ale z předcházejícího videa si možná vzpomínáte, že když provádíte "insertion sort", tak vlastně nedává smysl začínat na levém konci, protože nalevo od něj není nic, z čím ho porovnat. Takže vlastně můžeme prostě začít na druhém prvku zleva. A nejlevější prvek je 0. prvek, takže můžeme začít na 1. prvku. Nyní tedy, pokud je seznam délky 4, tohle vyrobí [1, 2, 3]. Tudíž 1 je druhý prvek zleva. 2 je další prvek na pravo. 3 je poslední prvek. Pamatujte si, indexy vždycky začínají od 0... 0. prvek je nejlevější prvek v seznamu. Dobře, můžeme přes to projít. Získejme hodnotu - v daném okamžiku - prvku, který je na tomto indexu. Takhle ho nemusíme pokaždé znovu hledat, "value" se rovná "list[index]". Tohle rozhodně nebude nejefektivnější možná implementace "insertion sortu". Bude to můj nejlepší pokus, když to píšu v "naživo", a snad způsobem, kterému budete schopni porozumět. "value" je tedy prostě prvek v seznamu na každém z těchto indexů, který teď budeme porovnávat se všemi prvky nalevo od něj. Co chci udělat je... porovnat hodnotu... chci porovnat hodnotu s každým prvkem nalevo od ní. Tak si zadefinujme proměnnou "i", která bude idexem prvků, se kterými chci "value" porovnávat. Na začátku chci porovnávat "value" s prvkem, který je nalevo od ní. Tudíž "i" by měl být o 1 menší, než index, na kterém je "value". "index - 1" Toto bude index prvku, který přímo nalevo od "value". Ale budeme "i" snižovat dále a dále. Abychom mohli pokračovat v porovnávání hodnoty s věcmi dále a dále nalevo. Co tedy chceme udělat je... chceme porovnávat dále a dále nalevo dokud "i" se nedostane až na začátek seznamu. A když se "i" dostane až na začátek seznamu, tak bude rovné 0. Co tedy chceme udělat je, chceme udělat tohle dokud je "i" větší nebo rovno 0. Protože pokud budeme "i" snižovat dále a dále, budeme se v seznamu pohybovat dále a dále nalevo. To nechceme udělat pokud je "i" - víte co - dále - je negativní - To by prostě začalo dělat divoké věci. Takže dokud je "i" větší nebo rovno 0... co udělam je, budu tlačít "i" dále a dále doleva. Zkusme me to takto, první věc, kterou chci udělat... už jsme to dotlačili o jednu doleva, tak porovnáme, jestli je "value" menší, než... tahle věc pořád říká "syntax error", protože čeká, že to dopíšu... pokude je "value" menší, než prvek, který je teď na indexu "i". Tudíž prvek, který je na indexu "i" (list[i]), prvek na indexu "i" je tento přímo tady. Pokud je tedy menší než toto, posuňme prvek, který je tamhle... posuňme ho o jedno doprava. Index napravu je tedy "i + 1" a nemůžu jednoduše říct, že je to "index", protože si pamatujte, že budu "i" tahat níže a níže. Protože práve teď má "i" hodnotu "index - 1" v prvním průchodu touto "while" smyčkou, ale já - jak uvidíte za sekundu - budu "i" snižovat, takže vždycky nebude o jedna nalevo od "index". Říkám tedy ať už je "i" kdekoliv, vezměme pozici o jednu napravo od "i"... o jednu napravo od toho... takže "i + 1" je její index. A nahradmě to tím, co je v "list[i]", tím, co je na pozici "i", ať už je to cokoliv. Takže jsme v podstatě vzali tuhle věc tady napravo ať už tam bylo jakékoliv číslo, a dáváme ho do pozice, která je o jednu napravo od toho. A potom, a způsob, jakým vlastně stavíme tento algoritmus. Ať už tam bude cokoliv... No... o tom nebudu mluvit. Projdeme si tím a uvidíme, jak to bude fungovat. A potom můžeme posunout "value" doleva. Cokoliv, co bylo v této pozici tady bude nahrazeno "value". "list[i]" bude tedy rovný "value". Jeden způsob, jak se o tom dá přemýšlet... ...nechtě mě tady dopsat komentář... posuň to, co bylo... posuň číslo z pozice "i" do pozice "i + 1", nebo "kyblík" "i + 1" ...tak se o tom také dá přemýšlet... A potom můžete říct, posuň číslo doprava... takhle to nazvu... posuň číslo doprava... v pozici... napíšeme to takhle... posuň číslo na pozici "i" doprava na pozici "i + 1" A potom tady, posunujeme... posuň "value" doleva do pozice "i". A pokud si pamatujete co jsme dělali v posledním videu, tak to přesně popisuje. Porovnáváme "value" s číslem, které je nalevo od ní. Pokud je to méně, pak číslo nalevo, ať je jakékoli, posuneme doprava a pak "value" doleva. Nyní porovnáme "value" s nižším číslem. Chceme dekrementovat "i", chceme snížit "i", dekrementování je prostě inkrementování směrem dolů. Do "i" dosadíme "i-1", a pak provedeme smyčku znovu. Teď bude "value" porovnána... teď je "i" o dvě pozice nalevo od "index" ... porovnána s ním. Pokud je nižší než "value", posuneme číslo doprava a "value" posuneme znovu doleva. Co když nastane situace kdy "value" není nižší, než číslo se kterým ji porovnáváme? Pokud není nižší, znamená to, že "value" už je na správném místě. A to znamená, že jsem hotoví, a nemusíme "value" posouvat dál doleva. Nemusíme posouvat čísla doleva ani doprava. Máme hotovo. Myslím, že by to mohlo fungovat, pokud jsem neudělal nějakou hloupou chybu. Podívejme se, jestli se mi povede... jestli to funguje jako třídící algoritmus. Uložím program "insertion_sort", a spustím ho. Nemám tam žádné syntaktické chyby. Syntaxe znamená, jaké jsem použil znaky... Nezapomněl jsem na čárku, anebo znak "větší než". Interpret dokáže kód přečíst, a provést ho. Ale podívejme se, jestli to skutečně funguje. Definujeme seznam "a". Řekněme [7,1,3,5,9,2] přidám do něj ještě číslo 3. To je seznam "a". Podívejme se... tohle je okamžik pravdy, insertion_sort(a), podívejme se, co se stane. Pamatujte, třídíme přímo v seznamu, tato funkce nemá návratovou hodnotu. Měla by vzít jakýkoli seznam, a uspořádat jeho prvky tak, aby byly seřazené. Tohle je okamžik pravdy. Podívejme se, jak "a" vypadá. Seznam je seřazený! Myslím, že jsem neudělal žádnou velkou chybu. Takže tedy je varianta algoritmu třídění vkládáním.
video