Selection sort

Selection sort (řazení výběrem) je jednoduchý nestabilní řadící algoritmus se složitostí O(n^{2}). V porovnání s dalšími kvadratickými algoritmy je selection sort v obecném případě rychlejší než bubble sort, avšak pomalejší než insertion sort. Výhodou selection sortu oproti algoritmům s asymptotickou složitostí O(n\\cdot \\log{n}) (quicksort, merge sort, heapsort) je jeho konstantní paměťová složitost.

Princip

Selection sort vychází z myšlenky, že pokud řadíme pole od největšího prvku k nejmenšímu, tak první bude nejvyšší prvek, za ním nejvyšší prvek ze zbytku pole atd., čili stačí pouze postupně vybírat nejvyšší prvky z neseřazené části pole a umísťovat je na konec seřazené části.


Příklad

(3 2 8 7 6) // zadání pole, řaďmě od největšího k nejmenšímu
(3 2 8 7 6) // nejvyšší číslo je 8, prohoďme ho tedy s číslem 3 na indexu 0
(8 2 3 7 6) // nejvyšší číslo je 7, prohoďme ho tedy s číslem 2 na indexu 1
(8 7 3 2 6) // nejvyšší číslo je 6, prohoďme ho tedy s číslem 3 na indexu 2
(8 7 6 2 3) // nejvyšší číslo je 3, prohoďme ho tedy s číslem 2 na indexu 3
(8 7 6 3 2) // seřazeno

Vizualizace


Kód

    function selectionSort(array a)
        for i in 0 -> a.length - 2 do
            maxIndex = i
            for j in (i + 1) -> (a.length - 1) do
                if a[j] > a[maxIndex]
                    maxIndex = j
            prohoď(a[i], a[maxIndex])
   /**
    * Razeni vyberem (od nejvyssiho)
    * @param array pole k serazeni
    */
    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;
        } 
    }
/**
 * Razeni vyberem (od nejvyssiho)
 * @param array pole k serazeni
 * @param size velikost pole
 */
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;
     } 
 }
        /**
         * Razeni vyberem (od nejvyssiho)
         * @param array pole k serazeni
         */
        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;
            }
        }
  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;







Doporučujeme