Odabir Sortiraj: Algoritam objašnjen uz Python Primjer koda

Što je odabir sortiranja?

ODABIR SORT je algoritam usporednog sortiranja koji se koristi za sortiranje nasumičnog popisa stavki uzlaznim redoslijedom. Usporedba ne zahtijeva puno dodatnog prostora. Zahtijeva samo jedan dodatni memorijski prostor za vremensku varijablu.

To je poznato kao na mjestu sortiranje. Sortiranje odabira ima vremensku složenost od O(n²) gdje je n ukupan broj stavki na listi. Vremenska složenost mjeri broj ponavljanja potrebnih za sortiranje popisa. Popis je podijeljen u dvije particije: prvi popis sadrži sortirane stavke, dok drugi popis sadrži nesortirane stavke.

Prema zadanim postavkama sortirani popis je prazan, a nesortirani popis sadrži sve elemente. Nesortirani popis se zatim skenira za najmanju vrijednost, koja se zatim stavlja na sortirani popis. Ovaj se postupak ponavlja dok se sve vrijednosti ne usporede i razvrstaju.

Kako funkcionira selekcijsko sortiranje?

Prva stavka u nesortiranoj particiji uspoređuje se sa svim vrijednostima na desnoj strani kako bi se provjerilo je li to minimalna vrijednost. Ako to nije minimalna vrijednost, tada se njegov položaj mijenja s minimalnom vrijednošću.

Primjer

• Na primjer, ako je indeks minimalne vrijednosti 3, tada je vrijednost elementa s indeksom 3 smještena na indeks 0, dok je vrijednost koja je bila na indeksu 0 smještena na indeks 3. Ako je prvi element u nesortiranoj particiji minimalnu vrijednost, zatim vraća svoje pozicije.
• Element koji je određen kao minimalna vrijednost tada se premješta u particiju na lijevoj strani, koja je sortirani popis.
• Particionirana strana sada ima jedan element, dok nepodijeljena strana ima (n – 1) elemenata gdje je n ukupan broj elemenata na listi. Ovaj se postupak ponavlja iznova i iznova dok se sve stavke ne usporede i razvrstaju na temelju njihovih vrijednosti.

Definicija problema

Popis elemenata koji su poredani nasumičnim redoslijedom potrebno je poredati uzlaznim redoslijedom. Razmotrite sljedeći popis kao primjer.

[21,6,9,33,3]

Gornji popis treba sortirati kako bi se dobili sljedeći rezultati

[3,6,9,21,33]

Rješenje (Algoritam)

Korak 1) Dobijte vrijednost n koja je ukupna veličina niza

Korak 2) Podijelite popis na sortirane i nesortirane dijelove. Razvrstani odjeljak u početku je prazan, dok nerazvrstani odjeljak sadrži cijeli popis

Korak 3) Odaberite minimalnu vrijednost iz neparticioniranog odjeljka i smjestite je u sortirani odjeljak.

Korak 4) Ponovite postupak (n – 1) puta dok se svi elementi na popisu ne poredaju.

Vizualno predstavljanje

S obzirom na popis od pet elemenata, sljedeće slike ilustriraju kako algoritam sortiranja odabirom ponavlja vrijednosti prilikom njihovog sortiranja.

Sljedeća slika prikazuje nerazvrstani popis

Korak 1)

Prva vrijednost 21 se uspoređuje s ostalim vrijednostima kako bi se provjerilo je li to minimalna vrijednost.

3 je minimalna vrijednost, tako da su pozicije 21 i 3 zamijenjene. Vrijednosti sa zelenom pozadinom predstavljaju sortiranu particiju popisa.

Korak 2)

Vrijednost 6 koja je prvi element u nesortiranoj particiji uspoređuje se s ostalim vrijednostima kako bi se otkrilo postoji li niža vrijednost

Vrijednost 6 je minimalna vrijednost, tako da zadržava svoju poziciju.

Korak 3)

Prvi element nesortiranog popisa s vrijednošću 9 uspoređuje se s ostalim vrijednostima kako bi se provjerilo je li to minimalna vrijednost.

Vrijednost 9 je minimalna vrijednost, tako da zadržava svoju poziciju u sortiranoj particiji.

Korak 4)

Vrijednost 33 se uspoređuje s ostalim vrijednostima.

Vrijednost 21 niža je od 33, pa su pozicije zamijenjene kako bi se proizveo gornji novi popis.

Korak 5)

Imamo samo jednu preostalu vrijednost na nepodijeljenom popisu. Stoga je već sortirano.

Konačna lista je kao ona prikazana na gornjoj slici.

Program odabira sortiranja pomoću Python 3

Sljedeći kod prikazuje implementaciju odabira sortiranja pomoću Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Pokretanje gornjeg koda daje sljedeće rezultate

[3, 6, 9, 21, 33]

Objašnjenje koda

Objašnjenje koda je sljedeće

Evo objašnjenja koda:

