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.

Zmienne 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: wykonuj kroki K05...K07	w pozostałych elementach szykamy minimalnego
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 <time.h>

using namespace std;

const int N = 200;

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

  srand ( ( unsigned )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;
      }
    x = Z [ i ];
    Z [ i ] = Z [ minp ];
    Z [ minp ] = x;
  }

// 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

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

Na początek: podrozdziału 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