Reklama

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.

Reklama

Algorytm

Podstawowe kroki algorytmu są następujące:

Wyszukaj minimalną wartość w tablicy od pozycji i do 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.

Reklama

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.

Reklama

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]];
        }
    }
}