Idea algorytmu sortowania przez wybór jest bardzo prosta. Załóżmy, iż chcemy posortować zbiór liczbowy rosnąco. Zatem element najmniejszy powinien znaleźć się na pierwszej pozycji. Szukamy w zbiorze elementu najmniejszego i wymieniamy go z elementem na pierwszej pozycji. W ten sposób element najmniejszy znajdzie się na swojej docelowej pozycji.
W identyczny sposób postępujemy z resztą elementów należących do zbioru. Znów wyszukujemy element najmniejszy i zamieniamy go z elementem na drugiej pozycji. Otrzymamy dwa posortowane elementy. Procedurę kontynuujemy dla pozostałych elementów dotąd, aż wszystkie będą posortowane.
Algorytm sortowania przez wybór posiada klasę czasowej złożoności obliczeniowej równą O(n2). Sortowanie odbywa się w miejscu.
Dla przykładu posortujmy tą metodą zbiór {4 7 2 9 3}. Kolorem zielonym oznaczyliśmy elementy zbioru, które są już posortowane.
Zbiór Opis operacji Wyszukujemy najmniejszy element w zbiorze. Jest nim liczba 2. Znaleziony element minimalny wymieniamy z pierwszym elementem zbioru - liczbą 4 Wśród pozostałych elementów wyszukujemy element najmniejszy. Jest nim liczba 3. Znaleziony element minimalny wymieniamy z drugim elementem zbioru - liczbą 7. Znajdujemy kolejny element minimalny - liczbę 4. Wymieniamy go z samym sobą - element ten nie zmienia zatem swojej pozycji w zbiorze. Znajdujemy kolejny element minimalny Wymieniamy go z liczbą 9 Ostatni element jest zawsze na właściwej pozycji. Sortowanie zakończone
Podana metoda sortuje zbiór rosnąco. Jeśli chcemy posortować zbiór malejąco, to zamiast elementu minimalnego poszukujemy elementu maksymalnego. Pozostała część procedury sortującej nie ulega zmianie.
Dane wejściowe
n - liczba elementów w sortowanym zbiorze, n N
d[ ] - zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n. Dane wyjściowe
d[ ] - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n. Zmienne pomocnicze
i, j - zmienne sterujące pętli, i, j pmin - pozycja elementu minimalnego w zbiorze d[ ], pmin
krok 1: Dla j = 1, 2, ..., n - 1: wykonuj kroki 2...4 krok 2: pmin j
krok 3: Dla i = j + 1, j + 2, ..., n: jeśli d[i] < d[pmin], to pmin krok 4: d[j] d[pmin]
krok 5: Zakończ algorytm
Pętla zewnętrzna sterowana zmienną j wyznacza kolejne elementy zbioru o indeksach od 1 do n - 1, w których zostaną umieszczone elementy minimalne. Na początku tej pętli zakładamy, iż elementem minimalnym jest element d[j] i zapamiętujemy jego indeks w zmiennej pmin.
W pętli numer 2 sterowanej zmienną i porównujemy pozostałe elementy zbioru z elementem d[pmin]. Jeśli element zbioru d[i] jest mniejszy od elementu d[pmin], to znaleźliśmy nowy element minimalny. W takim przypadku zapamiętujemy jego pozycję w pmin i kontynuujemy pętlę wewnętrzną.
Po zakończeniu pętli wewnętrznej pmin zawiera indeks elementu minimalnego. Zamieniamy miejscami element d[j] z elementem d[pmin]. Dzięki tej operacji element minimalny znajduje się na swojej docelowej pozycji. Zwiększamy j przechodząc do kolejnego elementu zbioru i kontynuujemy pętlę zewnętrzną.
Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.
| Efekt uruchomienia programu |
|---|
// Sortowanie Przez Wybór
//-------------------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-------------------------------------------------
program Selection_Sort;
const N = 20; // Liczebność zbioru.
var
d : array[1..N] of integer;
// Program główny
//---------------
var
i,j,x,pmin : integer;
begin
writeln(' Sortowanie przez wybor ');
writeln('------------------------');
writeln(' (C)2005 Jerzy Walaszek ');
writeln;
// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość
randomize;
for i := 1 to N do d[i] := random(100);
writeln('Przed sortowaniem:'); writeln;
for i := 1 to N do write(d[i] : 4);
writeln;
// Sortujemy
for j := 1 to N - 1 do
begin
pmin := j;
for i := j + 1 to N do
if d[i] < d[pmin] then pmin := i;
x := d[pmin]; d[pmin] := d[j]; d[j] := x;
end;
// Wyświetlamy wynik sortowania
writeln('Po sortowaniu:'); writeln;
for i := 1 to N do write(d[i] : 4);
writeln;
writeln('Nacisnij Enter...');
readln;
end.
// Sortowanie Przez Wybór
//-------------------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-------------------------------------------------
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;
const int N = 20; // Liczebność zbioru.
// Program główny
//---------------
int main()
{
int d[N],i,j,pmin;
cout << " Sortowanie przez wybor\n"
"------------------------\n"
" (C)2005 Jerzy Walaszek\n\n"
"Przed sortowaniem:\n\n";
// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość
srand((unsigned)time(NULL));
for(i = 0; i < N; i++) d[i] = rand() % 100;
for(i = 0; i < N; i++) cout << setw(4) << d[i];
cout << endl;
// Sortujemy
for(j = 0; j < N - 1; j++)
{
pmin = j;
for(i = j + 1; i < N; i++)
if(d[i] < d[pmin]) pmin = i;
swap(d[pmin], d[j]);
}
// Wyświetlamy wynik sortowania
cout << "Po sortowaniu:\n\n";
for(i = 0; i < N; i++) cout << setw(4) << d[i];
cout << endl;
system("PAUSE"); return 0;
}
' Sortowanie Przez Wybór
'-------------------------------------------------
' (C)2005 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'-------------------------------------------------
OPTION EXPLICIT
CONST N = 20 ' Liczebność zbioru.
DIM d(1 TO N) AS INTEGER
DIM i AS INTEGER, j AS INTEGER, pmin AS INTEGER
PRINT " Sortowanie przez wybor "
PRINT "------------------------"
PRINT " (C)2005 Jerzy Walaszek "
' Najpierw wypełniamy tablicę d() liczbami pseudolosowymi
' a następnie wyświetlamy jej zawartość
RANDOMIZE TIMER
FOR i = 1 TO N: d(i) = INT(RND * 100): NEXT
PRINT "Przed sortowaniem:"
FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
' Sortujemy
FOR j = 1 TO N - 1
pmin = j
FOR i = j + 1 TO N
IF d(i) < d(pmin) THEN pmin = i
NEXT
SWAP d(pmin),d(j)
NEXT
' Wyświetlamy wynik sortowania
PRINT "Po sortowaniu:"
FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
PRINT "Nacisnij Enter..."
SLEEP
END
<html>
<head>
</head>
<body>
<form style="BORDER-RIGHT: #ff9933 1px outset;
PADDING-RIGHT: 4px; BORDER-TOP: #ff9933 1px outset;
PADDING-LEFT: 4px; PADDING-BOTTOM: 1px;
BORDER-LEFT: #ff9933 1px outset; PADDING-TOP: 1px;
BORDER-BOTTOM: #ff9933 1px outset;
BACKGROUND-COLOR: #ffcc66" name="frmselectionsort">
<h3 style="text-align: center">Sortowanie Przez Wybór</h3>
<p style="TEXT-ALIGN: center">
(C)2005 mgr Jerzy Wałaszek - I LO w Tarnowie
</p>
<hr>
<p style="TEXT-ALIGN: center">
<input onclick="main()" type="button" value="Sortuj" name="B1">
</p>
<p id="t_out" style="TEXT-ALIGN: center">...</p>
</form>
<script language=javascript>
// Sortowanie Przez Wybór
//-------------------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-------------------------------------------------
var N = 20; // Liczebność zbioru.
function main()
{
var d = new Array(N);
var i,j,pmin,x,t;
// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
for(i = 0; i < N; i++) d[i] = Math.floor(Math.random() * 100);
t = "Przed sortowaniem:<BR><BR>";
for(i = 0; i < N; i++) t += d[i] + " ";
t += "<BR><BR>";
// Sortujemy
for(j = 0; j < N - 1; j++)
{
pmin = j;
for(i = j + 1; i < N; i++)
if(d[i] < d[pmin]) pmin = i;
x = d[pmin]; d[pmin] = d[j]; d[j] = x;
}
// Wyświetlamy wynik sortowania
t += "Po sortowaniu:<BR><BR>";
for(i = 0; i < N; i++) t += d[i] + " ";
document.getElementById("t_out").innerHTML = t;
}
</script>
</body>
</html>
W celach badawczych testujemy czas wykonania algorytmu sortowania przez wybór w środowisku opisanym we wstępie. Program testujący jest następujący:
// Program testujący czas sortowania dla
// danego algorytmu sortującego
//--------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie
//--------------------------------------
program TestCzasuSortowania;
uses Windows;
const
NAZWA = 'Sortowanie przez wybór';
K1 = '-------------------------------------------';
K2 = '(C)2005 mgr J.Wałaszek I LO w Tarnowie';
K3 = '------n---------tpo---------tod---------tpp---------tpk---------tnp';
K4 = '-------------------------------------------------------------------';
MAX_LN = 6; // określa ostatnie LN
LN : array[1..8] of integer = (1000,2000,4000,8000,16000,32000,64000,128000);
var
d : array[1..128000] of real; // sortowana tablica
n : integer; // liczba elementów
qpf,tqpc : int64; // dane dla pomiaru czasu
qpc1,qpc2 : int64;
// Tutaj umieszczamy procedurę sortującą tablicę d
//------------------------------------------------
function Sort : extended;
var
i,j,pmin : integer;
x : real;
begin
QueryPerformanceCounter(addr(qpc1));
for j := 1 to n - 1 do
begin
pmin := j;
for i := j + 1 to n do
if d[i] < d[pmin] then pmin := i;
x := d[pmin]; d[pmin] := d[j]; d[j] := x;
end;
QueryPerformanceCounter(addr(qpc2));
Sort := (qpc2 - qpc1 - tqpc) / qpf;
end;
// Program główny
//---------------
var
i,j,k : integer;
tpo,tod,tpp,tpk,tnp : extended;
f : Text;
begin
if QueryPerformanceFrequency(addr(qpf)) then
begin
QueryPerformanceCounter(addr(qpc1));
QueryPerformanceCounter(addr(qpc2));
tqpc := qpc2 - qpc1;
assignfile(f,'wyniki.txt'); rewrite(f);
// Wydruk na ekran
writeln('Nazwa: ',NAZWA);
writeln(K1);
writeln(K2);
writeln;
writeln(K3);
// Wydruk do pliku
writeln(f,'Nazwa: ',NAZWA);
writeln(f,K1);
writeln(f,K2);
writeln(f,'');
writeln(f,K3);
for i := 1 to MAX_LN do
begin
n := LN[i];
// Czas sortowania zbioru posortowanego
for j := 1 to n do d[j] := j;
tpo := Sort;
// Czas sortowania zbioru posortowanego odwrotnie
for j := 1 to n do d[j] := n - j;
tod := Sort;
// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na początku - średnia z 10 obiegów
tpp := 0;
for j := 1 to 10 do
begin
for k := 1 to n do d[k] := k;
d[1] := random * n + 1;
tpp += Sort;
end;
tpp /= 10;
// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na końcu - średnia z 10 obiegów
tpk := 0;
for j := 1 to 10 do
begin
for k := 1 to n do d[k] := k;
d[n] := random * n + 1;
tpk += Sort;
end;
tpk /= 10;
// Czas sortowania zbioru nieuporządkowanego - średnia z 10 obiegów
tnp := 0;
for j := 1 to 10 do
begin
for k := 1 to n do d[k] := random;
tnp += Sort;
end;
tnp /= 10;
writeln(n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
writeln(f,n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
end;
writeln(K4);
writeln(f,K4);
writeln(f,'Koniec');
closefile(f);
writeln;
writeln('Koniec. Wyniki w pliku WYNIKI.TXT');
end
else writeln('Na tym komputerze program testowy nie pracuje !');
writeln;
write('Nacisnij klawisz ENTER...'); readln;
end.Otrzymane wyniki są następujące (dla komputera o innych parametrach wyniki mogą się różnić co do wartości czasów wykonania, dlatego w celach porównawczych proponuję uruchomić podany program na komputerze czytelnika):
| Zawartość pliku wygenerowanego przez program | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Nazwa: Sortowanie przez wybór Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):
|
(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)
(Arkusz kalkulacyjny Excel do wyznaczania wzrostu prędkości sortowania)
Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów sortowania dla algorytmu sortowania przez wybór wyciągamy następujące wnioski:
| Cechy Algorytmu Sortowania Przez Wybór | |
|---|---|
| klasa złożoności obliczeniowej optymistyczna | O(n2) |
| klasa złożoności obliczeniowej typowa | O(n2) |
| klasa złożoności obliczeniowej pesymistyczna | O(n2) |
| Sortowanie w miejscu | TAK |
| Stabilność | NIE |
Klasy złożoności obliczeniowej szacujemy następująco:
- optymistyczna - dla zbiorów uporządkowanych (z niewielką liczbą elementów nie na swoich miejscach) - na podstawie czasów tpo, tpp, tpk
- typowa - dla zbiorów o losowym rozkładzie elementów - na podstawie czasu tnp
- pesymistyczna - dla zbiorów posortowanych odwrotnie - na podstawie czasu tod.
| Własności algorytmu | |||||
|---|---|---|---|---|---|
| Algorytm | tpo | tod | tpp | tpk | tnp |
| Sortowanie przez wybór | O(n2) | O(n2) | O(n2) | O(n2) | O(n2) |
tpo  tod tpp tpk tnp | |||||
- Wszystkie badane przez nas czasy sortowania są proporcjonalne do kwadratu liczby elementów porządkowanego zbioru. Klasa czasowej złożoności obliczeniowej algorytmu sortowania przez wybór wynosi O(n2).
- Wszystkie badane czasy sortowania są praktycznie takie same.
- Algorytm nie uwzględnia faktu posortowania zbioru. Jednakże również nie wyróżnia on przypadku posortowania zbioru w kierunku odwrotnym. Zatem można wysunąć wniosek, iż dla tego algorytmu złożoność czasowa nie zależy od rozkładu elementów w sortowanym zbiorze.
| Wzrost prędkości sortowania | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Algorytmy | tpo | tod | tpp | tpk | tnp | |||||||||||||
Sortowanie bąbelkowe 4 Sortowanie przez wybór |
|
|
|
|
| |||||||||||||
| źle | dobrze | źle | źle | dobrze | ||||||||||||||
Porównując prędkości algorytmów zoptymalizowanego sortowania bąbelkowego i sortowania przez wybór dochodzimy do wniosku, iż ten drugi w przypadku zbiorów posortowanych odwrotnie oraz nieposortowanych jest kilkakrotnie szybszy. Jednakże dla zbiorów w znacznym stopniu uporządkowanych algorytm sortowania bąbelkowego nie daje mu żadnych szans - nic w tym dziwnego, ponieważ zgodnie z naszymi badaniami, algorytm sortowania bąbelkowego posiada w tych przypadkach liniową klasę czasowej złożoności obliczeniowej, natomiast algorytm sortowania przez wybór ma dla każdego zestawu danych czasową złożoność obliczeniową proporcjonalną do kwadratu liczby sortowanych elementów.
Na podstawie algorytmu sortowania przez wybór uzasadnij, iż czas sortowania nie jest zależny od rozkładu elementów w porządkowanym zbiorze.
Uzasadnij, że algorytm sortowania przez wybór nie jest stabilny.
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.
Źródło: mgr Jerzy Wałaszek