Kiválasztásos rendezés (algoritmus)

A Programozás Wiki wikiből

A kiválasztásos rendezés egy egyszerű, négyzetes időben futó rendezési algoritmus. Az alapötlet az, hogy kiválasztjuk a rendezendő tömb legkisebb elemét, és kicseréljük a tömb legelső elemével. Ezzel a tömb első eleme megkapta a végső értékét, és a feladat egyszerűsödött a tömb maradékának rendezésére. Az algoritmust addig ismételjük a maradék tömbön, amíg csak egy elem marad.

Pszeudokódban:

 for i in 1..hossz(tömb)-1 do   // az i. elem lesz a rendezendő résztömb első eleme
    minindex := i;
    for j in i+1..hossz(tömb) do   // minimum kiválasztás ciklusa
       if tömb[j]<tömb[minindex] then
          minindex := j;
       end;
    end;
    csere(tömb[i], tömb[minindex]);
 end;

Mint látható, a tömböt mindig ugyanannyiszor olvassuk és írjuk, a benne levő adatoktól függetlenül. (Az adatoktól egyedül az függ, hogy hányszor változik a minindex értéke.) Azt is könnyű belátni, hogy az összehasonlítások száma (n-1)+(n-2)+...+1 = n*(n-1)/2, vagyis a futási idő tényleg négyzetes.

A kiválasztásos rendezés általában lassabb a közvetlen beszúrásos rendezésnél, de a konzisztens futásideje bizonyos esetekben előnyt jelenthet (pl. valós idejű alkalmazások esetén). Nagyobb adathalmaz rendezéséhez érdemesebb a bonyolultabb, de gyorsabb algoritmusokat (gyorsrendezést vagy összefésülő rendezést) használni.

[szerkesztés] Megvalósítás különböző nyelveken

[szerkesztés] Go

func kiv_rend(arr *[]int) {
        n := len(*arr)
        for i:=0; i<n; i++ {
                min := i
                for j:=i+1; j<n; j++ {
                        if (*arr)[j] < (*arr)[min] {
                                min = j
                        }
                }
                (*arr)[i],(*arr)[min] = (*arr)[min],(*arr)[i]
        }
}