Sortiranje umetanjem u Python-u

Osnovna implementacija algoritma za sortiranje umetanjem.

Ono što ću uraditi u ovom snimku je

pokušaj pravljenja implementacije

algoritma za sortiranje umetanjem

o kom smo pričali u prethodnom snimku.

Napraviću to kao Python funkciju.

Dakle, pozvaću Python funkciju insertion_sort()

koja će primiti listu...

dakle lista je parametar u definiciji funkcije...

tako da ćemo morati da je prosledimo
u listi argumenata.

I hajde da... ono što ćemo uraditi je da

prođemo kroz sva mesta u listi.

Pretpostavljam da bi to mogli tako reći.

Dakle, kažemo *for index in range()*.

Mogli bi krenuti od krajnjeg levog mesta u listi.

Tako da možemo prosto reći len()...

len samo znači... to je skraćeno od "length"...

dakle, dužine liste.

Tako da ono što bi se desilo je

da bi indeks počeo...

hajde da kažemo da lista ima u sebi četiri elementa...

onda bi len(list), ovo upravo ovde,

bilo 4, izvršenje bi dalo 4.

Range(4) bi dalo listu

koja ima elemente [0, 1, 2, 3] u sebi.

I tako, index bi mogao da prođe kroz

sve različite indekse ove liste ovde.

I to bi mogli tako da uradimo,

ali možda se sećate iz prethodnog snimka

da kada se radi sortiranje umetanjem

u suštini, nema smisla

početi od skroz levog elementa.

Jer on nema ništa s leve strane sa čime bi se poredio.

Tako da u stvari možemo početi

od drugog elementa s leve strane.

A skroz levi element je nulti element,

tako da možemo krenuti od prvog elementa.

Tako da sad, ako je lista dužine 4,

ovo ovde će dati [1, 2, 3].

Dakle, 1 bi bio drugi element s leva.

2 bi bio sledeći na desno.

3 bi bio poslednji.

Zapamtite, sa indeksima uvek počinjemo od 0...

nulti element je skroz levi element u listi.

Lepo, sada možemo proći kroz sve to-

Uzmimo vrednost - u tom trenutku vremena -

elementa koji je pod tim indeksom.

Na taj način ne moramo stalno da ga tražimo,

vrednost je jednaka list[index].

I ovo sigurno neće biti

najefikasnija implementacija,

čak ni za sortiranje umetanjem.

Ovo će biti moj najbolji pokušaj,

pisanja u realnom vremenu,

i na način koji će, nadam se...

koji ćete moći da razumete.

Dakle, value je samo stavka u listi

na svakom od ovih indeksa

koje ćemo sada uporediti

sa svim elementima sa njihove leve strane.

A ono što želim da uradim je da...

poredim vrednost... želim da poredim vrednost

sa svakim elementom sa njegove leve strane.

Stoga, definišimo promenljivu i

i postavimo je da bude indeks onih stvari

sa kojima želim da uporedim value.

I odmah s početka

želim da poredim value sa onim sa njegove leve strane.

Dakle, i treba da bude

za jedan manji indeks u odnosu na index.

Dakle, *index - 1*.

To je indeks elementa

koji je odmah levo od njega.

Ali mi ćemo nastaviti da smanjujemo i i dalje.

Tako možemo da nastavimo da poredimo value

sa stvarima dalje i dalje na levu stranu.

I ono što želimo da uradimo je da...

želimo da nastavimo sa poređenjem
sve dalje i dalje na levo

dok i ne ode skroz do početka liste.

A i je otišlo skroz do početka liste

onda kada postane jednako 0.

Dakle, ono što želimo da uradimo je,

želimo da ovo izvršavamo

dok je i veće ili jednako 0.

Jer ako nastavimo da smanjujemo i sve više i više,

odlazićemo sve dalje i dalje

na levu stranu liste.

Ne želimo da to izvršavamo

kada je i.... znate--- dalje.... kada je negativan broj...

to će samo početi da proizvodi lude pojave.

Dakle, dok je i veće ili jednako 0...

ono što ću uraditi je

da nastavim da guiram i dalje i dalje na levo.

Pokušajmo to na ovaj način,
i prva stvar koju želim da uradim...

već smo jednom izgurali na levo.

Hajde da uporedimo...

dakle, ako je value manje od...

ova stvar uporno daje sintaksnu grešku

jer me čeka da nastavim da kuckam...

ako value bude manje
od elementa koji je sada na indeksu i.

Dakle, element na indeksu i... list[i]

element na indeksu i je upravo ovaj ovde.

