Selection sort

Selection sort je jednoduchý nestabilný triediaci algoritmus so zložitosťou O(n^2). V porovnaní s ďalšími kvadratickými algoritmami je selection sort všeobecne rýchlejší než bubble sort, avšak pomalší než insertion sort. Výhodou selection sortu oproti algoritmom s asymptotickou zložitosťou O(n * log n) (quick sort, merge sort, heap sort) je jeho konštantná pamäťová zložitosť.

 Algoritmus 
Kódy algoritmov v rôznych jazykoch:

 Java 
 public static void selectionSort(int[] array)
 {
     for (int i = 0; i < array.length - 1; i++) {
         int maxIndex = i;
         for (int j = i + 1; j < array.length; j++) {
             if (array[j] < array[maxIndex]) maxIndex = j;
         }
         int tmp = array[i];
         array[i] = array[maxIndex];
         array[maxIndex] = tmp;
     } 
 }

 C++ 
 void selectionSort(int array[], int size)
 {
     for (int i = 0; i < size - 1; i++) {
         int maxIndex = i;
         for (int j = i + 1; j < size; j++) {
             if (array[j] < array[maxIndex]) maxIndex = j;
         }
         int tmp = array[i];
         array[i] = array[maxIndex];
         array[maxIndex] = tmp;
     } 
  }

 C# 
 public static void SelectionSort(int[] array)
 {
    for (int i = 0; i < array.Length - 1; i++)
    {
        int maxIndex = i;
        for (int j = i + 1; j < array.Length; j++)
        {
            if (array[j] < array[maxIndex]) maxIndex = j;
        }
        int tmp = array[i];
        array[i] = array[maxIndex];
        array[maxIndex] = tmp;
    }
 }

 Pascal 
 procedure SelectSort(var X : ArrayType; N : integer);
 var
  I,
  J,
  K,
  Y : integer;
 begin
  for I := 1 to N - 1 do
    begin
      K := I;
      Y := X[I];
      for J := I + 1 to N do
        if X[J] < Y then
          begin
            K := J;
            Y := X[J]
          end;
      X[K] := X[J];
      X[I] := Y;
    end
 end;

Kategória:Triediacie algoritmy