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;
PDF
– Pavel Mička
Zakladatel a administrátor stránek Algoritmy.net
Hodnocení (4): 4,75

Přečtěte si také

Diskuse





Pavel Mička21.8.2011
> JohnyD

Ahoj, patrně máš v systému nastaven jako výchozí monotype font něco, co nemá písmeno "ď"... čili na systémech, kde je font, který má všechna písmena, by to mělo fungovat. Tuto "chybu" opravovat nebudu, protože bych musel odstranit diakritiku i z článků (jsou i sans-serif písma bez háčků).

Tj. chyba je na přijímači :-).
JohnyD21.8.2011
To ď v prohoď bych předělal na d, takle je tam obdélníček.