Głupie sortowanie bąbelkowe
            Stupid Bubble Sort


Podrozdziały    

 

Algorytm

Sortowanie głupie jest również bardzo złym algorytmem sortującym, lecz, w przeciwieństwie do opisanego w poprzednim rozdziale sortowania zwariowanego, daje zawsze poprawne wyniki. Zasada działania jest bardzo prosta:

Przeglądamy kolejne pary sąsiednich elementów sortowanego zbioru. Jeśli bieżąco przeglądana para elementów jest w złej kolejności, elementy pary zamieniamy miejscami i całą operację rozpoczynamy od początku zbioru. Jeśli przeglądniemy wszystkie pary, zbiór będzie posortowany.

Naiwność (lub, jak wolą niektórzy, głupota) algorytmu wyraża się tym, iż po napotkaniu nieposortowanych elementów algorytm zamienia je miejscami, a następnie rozpoczyna całą pracę od początku zbioru. Złożoność obliczeniowa algorytmu przy sortowaniu zbioru nieuporządkowanego ma klasę O(n3). Sortowanie odbywa się w miejscu.

Algorytm sortowania głupiego występuje w dwóch wersjach - rekurencyjnej oraz iteracyjnej. Wersja rekurencyjna jest jeszcze gorsza od iteracyjnej, gdyż dodatkowo zajmuje pamięć na kolejne poziomy wywołań rekurencyjnych, dlatego nie będziemy się nią zajmować (zainteresowanych odsyłam do Wikipedii).

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 - zmienna sterująca pętli, i N

 

Lista kroków

K01: Dla i = 1,2,...,n - 1: wykonuj K02...K04
K02:     Jeśli d[i] ≤ d[i + 1], to wykonaj następny obieg K01
K03:     d[i] ↔ d[i + 1]
K04:     Idź do K01
K05: Zakończ

 

Schemat blokowy

flow

Rozpoczynamy przeglądanie zbioru od pierwszego elementu - indeks i przyjmuje wartość 1. W pętli sprawdzamy kolejność elementu d[i] z elementem następnym d[i+1]. Ponieważ założyliśmy porządek rosnący, to w przypadku d[i] > d[i+1] elementy te są w złej kolejności (dla porządku malejącego należy zmienić relację większości na relację mniejszości). W takiej sytuacji zamieniamy miejscami elementy, indeks i ustawiamy z powrotem na 1 (powrót na sam początek algorytmu byłby nieco kłopotliwy do zrealizowania w językach programowania, stąd dla prostoty ustawiamy i na 1 za operacją zamiany elementów) i wracamy na początek pętli.

Jeśli porównywane elementy są w dobrej kolejności, zwiększamy indeks i o 1, sprawdzamy, czy osiągnął już wartość końcową n i, jeśli nie, wracamy na początek pętli. W przeciwnym razie kończymy - zbiór jest posortowany.


 

Programy

Efekt uruchomienia programu
  Sortowanie  glupie
----------------------
(C)2005 Jerzy Walaszek

Przed sortowaniem:

  60  70  46  52  97  34  14  60   4  56  77  34  75  72  78  86  45  12  30  99

Po sortowaniu:

   4  12  14  30  34  34  45  46  52  56  60  60  70  72  75  77  78  86  97  99

 

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

program Stupid_Sort;

const N = 20; // Liczebność zbioru.

var
  d : array[1..N] of integer;

// Program główny
//---------------

var
  i,x : integer;
begin
  writeln('  Sortowanie  glupie  ');
  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

  i := 1;
  repeat
    if d[i] > d[i+1] then // Porządek rosnący
    begin
      x := d[i]; d[i] := d[i+1]; d[i+1] := x;
      i := 1;
      continue;
    end;
    inc(i);
  until i = N;

// Wyświetlamy wynik sortowania

  writeln('Po sortowaniu:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;
  writeln('Nacisnij Enter...');
  readln;
end.
Code::Blocks
// Sortowanie Głupie
//--------------------------------------------------------
// (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;
  
  cout << "  Sortowanie  glupie\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

  i = 0;
  do
  {
    if(d[i] > d[i+1]) // Porządek rosnący
    {
      swap(d[i], d[i+1]);
      i = 0;
      continue;
    }
    i++;
  } while(i < N-1);

// Wyświetlamy wynik sortowania

  cout << "Po sortowaniu:\n\n";
  for(i = 0; i < N; i++) cout << setw(4) << d[i];
  cout << endl;
  return 0;
}
Free Basic
' Sortowanie Głupie
'--------------------------------------------------------
' (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, i AS INTEGER

  PRINT "  Sortowanie  glupie  "
  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

  i = 1
  DO
    IF d(i) > d(i+1) THEN ' Porządek rosnący
      SWAP d(i), d(i+1)
      i = 1
      CONTINUE DO
    END IF
    i = i + 1
  LOOP UNTIL i = N

' 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="frmstupidsort">
      <h3 style="text-align: center">Sortowanie Głupie</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 Głupie
