Domů » Informatika » Algoritmus » Řadící algoritmus » Selection Sort (řazení výběrem)

Selection Sort (řazení výběrem)

Selection Sort je základní řadící algoritmus, velmi jednoduchý na pochopení i implementaci. Na začátku řazení se celé pole považuje za neseřazenou část. Jedním průchodem neseřazenou částí je nalezeno minimum, které se prohodí s prvek na začátku neseřazené části. Po této operaci je neseřazená část kratší o jeden prvek a algoritmus pokračuje stejným způsobem dál až na konec pole. Řadící algoritmus selection sort je nepřirozený, nestabilní a jeho asymptotická složitost je € O(n^2) €.

Implementace (Java)

kód v jazyce Java - Zobrazit

  1. /**
  2.  * Implementace algoritmu selection sort.
  3.  * @param input vstupní pole
  4.  * @author Vojtěch Hordějčuk
  5.  */
  6. public static <T extends Comparable<? super T>> void selectionSort(final T[] input)
  7. {
  8.   for (int i = 0; i < input.length; i++)
  9.   {
  10.     // 'i' je počáteční index neseřazené části pole
  11.     // nejdřív si jako minimum vezmi to první co najdeš
  12.     // (třeba tam nic menšího už není)
  13.  
  14.     int indexOfMinimum = i;
  15.  
  16.     // projdi zbytek pole
  17.  
  18.     for (int j = i + 1; j < input.length; j++)
  19.     {
  20.       // 'j' je počáteční index části pole, ve které hledám menší číslo
  21.  
  22.       if (input[j].compareTo(input[indexOfMinimum]) == -1)
  23.       {
  24.         // bylo nalezeno menší číslo, zapamatuj si jeho index
  25.  
  26.         indexOfMinimum = j;
  27.       }
  28.     }
  29.  
  30.     // pokud je třeba, prohoď začátek neseřazené části s minimem
  31.  
  32.     if (i != indexOfMinimum)
  33.     {
  34.       final T temp = input[i];
  35.       input[i] = input[indexOfMinimum];
  36.       input[indexOfMinimum] = temp;
  37.     }
  38.   }
  39. }

Ukázkový běh

Pole Operace
5 2 3 9 1 Toto pole chceme seřadit.
5 2 3 9 (1) Nalezené minimum je 1, prohodíme s 5.
1 2 3 9 5 Jeden prvek je seřazen.
1 (2) 3 9 5 Nalezené minimum je 2. Nic neprohodíme.
1 2 3 9 5 Dva prvky jsou seřazeny.
1 2 (3) 9 5 Nalezené minimum je 3. Nic neprohodíme.
1 2 3 9 5 Tři prvky jsou seřazeny.
1 2 3 9 (5) Nalezené minimum je 5, prohodíme s 9.
1 2 3 5 9 Čtyři prvky jsou seřazeny.
1 2 3 5 9 Dojeli jsme na poslední prvek, pole je seřazeno.