Sortowanie przez wybieranie: Różnice pomiędzy wersjami
[wersja nieprzejrzana] | [wersja przejrzana] |
m robot dodaje: ml:സെലക്ഷന് സോര്ട്ട് |
|||
Linia 36: | Linia 36: | ||
== Implementacja == |
== Implementacja == |
||
Sortowanie przez wybieranie w C++: |
Sortowanie przez wybieranie w C++: |
||
* przez wyszukiwanie największego składnika: |
|||
<source lang="cpp"> |
<source lang="cpp"> |
||
int Max_element_indeks(int n) |
int Max_element_indeks(int n) |
||
Linia 63: | Linia 65: | ||
for (; begin != end; ++begin) |
for (; begin != end; ++begin) |
||
std::iter_swap(begin, std::min_element(begin, end)); |
std::iter_swap(begin, std::min_element(begin, end)); |
||
} |
|||
</source> |
|||
* przez wyszukiwanie najmniejszego składnika: |
|||
<source lang="cpp"> |
|||
#include <cstdlib> |
|||
#include <iostream> |
|||
using namespace std; |
|||
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]); |
|||
} |
|||
} |
|||
int main(int argc, char *argv[]) |
|||
{ |
|||
srand(time(NULL)); |
|||
int tab[20]; |
|||
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; |
|||
system("PAUSE"); |
|||
return EXIT_SUCCESS; |
|||
} |
} |
||
</source> |
</source> |
Wersja z 15:33, 26 paź 2009
Sortowanie 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ł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 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.
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>
using namespace std;
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]);
}
}
int main(int argc, char *argv[])
{
srand(time(NULL));
int tab[20];
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;
system("PAUSE");
return EXIT_SUCCESS;
}