Sortowanie przez wybór


Tematy pokrewne
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych

 

Problem

Posortować rosnąco n-elementowy zbiór Z.

 

 

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 minZ. 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
minZ  – tymczasowy element minimalny
minp  – pozycja tymczasowego elementu minimalnego,  minp C
Lista kroków:
K01: Dla i = 0,1,...,n-2 wykonuj K02...K08  
K02:     minZZ[i] ; tymczasowy element minimalny
K03:     minpi ; oraz jego tymczasowa pozycja
K04:     Dla j = i+1,i+2,...,n-1 wykonuj K05...K07 ; w pozostałych elementach szykamy minimalnego
K05:         Jeśli Z[j] ≥ minZ, to kolejny obieg pętli K04...K07  
K06:         minZZ[j] ; znaleźliśmy, uaktualniamy minZ oraz minp
K07:         minpj  
K08:     Z[i] Z[minp] ; zamieniamy znaleziony element z i-tym
K09: Zakończ  

 

Program

Ważne:

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

 

Lazarus
// Sortowanie przez wybór
// Data:   1.05.2008
// (C)2012 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.
Code::Blocks
// Sortowanie przez wybór
// Data:   1.05.2008
// (C)2012 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;
}
Free Basic
' Sortowanie przez wybór
' Data:   1.05.2008
' (C)2012 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

 

Sortowanie przez wybór
(C)2012 mgr Jerzy Wałaszek


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.