Sortowanie przez wybieranie: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
Literówka Znaczniki: Z urządzenia mobilnego Z wersji mobilnej (przeglądarkowej) |
m drobne techniczne |
||
Linia 8: | Linia 8: | ||
|pamiec= |
|pamiec= |
||
}} |
}} |
||
{{Algorytm infobox |
|||
| nazwa = Sortowanie przez wybieranie |
|||
| grafika = Selection sort animation.gif |
|||
| wielkość grafiki = |
|||
| opis grafiki = Przykład działania sortowania przez wybieranie |
|||
| rodzaj = [[Sortowanie]] |
|||
| struktura = [[Tablica (informatyka)|Tablica]], [[lista]] |
|||
| czas = <math>O(n^2)</math> |
|||
| pamięć = |
|||
}} |
|||
'''Sortowanie przez wybieranie''' - jedna z prostszych metod [[sortowanie|sortowania]] o [[złożoność obliczeniowa|złożoności]] O(''n''<sup>2</sup>). 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. |
'''Sortowanie przez wybieranie''' - jedna z prostszych metod [[sortowanie|sortowania]] o [[złożoność obliczeniowa|złożoności]] O(''n''<sup>2</sup>). 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. |
||
Linia 193: | Linia 202: | ||
{{Algorytmy sortowania}} |
{{Algorytmy sortowania}} |
||
{{DEFAULTSORT:Wybieranie}} |
|||
[[Kategoria:Algorytmy sortowania |
[[Kategoria:Algorytmy sortowania]] |
Wersja z 00:03, 22 lip 2017
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
O(n2) |
Przykład działania sortowania przez wybieranie | |
Rodzaj | |
---|---|
Struktura danych | |
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ą.
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.
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. " ";
}
?>