level: Level 2 - Selection sort
Questions and Answers List
Selection sort
level questions: Level 2 - Selection sort
Question | Answer |
---|---|
Što je sortiranje? | Postupak kojim se neka kolekcija elemenata uređuje tako da se elementi poredaju po nekom kriteriju. |
Kako se obično radi sortiranje elemenata numeričkih nizova? | Obično se uređuje od manjeg prema većim elementima. |
Kako se obično radi sortiranje elemenata nizova stringova? | Red elemenata određuje se prema leksikografskom rasporedu. |
Koja je ideja selection sorta? | Odaberemo najmanji (ili najveći) element niza te da ga zamijenimo s prvim elementom niza. |
Kako radi selection sort nakon prve zamjene elemenata niza? | Promatramo sve elemente niza osim tog prvog, stalno smanjujući podniz kojeg promatramo dok ne dođemo do posljednjeg elementa koji bi trebao biti najveći (ili najmanji) element niza. |
Koliko elemenata u nizu pretražujemo pomoću selection sorta, gledajući po koracima? | U prvom koraku pretražujemo sve elemente u nizu (N), u drugom koraku pretražujemo N-1 elemente itd. do N-tog koraka gdje pretražujemo samo jedan element. |
Kolika je složenost selection sort algoritma? | Kvadratna, O(N^2). |
Koja je glavna razlika bubble sorta i selection sorta? | Bubble sort zamjenjuje susjedne elemente, ako su oni u krivom poretku (ako je prvi broj manji od drugoga, zamijenit će ih), dok selection sort sortira niz tražeći najmanji element nesortiranog niza te ga stavlja na početak. |
Koji sort je brži i efikasniji: selection sort ili bubble sort? | Selection sort. |
Kako radi algoritam za selection sort? | Uzima najmanju vrijednost (ako niz svrstavamo silazno) u listi i stavlja ju na odgovarajuće mjesto u listi. |
Kako u Pythonu implementiramo selection sort? | Pomoću 3 pokazivača: 1) na ključni element (i) 2) na indeks najmanjeg elementa u trenutnom prolazu (k) 3) na element s kojim uspoređujemo najmanji element trenutnog prolaza (j) |
Čemu na početku svakog prolaza u mora biti jednak indeks najmanjeg elementa kroz algoritam selection sorta? | Indeksu ključnog elementa za taj prolaz. |
Što u prvom prolazu predstavlja prvi element? | Smatramo ga sortiranim i najmanjim - tj. minimumom, te se uspoređuje sa svim ostalim elementima. |
Selection sort algoritam dijeli uneseni niz u ... | dva dijela |
Na koja 2 dijela selection sort dijeli uneseni niz? | Podniz elemenata koji su već sortirani, i podniz preostalih elemenata. |
Pseudokod za selection sort | - ulaz je nesortirana lista a1, , ......, an, izlaz je sortirana lista 1. za i = 1, 2, n-1 radi korake 2 - 5 2. min = i 3. za j = i, … , n radi korak 4 4. ako je aj < aminmin = j 5. zamijeni (ai, , amin) |
Koje sortove smatramo poboljšanim inačicama selection sorta? | 1. Heap sort - sortiranje pomoću hrpe. 2. Patience sort 3. Smoothsort 4. Strand sort |
Koji je hrvatski naziv za selection sort? | Sortiranje izborom |