Indexvektoros rendezés (algoritmus)

A Programozás Wiki wikiből

Lényegében arról van szó,hogy a rendezendő tömb elemeit nem mozgatjuk,hanem a tömbhöz egy index vektort rendelünk, melyben a tömb elemeire mutató indexek a tömb rendezettségének megfelelően követik egymást. Az eljárás során az indextömb elemeit az indexelt adatok rendezettségének függvényében sorba rakjuk. A hasonlítást tehát mindig az indexelt adatokra végezzük el, de csere esetén csak az indexeket cseréljük. Így az eredeti tömbünk változatlan maradhat.

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

Pascal[szerkesztés]

{pascal példa}
Program IndexVektor;
Uses Crt;
Const n = 5;
Var nevek:Array[1..n]Of String[10];
    indx :Array[1..n]Of 1..n;
    i,j,min,s:Byte;
Begin
  ClrScr;
  WriteLn('Kerem a rendezendo neveket: ');
  For i:=1 To n Do Begin
    ReadLn(nevek[i]);
  End;
  {indexvektoros minimumkiválasztásos rendezés}
  For i:=1 To n Do Begin
    indx[i]:=i;
  End;
  For i:=1 To n-1 Do Begin
    min:=i;
    For j:=i+1 To n Do Begin
      If nevek[indx[j]] < nevek[indx[min]] Then  min:=j;
      If i <> min Then Begin
        s:=indx[i];
        indx[i]:=indx[min];
        indx[min]:=s;
      End;
    End;
  End;
  WriteLn('A nevek rendezetten: ');
  For i:=1 To n Do Begin
    WriteLn(nevek[indx[i]]);
  End;
  WriteLn('A nevek rendezetlenul: ');
  For i:=1 To n Do Begin
    WriteLn(nevek[i]);
  End;
  ReadLn;
End.

Go[szerkesztés]

func rendez(arr []int) []int {
        n := len(arr)
        indx := make([]int,n)
        for i:=0; i<n; i++ {
                indx[i] = i
        }
        for i:=0; i<n-1; i++ {
                min := i
                for j:=i+1; j<n; j++ {
                        if arr[indx[j]] < arr[indx[min]] {
                                min = j
                        }
                }
                if i != min {
                        indx[i],indx[min] = indx[min],indx[i]
                }
        }
        return indx
}