Urejanje z izbiranjem/Navadno izbiranje

Iz MaFiRaWiki

Vsebina


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(n2).

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.

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.

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

Primer

Podano tabelo uredimo z navadnim izbiranjem.

44 55 12 42 94 18 6 67

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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

Implementacija

Glej tudi

Viri in literatura

Osebna orodja