Sortowanie przez wybieranie
Sortowanie przez wybieranie to jedna z prostszych metod sortowania, charakteryzująca się złożonością O(n²). Algorytm działa poprzez wyszukiwanie elementu, który ma znaleźć się na określonej pozycji, i zamianę go z aktualnie znajdującym się tam elementem. Proces ten powtarza się dla wszystkich indeksów tablicy.
Algorytm
Podstawowe kroki algorytmu są następujące:
- Wyszukaj minimalną wartość w tablicy od pozycji
ido końca tablicy. - Zamień wartość minimalną z elementem na pozycji
i.
Alternatywnie, można wyszukiwać maksymalną wartość, co posortuje tablicę w porządku malejącym. Algorytm jest niestabilny.
Przykład
Dla tablicy [9, 1, 6, 8, 4, 3, 2, 0], algorytm wyszukuje wartości minimalne i sortuje ją na końcu do [0, 1, 2, 3, 4, 6, 8, 9]. Można przyspieszyć ten proces, jednocześnie wyszukując minimum i maksimum z obu końców tablicy.
Implementacja w różnych językach
C++
void selection_sort(int n, int t[]) {
for(int i = 0; i < n; i++) {
int k = i;
for(int j = i + 1; j < n; j++)
if(t[j] < t[k]) k = j;
swap(t[k], t[i]);
}
}
Ruby
def wsort(list)
for i in 0...(list.size - 1)
min = i
for j in (i + 1)...(list.size)
if list[j] <= list[min]
min = j
end
list[i], list[min] = list[min], list[i]
end
return list
end
PHP
function selection_sort($tab) {
$n = count($tab);
for($j = 0; $j < $n - 1; $j++) {
$pmin = $j;
for($i = $j + 1; $i < $n; $i++) {
if($tab[$i] < $tab[$pmin]) {
$pmin = $i;
}
}
$x = $tab[$pmin];
$tab[$pmin] = $tab[$j];
$tab[$j] = $x;
}
return $tab;
}
JavaScript
function selectionSort(array) {
for (var i = 0; i < array.length - 1; i++) {
var min = i;
for (var j = i + 1; j < array.length; j++) {
if (array[j] < array[min]) {
min = j;
}
}
if (min !== i) {
[array[i], array[min]] = [array[min], array[i]];
}
}
}
