Urejanje z izbiranjem/Navadno izbiranje

Iz MaFiRaWiki

Vsebina

1 Opis algoritma
2 Algoritem
3 Primer
4 Implementacija
5 Glej tudi
6 Viri in literatura

Navadno izbiranje ali selection sort je enostavna metoda za urejanje manjšega števila podatkov v tabeli, ko enostavnost kode prevlada nad slabšo učinkovitostjo. Časovna zahtevnost metode je O(n²).

Tabela podatkov je v vsakem trenutku razdeljena na dva dela: prvi del je urejen, drugi del je neurejen. Na začetku so vsi elementi v neurejenem delu, urejeni del je prazen. Metoda temelji na iskanju oziroma izbiranju najmanjšega elementa v neurejenem delu in premeščanju le-tega na prvo mesto v tem delu. S tem se na vsakem koraku število elementov v urejenem delu poveča za 1.

[spremeni]

Opis algoritma

Najdi najmanjši element in ga zamenjaj s prvim elementom.
Med ostalimi elementi najdi drugi najmanjši element in ga zamenjaj z drugim elementom.
Korake ponavljaj do predzadnjega elementa polja.

[spremeni]

Algoritem

Pomen spremenljivk:

n ...... število elementov v tabeli
a[i] ... element v tabeli a, kjer je 0<=i<=n
k, j ... pomožna števca
min .... vrednost trenutno najmanjšega elementa

for i = 0 to n-2 do
 min = a[i]
 k = i
 for j = i + 1 to n-1 do
  if (a[j] > min) then
   min = a[j]
   k = j
  end_if
 end_for
 a[k] = a[i]
 a[i] = min
end_for

[spremeni]

Primer

Podano tabelo uredimo z navadnim izbiranjem.

44	55	12	42	94	18	6	67

Korak, i = 0:
Primerjamo vse elemente tabele s prvim elementom (indeks 0). Najdemo najmanjšega, to je 6 in ju zamenjamo. Dobimo:

6 55 12 42 94 18 44 67
Korak, i = 1:
Vzamemo drugi element (indeks 1) in primerjamo vse elemente za njim. Najdemo najmanjšega, to je 12 in ju zamenjamo. Dobimo:

6 12 55 42 94 18 44 67
Korak, i = 2:
Vzamemo tretji element (indeks 2) in primerjamo vse elemente za njim. Najdemo najmanjšega, to je 18 in ju zamenjamo. Dobimo:

6 12 18 42 94 55 44 67
Korak, i =3:
Vzamemo četrti element (indeks 3) in primerjamo vse elemente za njim. Ko pregledamo ostale elemente, vidimo da je ta že najmanjši. Dobimo:

6 12 18 42 94 55 44 67
Korak, i = 4:
Vzamemo peti element (indeks 4) in primerjamo vse elemente za njim. Najdemo najmanjšega, to je 44 in ju zamenjamo. Dobimo:

6 12 18 42 44 55 94 67
Korak, i = 5:
Vzamemo šesti element (indeks 5) in primerjamo vse elemente za njim. Ko pregledamo ostale elemente, vidimo da je ta že najmanjši. Dobimo:

6 12 18 42 44 55 94 67
Korak, i = 6:
Vzamemo peti element (indeks 6) in ga primerjamo z zadnjim elementom. Ker je ta manjši, ju zamenjamo. Dobimo urejeno tabelo:

6 12 18 42 44 55 67 94