Sortowanie przez wybieranie
Sortowanie przez wybieranieSortowanie przez wybieranie - jedna z prostszych metod
sortowania
o
złożoności
O(n2). Polega na wyszukaniu elementu mającego się znaleźć na zadanej 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+1 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ładPosortowana zostanie tablica 8-elementowa [9,1,6,8,4,3,2,0]. W tablicy pogrubione zostaną te elementy wśród których wyszukuje sie wartość minimalną. nr iteracji (wartość i) | tablica | minimum |
---|
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 (...) | 5 | [0,1,2,3,4,8,6,9] | 6 | 6 | [0,1,2,3,4,6,8,9] | 8 (...) |
Algorytm można nieco przyspieszyć, gdy tablica jest wypełniana z obu końców, tj. wyszukiwane jest równocześnie minimum i maksimum. ImplementacjaSortowanie 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> 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 = ifor j in (i+1)...(list.size)if list[j] <= list[min]min = jendlist[i], list[min] = list[min], list[i]endendreturn listend list = []puts "podaj dane do posortowania CTRL-D - koniec"while line = $stdin.gets list << line.to_iendputs "Dane posortowane"puts wsort(list)
Inne hasła zawierające informacje o "Sortowanie przez wybieranie":
Podróżnik
...
Dziady (zwyczaj)
...
Pęcice
...
Zambezi
...
Rodzimy Kościół Polski
...
Ren
...
Dzień Zmarłych
...
Dzień Zaduszny
...
Muzeum Zoologiczne Tadasa Ivanauskasa w Kownie
...
II wiek
...
Inne lekcje zawierające informacje o "Sortowanie przez wybieranie":
Potęgi (plansza 2)
...
10b Wyprzedzanie - część 2 (plansza 11)
...
01 Znaki drogowe - tabliczki do znaków drogowych - część 2 (plansza 20)
...
|