1. Definira funkciju pod nazivom selectionSort
2. Dobiva ukupan broj elemenata na popisu. Ovo nam je potrebno kako bismo odredili broj prolaza koje treba napraviti prilikom uspoređivanja vrijednosti.
3. Vanjska petlja. Koristi petlju za ponavljanje kroz vrijednosti popisa. Broj ponavljanja je (n – 1). Vrijednost n je 5, tako da (5 – 1) daje 4. To znači da će vanjske iteracije biti izvedene 4 puta. U svakoj iteraciji, vrijednost varijable i dodjeljuje se varijabli minValueIndex
4. Unutarnja petlja. Koristi petlju za usporedbu krajnje lijeve vrijednosti s ostalim vrijednostima na desnoj strani. Međutim, vrijednost za j ne počinje s indeksom 0. Počinje s (i + 1). Ovo isključuje vrijednosti koje su već sortirane tako da se fokusiramo na stavke koje još nisu sortirane.
5. Pronalazi minimalnu vrijednost na nesortiranom popisu i postavlja je na odgovarajuće mjesto
6. Ažurira vrijednost minValueIndex kada je uvjet zamjene istinit
7. Uspoređuje vrijednosti indeksnih brojeva minValueIndex i i da vidi jesu li jednaki
8. Krajnja lijeva vrijednost pohranjuje se u vremenskoj varijabli
9. Niža vrijednost s desne strane zauzima prvo mjesto
10. Vrijednost koja je bila pohranjena u vremenskoj vrijednosti pohranjena je na poziciji koju je prethodno držala minimalna vrijednost
11. Vraća sortirani popis kao rezultat funkcije
12. Stvara popis el koji ima nasumične brojeve
13. Ispišite sortirani popis nakon poziva funkcije Sortiranje odabira prosljeđujući el kao parametar.

Vremenska složenost odabira sortiranja

Složenost sortiranja koristi se za izražavanje broja vremena izvršenja koje je potrebno za sortiranje popisa. Implementacija ima dvije petlje.

Vanjska petlja koja odabire vrijednosti jednu po jednu s popisa izvodi se n puta, gdje je n ukupan broj vrijednosti na popisu.

Unutarnja petlja, koja uspoređuje vrijednost iz vanjske petlje s ostalim vrijednostima, također se izvršava n puta gdje je n ukupan broj elemenata na listi.

Stoga je broj izvršenja (n * n), što se također može izraziti kao O(n²).

Sortiranje odabira ima tri kategorije složenosti, naime;

• Najgori slučaj – ovdje je navedeni popis u silaznom redoslijedu. Algoritam izvodi maksimalan broj izvršenja koji se izražava kao [Big-O] O(n²)
• Najbolji slučaj – ovo se događa kada je navedeni popis već sortiran. Algoritam izvodi minimalni broj izvršenja koji se izražava kao [Big-Omega] ?(n²)
• Prosječan slučaj – ovo se događa kada je popis nasumičan. Prosječna složenost se izražava kao [Big-theta] ?(n²)

Sortiranje odabira ima prostornu složenost O(1) jer zahtijeva jednu vremensku varijablu koja se koristi za zamjenu vrijednosti.

Kada koristiti selekcijsko sortiranje?

Razvrstavanje odabira najbolje je koristiti kada želite:

• Morate poredati mali popis stavki uzlaznim redoslijedom
• Kada je trošak zamjene vrijednosti beznačajan
• Također se koristi kada morate biti sigurni da su sve vrijednosti na popisu provjerene.

Prednosti odabira sortiranja

Sljedeće su prednosti selekcije

• Vrlo dobro radi na malim listama
• To je algoritam na mjestu. Ne zahtijeva puno prostora za sortiranje. Za držanje vremenske varijable potreban je samo jedan dodatni prostor.
• Dobro radi na stavkama koje su već sortirane.

Nedostaci selekcijskog sortiranja

Sljedeći su nedostaci selekcije.

• Loše radi na velikim popisima.
• Broj ponavljanja učinjenih tijekom sortiranja je n-kvadrat, gdje je n ukupan broj elemenata na listi.
• Drugi algoritmi, kao što je brzo sortiranje, imaju bolju izvedbu u usporedbi s selekcijskim sortiranjem.

Rezime

• Sortiranje odabirom algoritam je usporedbe na mjestu koji se koristi za sortiranje nasumičnog popisa u uređeni popis. Ima vremensku složenost od O(n²)
• Popis je podijeljen u dva dijela, sortirani i nesortirani. Najmanja vrijednost bira se iz nesortiranog odjeljka i stavlja u sortirani odjeljak.
• Ovo se ponavlja dok se sve stavke ne razvrstaju.
• Implementacija pseudokoda u Python 3 uključuje korištenje dvije for petlje i if naredbe za provjeru je li zamjena potrebna
• Vremenska složenost mjeri broj koraka potrebnih za sortiranje popisa.
• Vremenska složenost u najgorem slučaju događa se kada je popis u silaznom redoslijedu. Ima vremensku složenost [Big-O] O(n²)
• Vremenska složenost u najboljem slučaju događa se kada je popis već u uzlaznom redoslijedu. Ima vremensku složenost [Big-Omega] ?(n²)
• Složenost prosječnog slučaja događa se kada je popis nasumičan. Ima vremensku složenost [Big-theta] ?(n²)
• Razvrstavanje odabirom najbolje je koristiti kada imate mali popis stavki za sortiranje, cijena zamjene vrijednosti nije važna, a provjera svih vrijednosti je obavezna.
• Sortiranje odabira ne funkcionira dobro na velikim popisima
• Drugi algoritmi sortiranja, kao što je brzo sortiranje, imaju bolje performanse u usporedbi s sortiranjem odabirom.