Algorytmy i Struktury Danych - Sortowanie przez wybór

Zadanie sortowania polega na takim ułożeniu elementów zbioru Z, aby zachodził pomiędzy nimi porządek zdefiniowany odpowiednią relacją porządkującą. Porządek rosnący oznacza, iż w miarę posuwania się w głąb zbioru, wartości elementów stają się coraz większe – nie napotkamy elementu mniejszego od któregokolwiek z elementów go poprzedzających w zbiorze. Relacją porządkującą jest relacja < lub ≤ przy dopuszczeniu elementów o równych wartościach – jednakże wtedy nie jest określona kolejność elementów równych.

Istnieje bardzo wiele różnych algorytmów sortowania (ang. Sorting Algorithms). W tym rozdziale przedstawimy bardzo prosty algorytm, który wykorzystuje liniowe wyszukiwanie (ang. linear search) elementu minimalnego w zbiorze – sortowanie przez wybór (ang. Selection Sort). Zasada pracy tego algorytmu jest następująca:

Wyszukujemy w zbiorze Z najmniejszy element min_Z. Element najmniejszy w zbiorze posortowanym powinien znaleźć się na pierwszej pozycji. Zatem znaleziony element wymieniamy z elementem pierwszym. Dalej postępujemy identycznie ze zbiorem Z pomniejszonym o pierwszy element.. Znajdujemy kolejny element minimalny i wymieniamy go z elementem na pozycji drugiej. Sortowanie tym samym sposobem kontynuujemy dla kolejnych podzbiorów Z. Gdy otrzymamy podzbiór jednoelementowy (czyli gdy wykonamy n-1 wyborów elementów minimalnych). Kolejno znajdowane elementy minimalne tworzą ciąg niemalejący – to wyjaśnia skuteczność tej metody przy sortowaniu zbioru.

Algorytm sortowania przez wybór

Wejście:

n : liczba elementów w tablicy Z, n ∈ N.
Z : tablica zawierająca elementy do posortowania.

Wyjście:

Tablica Z z posortowanymi rosnąco elementami.

Elementy pomocnicze:

i, j : przebiegają przez kolejne indeksy elementów Z. i, j ∈ C.
min_Z : tymczasowy element minimalny.
min_p : pozycja tymczasowego elementu minimalnego, min_p ∈ C.

Lista kroków:

K01: Dla i = 0, 1, …, n-2:
     wykonuj kroki K02…K08
K02:   min_Z ← Z[i] ; tymczasowy element minimalny
K03:   min_p ← i ; oraz jego tymczasowa pozycja
K04:   Dla j = i+1, i+2, …, n-1: ; w pozostałych elementach szukamy minimalnego
       wykonuj kroki K05…K07
K05:   Jeśli Z[j] ≥ min_Z, 
       to kolejny obieg pętli K04
K06:   min_Z ← Z[j] ; znaleźliśmy, uaktualniamy min_Z oraz min_p
K07:   min_p ← j
K08:   Z[i] ↔ Z[min_p] ; zamieniamy znaleziony element z i-tym
K09: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program wypełnia 200 elementową tablicę liczbami pseudolosowymi od 0 do 999. Następnie wyświetla zawartość tej tablicy przed sortowaniem, sortuje ją opisanym algorytmem sortowania przez wybór i na koniec wyświetla tablicę posortowaną.

Pascal

// Sortowanie przez wybór
// Data:   1.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 200;

var Z : array [0..N-1] of integer;
    minZ, minp, i, j, x : integer;

begin
  randomize;
  for i := 0 to N-1 do
    Z[i] := random(1000);

  // Przed sortowaniem
  for i := 0 to N-1 do
    write(Z[i]:4);
  writeln;

  // Sortowanie przez wybór
  for i := 0 to N-2 do
  begin
    minZ := Z[i];
    minp := i;
    for j := i+1 to N-1 do
      if Z[j] < minZ then
      begin
        minZ := Z[j];
        minp := j;
      end;
    x       := Z[i];
    Z[i]    := Z[minp];
    Z[minp] := x;
  end;

  // Po sortowaniu
  for i := 0 to N-1 do
    write(Z[i]:4);
  writeln;
end.

C++

// Sortowanie przez wybór
// Data:   1.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 200;

