Algorytmy Sortujące - Sortowanie Przez Wybór

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(n²). Sortowanie odbywa się w miejscu.

Przykład:

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 3	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 7	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.

Na początek: podrozdziału strony

Specyfikacja problemu

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
p_min	- pozycja elementu minimalnego w zbiorze d[ ], p_min ∈ N

Lista kroków

K01:	Dla j = 1, 2, ..., n - 1: wykonuj kroki K02...K04
K02:	p_min ← j
K03:	Dla i = j + 1, j + 2, ..., n: jeśli d[i] < d[p_min], to p_min ← i
K04:	d[j] ↔ d[p_min]
K05:	Zakończ

Schemat blokowy

obrazek

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 p_min.

W pętli numer 2 sterowanej zmienną i porównujemy pozostałe elementy zbioru z elementem d[p_min]. Jeśli element zbioru d[i] jest mniejszy od elementu d[p_min], to znaleźliśmy nowy element minimalny. W takim przypadku zapamiętujemy jego pozycję w p_min i kontynuujemy pętlę wewnętrzną.

Po zakończeniu pętli wewnętrznej p_min zawiera indeks elementu minimalnego. Zamieniamy miejscami element d[j] z elementem d[p_min]. 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ą.

Na początek: podrozdziału strony

C++

// Sortowanie Przez Wybór
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

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;
  return 0;
}

Pascal

// Sortowanie Przez Wybór
//--------------------------------------------------------
// (C)2012 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.

Basic

' Sortowanie Przez Wybór
'--------------------------------------------------------
' (C)2012 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

JavaScript

<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)2012 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)2012 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>

Wynik:

Sortowanie przez wybor
------------------------
(C)2005 Jerzy Walaszek

Przed sortowaniem:

98 49 73 16 64 25 5 83 54 51 80 3 98 26 86 87 80 68 5 11

Po sortowaniu:

3 5 5 11 16 25 26 49 51 54 64 68 73 80 80 83 86 87 98 98

Na początek: podrozdziału strony

W celach badawczych testujemy czas wykonania algorytmu sortowania przez wybór w środowisku opisanym we wstępie. Program testujący jest następujący:

Pascal

// Program testujący czas sortowania dla
// danego algorytmu sortującego
//--------------------------------------
// (C)2012 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)2011/2012 I Liceum Ogolnoksztalcace  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)2011/2012 I Liceum Ogolnoksztalcace  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
t_po	-	czas sortowania zbioru posortowanego
t_od	-	czas sortowania zbioru posortowanego malejąco
t_pp	-	czas sortowania zbioru posortowanego z losowym elementem na początku
t_pk	-	czas sortowania zbioru posortowanego z losowym elementem na końcu
t_np	-	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)

Na początek: podrozdziału strony

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
klasa złożoności obliczeniowej typowa
klasa złożoności obliczeniowej pesymistyczna
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 t_po, t_pp, t_pk
typowa - dla zbiorów o losowym rozkładzie elementów - na podstawie czasu t_np
pesymistyczna - dla zbiorów posortowanych odwrotnie - na podstawie czasu t_od.

Własności algorytmu
Algorytm	t_po	t_od	t_pp	t_pk	t_np
Sortowanie przez wybór
Sortowanie przez wybór

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(n²).
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	t_po	t_od	t_pp	t_pk	t_np
Sortowanie bąbelkowe 4 Sortowanie przez wybór
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 początek: podrozdziału strony

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.

Na początek: podrozdziału strony

Sortowanie przez wybór
Selection Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Przez Wybór

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Sortowanie przez wybór Selection Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Przez Wybór

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Sortowanie przez wybór
Selection Sort