Ako je manji od toga,

hajde da pomerimo element koji je ovde...

pomerimo ga jednom na desno.

Tako da je pravo mesto *i + 1*

i ja ne mogu reći da je to index

jer setite se da nastavljam da odvlačim i

na sve manje i manje i manje.

Jer, upravo sada, i je *index - 1*

u prvom prolasku kroz ovu while petlju,

ali ja ću... kao što ćete videti za sekund...

ja ću nastaviti da smanjujem i,

tako da neće uvek biti za jedan levo od index.

Zato ću reći, gde god da je i,

hajde da uzmemo mesto za jedan s desne strane od i...

jedno mesto od... jednom na desno od...

dakle, njegov indeks je *i + 1*.

I hajde da zamenimo to sa šta god da je na list[i],

šta god da je na i, na mestu i.

Mi u suštini uzimamo ovu stvar ovde,

koji god da je broj bio tu.

I stavljamo na mesto

koje je za jedno mesto s desne strane od njega.
A onda,

i zapravo na način na koji smo pripremili taj algoritam.

Šta god da se desi da je tu...

Zapravo... neću o tome pričati.

Proći ćemo kroz to i videti kako se to sve odigrava.

I tada možemo da pomerimo value ulevo.

Tako da, šta god da je bilo na tom mestu,

biće zamenjeno sa value.

Tako će list[i] postati jednako sa value.

I jedan način da o tome mislimo

- napisaću komentar ovde -

pomeri ono što je...

pomeri broj sa mesta i na mesto *i + 1*

ili u stvari kontejner na *i + 1*...

pretpostavljam da je to jedan način da to zamislimo...

I onda možete reći,

pomeri broj na desno... nazvaću to tako...

pomeri broj desno, na mesto...

pisaćemo to na ovaj način...

pomeri broj na mestu i desno na mesto *i + 1*

A onda ovde, mi pomeramo...

pomerimo vrednost levo na mesto i.

I tako, ako se sećate šta smo radili
u prethodnom snimku,

to tačno opisuje ovo.

Mi poredimo value sa onim što mu je sa leve strane.

Ako je manje od njega,

onda bez obzira na broj koji se nalazi na
mestu s njegove leve strane,

pomeri ga na desno i onda pomeri value na levo.

A sada hajde da uporedimo value

sa nečim što je manje od njega.

Želimo da dekrementiramo i, želimo da ga smanjimo...

dekrementiranje je u stvari inkrementiranje na dole.

Tako da će i postati jednako *i - 1*,

a onda ćemo izvršiti petlju ponovo.

I sada će value biti upoređeno...

sada je i za dva levo od index...

u poređenju s tim...

ako je manje od toga, pomeri ga na desno

i pomeri value ponovo na levo.

A sada, šta ako imamo situaciju

gde value nije manje od

elementa sa kojim ga poredite?

Pa, ako nije manje od elementa sa kojim ga poredite,

to znači da je value već sada na pravom mestu.

To takođe znači da ste završili,

i da ne morate dalje da pomerate value na levo.

I ne morate više da pomerate stvari na levo

niti na desno.

Tako da - završili smo.

i mislim da bi ovo trebalo da radi

osim ako sam napravio neku blesavu grešku.

Dakle, hajde da probamo da vidimo da li bi mogao da...

da li ovo zapravo radi kao algoritam za sortiranje.

Sačuvaću to, insertion_sort,

i pokrenuti.

Dobro, dakle nisam imao nikakvih,
barem ne sintaksnih, grešaka.

Sintaksa samo znači da su karakteri koje sam koristio...

nisam zaboravio da stavim zarez ovde ili znak veće...

u suštini, uspeo je da obradi ovo,

da interpretira sve ovo ovde.

Ali hajde da vidimo da li to zapravo radi.

Definisaću listu a.

Recimo [7, 1, 3, 5, 9, 2]

i dodaću još jedno 3 ovde.

To je dakle a.

Onda hajde da vidimo... ovo je trenutak istine.

insertion_sort(a), hajde da vidimo šta se dešava.

I zapamtite, mi sortiramo u mestu,

ova funkcija ne vraća ništa.

Ali bi trebala da uzme listu kakva god da je,

i da joj izmeni sve elemente

tako da sada budu poređani po veličini.

Ovo je dakle momenat istine.

Hajde da vidimo na šta a liči.

Eto ga! Sortirano je.

Dakle, mislim da nisam napravio nikakve velike greške.

I to vam je to.

Imate verziju sortiranja umetanjem.