Tip:
Highlight text to annotate it
X
Želim da u ovom snimku pređem ono što smatram
da je jedan od intuitivnijih načina za sortiranje liste.
Tako bih je verovatno ja sortirao kada bih to morao ručno da uradim.
Ali samo da razjasnim,
to nije najefikasniji način da se sortira lista.
Ali hajde samo --
mislim da je ovo dobra početna tačka
da se zagrejemo za sortiranje listi.
Naziva se sortiranje umetanjem.
Daću vam grafički opis
algoritma za sortiranje umetanjem.
I samo da znate,
algoritam zvuči kao veoma fensi reč.
Ali algoritam je zapravo samo način kako sortirati,
ili proces kako nešto uraditi,
ili metod kako nešto uraditi.
Program je specifična implementacija algoritma,
ili može biti specifična implementacija algoritma.
Jednom kada imam opšti algoritam,
mogu da ga implementiram u Python-u,
mogu da ga implementiram u C-u,
mogu da ga implementiram u Java-i.
To su sve specifični programi,
ali bi svi implementirali
isti način sortiranja.
I to je ono što upravo opisujem --
Algoritam za sortiranje umetanjem.
Hajde da počnemo sa jednostavnim primerom:
Recimo da imam listu --
Recimo da imam Python listu,
pošto ćemo ovo raditi u Python-u,
i ta lista je --
recimo da je [7, 3, 1, 2, 4, 6].
Dakle, način na koji radimo sortiranje umetanjem
je da idete element po element,
i poredite ga sa elementima pre njega,
i onda tražite prvi element koji mu prethodi
i od kog je manji,
i onda ga zalepite baš tamo.
Hajde da vam pokažem o čemu pričam:
mogli bi da počnete sa 7,
nulti element ovde,
ali kada pogledate --
kada počnete sa nultim elementom,
reći ćete: "Čekaj, nemam ništa od ranije sa čim bih to poredio, "
tako da u stvari nema smisla početi od nultog elementa.
Zapravo, ako biste implementirali ovaj algoritam,
počeli biste sa prvim elementom --
Izvinjavam se! Počinjete sa --
ako je ovo nulti element,
počinjete sa prvim elementom upravo ovde.
Ovo je nulti, ovo je prvi, znam,
zbunjuje vas kada za ovo kažete da je prvi element
ali ovaj je nulti.
Dakle, počinjete sa ovom trojkom ovde
i počinjete da je poredite sa svim elementima koji joj prethode
i čim pronađete element koji je 3 ili manji
zalepite ga u taj deo liste.
Dakle, šta radite, kažete:
"OK, da li je 3 manje od 7?"
"Pa, da, jeste manje od 7."
I šta želite da uradite, želite da pomerite --
da pomerite 7 tamo gde je 3.
Hajde da stavim to ovde --
dakle, koristimo --
pokušavamo da uporedimo 3 sa svim što mu prethodi, trenutno.
Pokušavamo da uporedimo 3 sa svim što mu prethodi.
I kažete: "OK, da li je 3 manje od 7?"
"Da, manje je od 7."
Hajde da stavimo 7 na mesto 3,
a 3 ćemo staviti na mesto 7.
Naročito jer nije preostalo ništa sa čim bi poredili 3,
nema ničeg manjeg --
nema elemenata pre nultog elementa,
tako da ćemo samo zalepiti 3 tamo.
I naša lista sada izgleda ovako
naša lista izgleda kao: [3, 7, 1, 2, 4, 6]
I jedna stvar koja će vam biti zanimljiva --
treba obratiti pažnju na nešto --
kako gradimo ovu listu, mi --
nulti element je sada definitivno manji od prvog elementa
i sve do, i uključujući prvi element
je sada sortirano.
Sve do, i uključujući i prvi element
je sada sortirano.
I to će i dalje biti tačno kako nastavljamo da prolazimo kroz --
kako idemo kroz veće i veće indekse,
dok ne uključimo taj indeks,
nakon što uradimo taj prolaz, biće sortirano.
I pokušaću da na to ukažem dok radimo.
Dakle, uradili smo prvi indeks,
sada možemo da pređemo na drugi element,
koji je ova jedinica ovde.
I tako uzmete tu jedinicu --
staviću je ovde sa strane --
uzmete 1 i uporedite sa...
... sa svakim od elemenata koji su prethodili:
"OK, da li je 1 manje od 7?"
"Naravno, 1 je manje od 7"
pa hajde da stavimo 7 tamo gde je bilo 1.
I onda biste mogli samo da nastavite sa poređenjem,
ili da jednostavno stavite 1 tamo gde je 7.
I onda kažete: "OK, da li je 1 manje od 3?"
"Da, naravno, manje je od 3."
Hajde da stavimo 3 tamo gde je 1,
i da stavimo 1 gde je 3.
I, kakva je sada naša lista?
Naša lista će sada izgledati kao --
naša lista će sada biti [1, 3, 7, 2, 4, 6]
Primetite, nakon što smo stigli do n-tog indeksa --
dakle, u ovom slučaju, ovo je indeks 2
gde je bila jedinica --
sve do i uključujući taj indeks je sortirano.
Ovaj deo ovde je sortiran.
Biće --
druge stvari će biti
verovatno ubačene ovde kako budemo išli dalje,
ali za sada, ovaj deo je sortiran.
Dakle, možete da vidite,
dok stignemo do kraja ove liste,
sve će biti sortirano.
Hajde da odemo do sledećeg indeksa,
ili do sledećeg elemnta liste,
a to je ova dvojka ovde.
To je ova dvojka ovde.
I onda, poredimo 2 i 7,
2 je definitivno manje od 7,
pa hajde da stavimo 7 tamo gde je 2,
i 2 tamo gde je 7.
Sada uporedite 2 i 3.
2 je manje od 3,
hajde da stavimo 3 tamo gde je 2,
i da stavimo 2 tamo gde je 3.
Onda uporedite 2 i 1.
"Da li je 2 manje od 1?"
"Ne, nije manje od 1."
Dakle, ne treba više ništa da radimo.
Ne treba da nastavimo da [tražimo] -- idemo u levo.
I sada, nakon ovog prolaza --
u ovom prolazu poredimo ova dva elementa
sa svim pre njih --
Dakle, nakon ovog prolaza, naša lista izgleda ovako:
naša lista izgleda kao: [1, 2, 3, 7, 4, 6]
Primetiću, sve do i uključujući treći element --
nulti, prvi, drugi, treći element--
je sada sortirano.
I sada smo spremni da pogledamo ovo --
sledeći element u listi.
I želim da razjasnim jednu stvar:
kada zaista ovo implementirate,
postoji nekoliko načina da to uradite.
Ne morate uvek da --
u ovom primeru, rekli smo:
"Hej, 2 je manje od 7?"
7 ide na mesto 2, to je
ono što treba da uradite.
I onda smo 2 pomerili na mesto 7.
Ali u stvari,
možete da nastavite dalje
dok ne nađete dobro mesto da smestite 2,
pomerajući sve u desno dok to radite,
i onda stavite 2.
Mada, na ovaj način je malo lakše pratiti šta se dešava.
I vau, možda ćemo istražiti druge načine da to uradimo
kada budemo zapravo implementirali algoritam.
U svakom slučaju, hajde da pogledamo ovu četvorku.
Identična ideja:
4 je manje od 7,
pa hajde da stavimo 7 tamo gde je 4
i 4 tamo gde je 7.
"Da li je 4 manje od 3?"
"Ne, nije manje od 3."
Tako da prestajemo, završili smo.
Sada, sve do i uključujući četvrti element
liste -- 0 1 2 3 4 --
je sada sortirano.
I sada naša lista izgleda --
malo ću odskrolovati na dole --
Sada, naša lista izgleda ovako --
Zapišite --
To je [1, 2, 3, 4, 7, 6].
I sada možemo da odemo do zadnjeg elementa liste --
Sada upoređujemo 6 --
poslednji put kad smo ovo radili
bila nam je bitna četvorka.
Ali sada nam je bitna šestica.
"Da li je 6 manje od 7?" "Naravno."
Hajde da stavimo 7 tamo gde je 6,
i 6 tamo gde je 7.
"Da li je 6 manje od 4?" "Ne, nije."
I tako završavamo.
Jer znamo da će ovo biti sortirano.
Ako bismo nastavili dalje, dobili bismo samo elemente
koji su manji ili jednaki 4.
Znači gotovi smo, sortirali smo ovu listu.
Sada je sortirana lista: [1, 2, 3, 4, 6, 7]
U sledećem snimku,
zapravo ću pokušati da implementiram
ovaj algoritam koji sam upravo opisao.
I implementiraću ga kao jednostavnu Python funkciju.