//--------------------------------------------------------
// (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,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

  i = 0;
  do
  {
    if(d[i] > d[i+1]) // Porządek rosnący
    {
      x = d[i]; d[i] = d[i+1]; d[i+1] = x;
      i = 0;
      continue;
    }
    i++;
  } while(i < N-1);

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

 

Tutaj możesz przetestować działanie prezentowanego skryptu:

Sortowanie Głupie

(C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie


...

 

Einstein
DLA
GENIUSZA

Badanie algorytmów sortowania

W celach badawczych testujemy czas wykonania algorytmu sortowania głupiego w środowisku opisanym we wstępie. Jednakże, ze względu na bardzo długi czas sortowania zbiorów o dużej liczbie elementów, ograniczyliśmy się jedynie do 8000 elementów. Program testujący jest następujący:

 

DevPascal
// 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 Glupie - Stupid Sort';
  K1    = '----------------------------------------';
  K2    = '(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie';
  K3    = '------n---------tpo---------tod---------tpp---------tpk---------tnp';
  K4    = '-------------------------------------------------------------------';
  MAX_LN = 4; // 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 : integer;
  x : real;
begin
  QueryPerformanceCounter(addr(qpc1));
  i := 1;
  repeat
    if d[i] > d[i+1] then // Porządek rosnący
    begin
      x := d[i]; d[i] := d[i+1]; d[i+1] := x;
      i := 1;
      continue;
    end;
    inc(i);
  until i = n;
  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 - najlepiej na noc):

 

Zawartość pliku wygenerowanego przez program
Nazwa: Sortowanie Glupie - Stupid Sort
----------------------------------------
(C)2011/2012 I Liceum Ogolnoksztalcace w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
1000 0.000006 1.087045 0.001226 0.002302 0.676225
2000 0.000012 7.998662 0.005473 0.010103 5.377530
4000 0.000024 64.041837 0.020801 0.030448 43.222395
8000 0.000050 513.938879 0.043996 0.087417 343.565348
-------------------------------------------------------------------
Koniec

Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):

n -  ilość elementów w sortowanym zbiorze
tpo -  czas sortowania zbioru posortowanego
tod -  czas sortowania zbioru posortowanego malejąco
tpp -  czas sortowania zbioru posortowanego z losowym elementem na początku
tpk -  czas sortowania zbioru posortowanego z losowym elementem na końcu
tnp -  czas sortowania zbioru z losowym rozkładem elementów

(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)

 

Podsumowanie

Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów sortowania dla algorytmu sortowania głupiego wyciągamy następujące wnioski

 

Cechy Algorytmu Sortowania Głupiego
klasa złożoności obliczeniowej optymistyczna O(n) - O(n2)
klasa złożoności obliczeniowej typowa O(n3)
klasa złożoności obliczeniowej pesymistyczna O(n3)
Sortowanie w miejscu TAK
Stabilność TAK

 

Klasy złożoności obliczeniowej szacujemy następująco:

Własności algorytmu
Algorytm tpo tod tpp tpk tnp
Sortowanie głupie O(n) O(n3) O(n2) O(n2) O(n3)
tpo << tod
tpp 1 tpk
2
tnp 2 tod
3
  1. Dla zbioru już posortowanego klasa czasowej złożoności obliczeniowej wynosi O(n) - liniowa. Czas sortowania jest pomijalnie mały.
  2. Dla zbioru posortowanego odwrotnie klasa czasowej złożoności obliczeniowej wynosi O(n3) - sześcienna, a czas sortowania jest najdłuższy z otrzymanych, jest to zatem przypadek najbardziej niekorzystny.
  3. Dla zbioru posortowanego z losowym elementem na początku klasa czasowej złożoności obliczeniowej wynosi O(n2) - kwadratowa. Czas sortowania jest bardzo mały w porównaniu z czasem sortowania zbioru nieuporządkowanego.
  4. Dla zbioru posortowanego z losowym elementem na końcu klasa czasowej złożoności obliczeniowej wynosi O(n2) - kwadratowa.
  5. Dla zbioru o losowym rozkładzie elementów klasa czasowej złożoności obliczeniowej wynosi O(n3) - sześcienna. Czas sortowania jest krótszy w porównaniu z czasem sortowania zbioru uporządkowanego odwrotnie.

Zadania dla ambitnych

  1. Z uwagi na bardzo długi czas pracy programu testującego musieliśmy ograniczyć do 8000 elementów badanie czasów sortowania dla algorytmu sortowania głupiego. Na podstawie wyników oszacuj przybliżone czasy dla 16000, 32000, 64000 oraz 128000 elementów (zadanie możesz rozwiązać pisząc odpowiedni program lub wykorzystując do obliczeń arkusz kalkulacyjny). Jak długo musiałby pracować nasz program testowy, aby zebrać wszystkie te wyniki? Wykorzystaj informację o ilości sortowań każdego typu wykonywanych w programie testującym.
  2. Dlaczego czas tpo ma liniową czasową złożoność obliczeniową?
  3. Uzasadnij, iż dla czasów tpp i tpk algorytm wykazuje kwadratową złożoność obliczeniową.

 



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.