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.

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

Go[szerkesztés]

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]
        }
}




ANSI C[szerkesztés]

void csere(int* a, int* b) {
   /* a kivalasztasos_rendezes fuggvenybe beagyazva ezt a kodot hatekonyabb lenne a program, de igy szemleletesebb */
   int tmp = *a;
   *a = *b;
   *b = tmp;
}

void kivalasztasos_rendezes(int* tomb, int size){

	int i, j;
	for(i = 0; i<n; i++){
		int idx_of_min_item = i;
		for(j= i + 1; j<n; j++){
			if(tomb[j] < tomb[idx_of_min_item])
				idx_of_min_item= j;
		}
		csere(&tomb[i], &tomb[idx_of_min_item]);
	}
 }




Java[szerkesztés]

/**
tomb: int-ekbol allo tomb.
*/

public static void kivalasztasosRendezes(int[] tomb) {
    int idMin;
    for (int i = 0; i < tomb.length; i++) {
      idMin = i;
      for (int j = i + 1; j < tomb.length; j++) {
        if (tomb[j] < tomb[idMin]) {
          idMin = j;
        }
      }

      /*Az elemek megcsereleset a kovetkezo 3 sor vegzi el*/
      /*Ez helyettesitheto egy 2 int tipusu tömbelem megcsereleset elvegzo csere() fuggvennyel is*/
      int tmp = tomb[i];
      tomb[i] = tomb[idMin];
      tomb[idMin] = tmp;
    }
  }

Python[szerkesztés]

def kivalasztasos_rendezes(tomb):
   for i, item_at_i in enumerate(tomb):
      min_index = i
      min_value = item_at_i
      for j, item_at_j in enumerate(tomb[i+1:],i+1):
         if item_at_j < min_value:
            min_index = j
            min_value = item_at_j
      tomb[i] = min_value
      tomb[min_index] = item_at_i