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, ponieważ mniejsze zostały już przetworzone. 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.

do podrozdziału do 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

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

do podrozdziału do 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 << 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 << endl;
  system("pause");
  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;
  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;
  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

CONST N = 20 ' Liczebność zbioru.

DIM AS INTEGER d(1 TO N),i,j,pmin

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
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
PRINT "Nacisnij Enter..."
SLEEP
END

Python (dodatek)

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

import random

n = 20 # Liczebność zbioru.

d = [random.randrange(100) for i in range(n)]

print(" Sortowanie przez wybór")
print("------------------------")
print(" (C)2026 Jerzy Wałaszek")
print()

# wyświetlamy zawartość d

print("Przed sortowaniem:")
print()
for i in range(n):
    print("%4d" % (d[i]),end="")
print()
print()

# Sortujemy

for j in range(n):
    pmin = j
    for i in range(j+1,n):
        if d[i] < d[pmin]: pmin = i
    d[pmin],d[j] = d[j],d[pmin]

# Wyświetlamy wynik sortowania

print("Po sortowaniu:")
print()
for i in range(n):
    print("%4d" % (d[i]), end="")
print()
print()
input("Naciśnij Enter...")

Wynik:

 Sortowanie przez wybór
------------------------
 (C)2026 Jerzy Wałaszek

Przed sortowaniem:

   5  84  53  27  88  27  21  39  71  79  43  86  42  72   5   5  21  42  31  99

Po sortowaniu:

   5   5   5  21  21  27  27  31  39  42  42  43  53  71  72  79  84  86  88  99

Naciśnij Enter...

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>

do podrozdziału do strony

Cechy Algorytmu Sortowania Przez Wybór
klasa złożoności obliczeniowej optymistyczna	O(n²)
klasa złożoności obliczeniowej typowa	O(n²)
klasa złożoności obliczeniowej pesymistyczna	O(n²)
Sortowanie w miejscu	TAK
Stabilność	NIE

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

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

Podsumowanie

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

Podsumowanie

Sortowanie przez wybór
Selection Sort