int main()
{
  int Z[N], minZ, minp, i, j;

  srand(time(NULL));
  for(i = 0; i < N; i++)
    Z[i] = rand() % 1000;

  // Przed sortowaniem
  for(i = 0; i < N; i++)
    cout << setw(4) << Z[i];
  cout << endl;

// Sortowanie przez wybór
  for(i = 0; i < N-1; i++)
  {
    minZ = Z[i];
    minp = i;
    for(j = i+1; j < N; j++)
      if(Z[j] < minZ)
      {
        minZ = Z[j];
        minp = j;
      }
    swap(Z[i], Z[minp]);
  }

// Po sortowaniu

  for(i = 0; i < N; i++)
    cout << setw(4) << Z[i];
  cout << endl;
  return 0;
}

Basic

' Sortowanie przez wybór
' Data:   1.05.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 200

Dim As Integer Z(N-1), minZ, minp, i, j

Randomize
For i = 0 To N-1
  Z(i) = Cint(Rnd*999)
Next

' Przed sortowaniem
For i = 0 To N-1
  Print Using "####";Z(i);
Next
Print

' Sortowanie przez wybór
For i = 0 To N-2
  minZ = Z(i)
  minp = i
  For j = i+1 To N-1
    If Z(j) < minZ Then
      minZ = Z(j)
      minp = j
    End If
  Next 
  Swap Z(i), Z(minp)
Next

' Po sortowaniu
For i = 0 To N-1
  Print Using "####";Z(i);
Next
Print

End

Python (dodatek)

# Sortowanie przez wybór
# Data:   25.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 200 # Ilość liczb
z = [random.randrange(1000) for i in range(N)]
# Przed sortowaniem
for i in range(N):
    print("%4d" % z[i], end="")
print()
print()
# Sortowanie przez wybór
for i in range(N-1):
    minz = z[i]
    minp = i
    for j in range(i+1, N):
        if z[j] < minz:
            minz = z[j]
            minp = j
    z[i], z[minp] = z[minp], z[i]
# Po sortowaniu
for i in range(N):
    print("%4d" % z[i], end="")
print()

Wynik:

 996 402 535 550 195 212 312  58  55 550 383 146 299  29 147 723 430 271  70 891
 566 958 414 261 157 434  37 866 229 726 619 615 325 147 277 761 824 326 126 999
 258 880 123 539 692 469 843  23 719 544 419 894 249 316 965 478  54 329 256 457
 400 482 728 190 639 235 287 427 150 182 666 597 554 245 122 659 125 526 385 949
 877 483 709 720 867 961 348 598 761 526 997 154 764 750 138 245 183 489 274 524
 729 451 165 989 879 812 507 629 294 304 356  68 617 970 113 726 697 222 731 532
 583 734 382 934 325 278 998 705 630 337 676 297 401 881 190 531 848 215 807 646
 659 669 167 102 461 318  15 911 552 640 525 966 423 263 354 865 331 862  13 279
 548 300 620 448 272 779 226 912 807 413 830 849 566 449 111 120 125 329 711 650
 196  39 171   6 707 891 517  38 934 118 707 546 478 213 726 319 725 376 328 764

   6  13  15  23  29  37  38  39  54  55  58  68  70 102 111 113 118 120 122 123
 125 125 126 138 146 147 147 150 154 157 165 167 171 182 183 190 190 195 196 212
 213 215 222 226 229 235 245 245 249 256 258 261 263 271 272 274 277 278 279 287
 294 297 299 300 304 312 316 318 319 325 325 326 328 329 329 331 337 348 354 356
 376 382 383 385 400 401 402 413 414 419 423 427 430 434 448 449 451 457 461 469
 478 478 482 483 489 507 517 524 525 526 526 531 532 535 539 544 546 548 550 550
 552 554 566 566 583 597 598 615 617 619 620 629 630 639 640 646 650 659 659 666
 669 676 692 697 705 707 707 709 711 719 720 723 725 726 726 726 728 729 731 734
 750 761 761 764 764 779 807 807 812 824 830 843 848 849 862 865 866 867 877 879
 880 881 891 891 894 911 912 934 934 949 958 961 965 966 970 989 996 997 998 999

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