Sortowanie przez wybieranie
Przykład działania sortowania przez wybieranie | |
Rodzaj | Sortowanie |
---|---|
Struktura danych | Tablica, lista |
Złożoność | |
Czasowa |
|
Sortowanie przez wybieranie – jedna z prostszych metod sortowania o złożoności O(n2). Polega na wyszukaniu elementu mającego się znaleźć na żądanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.
Algorytm przedstawia się następująco:
- wyszukaj minimalną wartość z tablicy spośród elementów od
i
do końca tablicy - zamień wartość minimalną, z elementem na pozycji
i
Gdy zamiast wartości minimalnej wybierana będzie maksymalna, wówczas tablica będzie posortowana od największego do najmniejszego elementu.
Algorytm jest niestabilny. Przykładowa lista to: [2a,2b,1] → [1,2b,2a] (gdzie 2b=2a)
Przykład
Posortowana zostanie tablica 8-elementowa [9,1,6,8,4,3,2,0]. W tablicy pogrubione zostaną te elementy wśród których wyszukuje się wartość minimalną.
element tablicy (wartość | tablica | wartość najmniejszego elementu tablicy (z części nieposortowanej) |
---|---|---|
0 | [9,1,6,8,4,3,2,0] | 0 |
1 | [0,1,6,8,4,3,2,9] | 1 (element znajduje się na właściwej pozycji) |
2 | [0,1,6,8,4,3,2,9] | 2 |
3 | [0,1,2,8,4,3,6,9] | 3 |
4 | [0,1,2,3,4,8,6,9] | 4 (element znajduje się na właściwej pozycji) |
5 | [0,1,2,3,4,8,6,9] | 6 |
6 | [0,1,2,3,4,6,8,9] | 8 (element znajduje się na właściwej pozycji) |
Algorytm można nieco przyspieszyć, gdy tablica jest wypełniana z obu końców, tj. wyszukiwane jest równocześnie minimum i maksimum.
Implementacja
Sortowanie przez wybieranie w C++:
- przez wyszukiwanie największego składnika:
int Max_element_indeks(int n) { int max = 0; for (int i = 1; i < n; i++) if (t[i] > t[max]) max = i; return max; } void Selection_sort(int n) { for (int i = n; i >= 2; i--) { int max = Max_element_indeks(i); if (max != i - 1) swap(t[i - 1], t[max]); } }
template<typename It> void selection_sort(It begin, It end) { for (; begin != end; ++begin) std::iter_swap(begin, std::min_element(begin, end)); }
- przez wyszukiwanie najmniejszego składnika:
#include <cstdlib> #include <iostream> #include <ctime> using namespace std; void selection_sort(int n, int t[]); int main(void) { int tab[20]; srand(time(NULL)); for(int i=0; i<20; i++) { tab[i] = rand()%100; cout << tab[i] << " "; } cout << endl; selection_sort(20, tab); for(int i=0; i<20; i++) cout << tab[i] << " "; cout << endl; return 0; } void selection_sort(int n, int t[]) { int i, j, k; for(i=0; i<n; i++) { k=i; for(j=i+1; j<n; j++) if(t[j]<t[k]) k=j; swap(t[k], t[i]); } }
Sortowanie przez wybieranie w ruby
#!/usr/bin/ruby # sortowanie przez wybor 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 end return list end list = [] puts "podaj dane do posortowania CTRL-D - koniec" while line = $stdin.gets list << line.to_i end puts "Dane posortowane" puts wsort(list)
Sortowanie przez wybieranie w PHP
<?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; } // generujemy tablicę 30 liczb do posortowania $arr = array(); for($i=1; $i<=30; $i++) { $arr[] = rand(10,99); // zapełniamy tablicę liczbami dwucyfrowymi } // drukujemy wygenerowaną tablicę echo "Przed sortowaniem:<br />"; foreach($arr as $k) { echo $k. " "; } // drukujemy posortowaną tablicę echo "<br /><br />Po sortowaniu:<br />"; $sort = selection_sort($arr); foreach($sort as $k) { echo $k. " "; } ?>
Sortowanie przez wybieranie w Javascript
/** * Prototyp dla tablicy zamieniający kolejność dwóch indeksów tej tablicy * @param x * @param y * @returns {Array} */ Array.prototype.swap = function (x, y) { var b = this[x]; this[x] = this[y]; this[y] = b; return this; }; /** * Funkcja wypełniająca tablice losowymi liczbami * @param array */ function fillArray(array) { for (var i = 0; i < 30; i++) { var randomNumber = Math.floor(Math.random() * 30) + 1; // "+ 1" aby losowało z zakresu <1, 30> array.push(randomNumber); } } /** * Funkcja sortowania przez wybieranie * @param array */ 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.swap(i, min); } } }
Linki zewnętrzne
- Algorytm przedstawiony z wykorzystaniem cygańskiego tańca
- p
- d
- e
Algorytmy stabilne |
|
---|---|
Algorytmy niestabilne |
|