Login lub e-mail Hasło   

Algorytmy sortujące - sortowanie przez wybór

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
Idea algorytmu sortowania przez wybór jest bardzo prosta. Załóżmy, iż chcemy posortować zbiór liczbowy rosnąco. Zatem element najmniejszy powinien znaleźć...
Wyświetlenia: 23.725 Zamieszczono 17/10/2006

 

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
 4 7 2 9 3 
Wyszukujemy najmniejszy element w zbiorze. Jest nim liczba 2.
 2 7 4 9 3 
Znaleziony element minimalny wymieniamy z pierwszym elementem zbioru - liczbą 4
 2 7 4 9
Wśród pozostałych elementów wyszukujemy element najmniejszy. Jest nim liczba 3.
 2 3 4 9 7 
Znaleziony element minimalny wymieniamy z drugim elementem zbioru - liczbą 7.
 2 3 4 9 7 
Znajdujemy kolejny element minimalny - liczbę 4.
 2 3 4 9 7 
Wymieniamy go z samym sobą - element ten nie zmienia zatem swojej pozycji w zbiorze.
 2 3 4 9
Znajdujemy kolejny element minimalny
 2 3 4 7 9 
Wymieniamy go z liczbą 9
 2 3 4 7 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 N
pmin - pozycja elementu minimalnego w zbiorze d[ ]pmin N

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 i
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 "
PRINT

' 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:"
PRINT
FOR
i = 1 TO N: PRINT USING "####"; d(i);: NEXT
PRINT


' 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:"
PRINT
FOR
i = 1 TO N: PRINT USING "####"; d(i);: NEXT
PRINT
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
-------------------------------------------
(C)2005 mgr J.Wałaszek I LO w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
1000 0.002724 0.002909 0.002791 0.002780 0.003110
2000 0.011507 0.012866 0.011278 0.011224 0.011862
4000 0.045771 0.049455 0.045857 0.045861 0.047035
8000 0.183433 0.198379 0.187596 0.187755 0.186893
16000 0.737399 0.797531 0.743703 0.741200 0.748871
32000 3.236753 3.429465 3.221679 3.219949 3.234469
-------------------------------------------------------------------
Koniec

Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):

n -  ilość elementów w sortowanym zbiorze
tpo -  czas sortowania zbioru posortowanego
tod -  czas sortowania zbioru posortowanego malejąco
tpp -  czas sortowania zbioru posortowanego z losowym elementem na początku
tpk -  czas sortowania zbioru posortowanego z losowym elementem na końcu
tnp -  czas sortowania zbioru z losowym rozkładem elementów

(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
  1. 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).
  2. Wszystkie badane czasy sortowania są praktycznie takie same.
  3. 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

  3
n
  9
  14
n
  8
n
  6
źle dobrze źle źle dobrze
  1. 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.

 

  1. Na podstawie algorytmu sortowania przez wybór uzasadnij, iż czas sortowania nie jest zależny od rozkładu elementów w porządkowanym zbiorze.

  2. Uzasadnij, że algorytm sortowania przez wybór nie jest stabilny.

 Dokument ten rozpowszechniany jest zgodnie z zasadami licencji

GNU Free Documentation License.

Podobne artykuły


16
komentarze: 5 | wyświetlenia: 9006
9
komentarze: 0 | wyświetlenia: 2784
49
komentarze: 18 | wyświetlenia: 64978
37
komentarze: 9 | wyświetlenia: 28520
11
komentarze: 2 | wyświetlenia: 33153
7
komentarze: 1 | wyświetlenia: 34649
17
komentarze: 4 | wyświetlenia: 14183
15
komentarze: 5 | wyświetlenia: 32761
13
komentarze: 2 | wyświetlenia: 22961
12
komentarze: 2 | wyświetlenia: 18506
12
komentarze: 3 | wyświetlenia: 29779
11
komentarze: 1 | wyświetlenia: 86405
11
komentarze: 1 | wyświetlenia: 10475
10
komentarze: 1 | wyświetlenia: 34971
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska