DAA - Sortowanie przez wybór

Ten typ sortowania nosi nazwę Selection Sortjak to działa poprzez wielokrotne sortowanie elementów. Działa to w następujący sposób: najpierw znajdź najmniejszy w tablicy i zamień go z elementem na pierwszej pozycji, następnie znajdź drugi najmniejszy element i zamień go z elementem na drugiej pozycji i kontynuuj w ten sposób aż cała tablica będzie posortowane.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

Sortowanie przez wybieranie należy do najprostszych technik sortowania i działa bardzo dobrze w przypadku małych plików. Ma dość ważne zastosowanie, ponieważ każdy element jest przenoszony najwyżej raz.

Sortowanie sekcji jest metodą z wyboru do sortowania plików z bardzo dużymi obiektami (rekordami) i małymi kluczami. Najgorszy przypadek ma miejsce, gdy tablica jest już posortowana w porządku malejącym i chcemy posortować je w kolejności rosnącej.

Niemniej jednak czas wymagany przez algorytm sortowania przez wybór nie jest bardzo wrażliwy na pierwotną kolejność sortowanej tablicy: test, jeśli A[j] < min x jest wykonywany dokładnie tyle samo razy w każdym przypadku.

Sortowanie przez wybór spędza większość czasu na próbach znalezienia minimalnego elementu w nieposortowanej części tablicy. Wyraźnie pokazuje podobieństwo między sortowaniem przez wybór i sortowaniem bąbelkowym.

Sortowanie bąbelkowe wybiera maksymalną liczbę pozostałych elementów na każdym etapie, ale marnuje trochę wysiłku, nadając porządek nieposortowanej części tablicy.
Sortowanie przez wybór jest kwadratowe zarówno w najgorszym, jak i przeciętnym przypadku, i nie wymaga dodatkowej pamięci.

Dla każdego i z 1 do n - 1, jest jedna wymiana i n - i porównań, więc jest w sumie n - 1 wymiany i

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 porównania.

Te obserwacje są prawdziwe, bez względu na dane wejściowe.

W najgorszym przypadku może to być kwadrat, ale w przeciętnym przypadku jest to wielkość O(n log n). Oznacza to, żerunning time of Selection sort is quite insensitive to the input.

Realizacja

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}