Sortowanie zwariowane
           Bogo Sort, Bozo Sort, Blort Sort


Podrozdziały  

 

 

Algorytm

Pierwszy z prezentowanych algorytmów sortujących opiera się na dosyć zwariowanych zasadach. Jego działanie możemy scharakteryzować na przykładzie układania talii kart. Bierzemy talię kart. Sprawdzamy, czy jest ułożona. Jeśli nie, tasujemy ją i znów sprawdzamy ułożenie. Operacje sprawdzania i tasowania wykonujemy dotąd, aż talia nam się ułoży w pożądanej kolejności kart.

Nic nie sortujemy, wręcz dokonujemy operacji odwrotnej - tasowania, a talia może zostać posortowana. Dlaczego? Wynika to z praw rachunku prawdopodobieństwa. Otóż tasowanie powoduje, iż karty przyjmują losowe permutacje swoich położeń. Ponieważ każda permutacja zbioru kart jest równie prawdopodobna (jeśli przy tasowaniu nie oszukujemy), zatem możemy też otrzymać układ uporządkowany. Oczywiście wynik taki pojawia się dosyć rzadko (bądźmy szczerzy - przy dużej liczbie elementów bardzo, bardzo... rzadko). Nie polecamy sortowania tą metodą zbiorów liczniejszych niż 9 elementów.

Algorytm opiera się na losowym sortowaniu zbioru. Tymczasem w komputerze nie mamy tak naprawdę dostępu do liczb czysto losowych. Zadowalamy się ich przybliżeniem, czyli liczbami pseudolosowymi powstającymi na bazie algorytmicznej (dokładny opis tworzenia liczb pseudolosowych znajdziesz w artykule o liczbach pierwszych). Może się zatem zdarzyć, iż nasz generator pseudolosowy nigdy nie wygeneruje potrzebnej sekwencji liczb pseudolosowych, zatem algorytm sortujący nie będzie w stanie ukończyć swojej pracy.

Z tego powodu jest to jeden z najgorszych algorytmów sortujących. Posiada pesymistyczną czasową złożoność obliczeniową klasy O(nn!). Złożoność taką nazywamy złożonością super wykładniczą. Co gorsze, ten sam zbiór raz może zostać błyskawicznie posortowany (gdy akurat mamy szczęście), a innym razem możemy czekać na wynik nawet cały rok (albo jeszcze dłużej). Sortowanie odbywa się w miejscu.

Szczegóły implementacji

Jeśli za pomocą podanego algorytmu chcemy posortować zbiór liczbowy (a takimi się zajmujemy w opracowaniu), to musimy rozwiązać dwa istotne problemy: sprawdzenie posortowania elementów oraz losowe potasowanie.

 

Sprawdzenie posortowania elementów

Aby upewnić się, iż  zbiór jest posortowany, należy porównać ze sobą wszystkie kolejne sąsiednie elementy. Jeśli spełniają założoną kolejność, to zbiór jest uporządkowany. Jeśli chociaż jedna para elementów zbioru jest w złej kolejności ze względu na przyjęty porządek, to zbiór nie jest uporządkowany.

 

Losowe potasowanie elementów zbioru

Operacja ta ma na celu pomieszanie elementów w zbiorze, aby przyjęły przypadkowe pozycje. Najprościej dokonamy tego, losując dwa numery elementów, a następnie zamieniając wylosowane elementy miejscami. Jeśli operację taką powtórzymy wystarczającą liczbę razy (np. 3-krotną liczbę elementów w zbiorze), to zawartość zbioru zostanie potasowana (wymieszana).

Podstawową operacją jest zamiana zawartości dwóch elementów zbioru. Wymaga ona trzech kroków oraz zmiennej pomocniczej do tymczasowego przechowania jednego z elementów.

W pierwszym kroku przenosimy do zmiennej pomocniczej jeden z elementów. W drugim kroku na zwolnione miejsce wstawiamy drugi z elementów, a na koniec w kroku trzecim na miejsce drugiego elementu przenosimy element zapamiętany w zmiennej pomocniczej. Obok prezentujemy w formie graficznej tę prostą zasadę.

Pascal
x := a; a := b; b := x;
C++ i JavaScript
x = a; a = b; b = x;

Operację zamiany zawartości dwóch elementów w algorytmach przedstawianych w postaci listy kroków będziemy oznaczali symbolem: ↔

Kolejna operacja to losowanie indeksu elementu. Wykorzystamy tutaj generator liczb pseudolosowych. Wygenerowany indeks powinien być liczbą pseudolosową z zakresu od 1 do n (w C++ i JavaScript obowiązuje zakres od 0 do n-1), gdzie n oznacza ilość elementów w zbiorze. Operację tę wykonujemy następująco:

Pascal
indeks := 1 + random(n);
C++
indeks = rand() % n;
JavaScript
indeks = Math.floor(Math.random() * n);

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
i1, i2 - losowe indeksy elementów zbioru d[ ], i1, i2 N

 

Lista kroków

Algorytm procedury Tasuj

K01: Dla i = 1,2,...,3 × nwykonuj K02...K03
K02:     Wylosuj indeksy i1, i2 <1,n>
K03:     d[i1] ↔ d[i2]
K04: Zakończ

Algorytm funkcji Posortowane

K01: Dla i = 1,2,...,n - 1,  jeśli d[i] > d[i + 1], to Posortowane ← false i zakończ
K02: Posortowane ← true
K03: Zakończ

Algorytm główny BogoSort

K01: Dopóki Posortowane = false: Tasuj
K02: Zakończ

 

Schemat blokowy

flow

Trzon algorytmu stanowi pojedyncza pętla warunkowa typu while. Na początku wywołana zostaje funkcja sprawdzająca posortowanie zbioru - Posortowane?. Jeśli da wynik pozytywny, kończymy algorytm.

Przy wyniku negatywnym wywołujemy procedurę tasowania elementów zbioru - Tasuj i pętla jest powtarzana aż do skutku (który może nigdy nie nastąpić z powodu niedoskonałości generacji liczb pseudolosowych! - zobacz na uwagi umieszczone na początku rozdziału).

flow


Algorytm funkcji Posortowane? zbudowany jest z pojedynczej pętli iteracyjnej sterowanej zmienną licznikową i. Zmienna i pełni rolę indeksu kolejno porównywanych elementów sortowanego zbioru. Sprawdzamy, czy zbiór jest posortowany rosnąco (dla porządku malejącego należy zamienić w teście kolejności elementów zbioru relację większości na relację mniejszości).

Wykonanie pętli rozpoczynamy od pierwszego elementu i kontynuujemy do przedostatniego (tzn. o numerze n - 1). Element i-ty oraz (i + 1)-wszy porównujemy ze sobą. Jeśli relacja jest spełniona, to elementy te są w złej kolejności (większy jest przed mniejszym).  W takim przypadku wiemy natychmiast, iż zbiór jest nieposortowany. Przerywamy zatem wykonywanie pętli iteracyjnej, zwracamy jako wynik działania funkcji wartość logiczną false i kończymy algorytm.

Jeśli relacja w teście nie będzie spełniona, zwiększamy o 1 indeks i rozpoczynamy następny obieg pętli.

Jeśli pętla wykona się do końca, to znaczy, iż wszystkie elementy zbioru są w dobrym porządku. Jako wynik funkcji zwracamy wartość logiczną true i kończymy algorytm.

 

Uwaga:

Sprawdź, jak zachowa się ten sam algorytm dla zbioru pustego (tzn. przy n = 0) oraz dla zbioru jednoelementowego (tzn. n = 1). Jakie wyciągniesz stąd wnioski?

 

flow

Tasowanie elementów zbioru jest operacją odwrotną do ich sortowania. Tutaj celem będzie losowe ustawienie elementów.

Trzonem algorytmu jest pętla iteracyjna wykonująca się 3n razy. Ilość wykonań można dobrać doświadczalnie - my przyjęliśmy trzykrotną ilość elementów w tasowanym zbiorze.

Pojedyncza operacja tasowania polega na wylosowaniu dwóch indeksów w zakresie od 1 do n, a następnie zamianie zawartości elementów zbioru o tych indeksach. W wyniku elementy zbioru zostaną rozmieszczone losowo.

Zapamiętaj ten algorytm - bardzo przydaje się on w różnych grach losowych, gdzie należy coś pomieszać (na przykład wszelkie gry karciane).

 

Uwaga:

Sprawdź co się stanie, gdy wylosowane zostaną dwa takie same indeksy. Czy musimy się tego obawiać przy tasowaniu zbioru?


Programy

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

Przed sortowaniem:

  2043  6751  8525  2306  3923  7457  9686  5862

Po sortowaniu:

  2043  2306  3923  5862  6751  7457  8525  9686

 

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

program Bogo_Sort;

const N = 8; // Liczebność zbioru. Nie wstawiaj liczb
             // większych od 9, bo możesz się nie
             // doczekać rozwiązania
var
  d : array[1..N] of integer;

// Funkcja sprawdzająca uporządkowanie w zbiorze
//-----------------------------------------------------
function Posortowane : boolean;
var
  i : integer;
begin
  for i := 1 to N - 1 do
    if d[i] > d[i+1] then
    begin
      Posortowane := false; Exit;
    end;
  Posortowane := true;
end;

// Procedura tasująca zbiór
//-------------------------
procedure Tasuj;
var
  i,i1,i2,x : integer;
begin
  for i := 1 to 3 * N do
  begin
    i1 := 1 + random(N); i2 := 1 + random(N);
    x := d[i1]; d[i1] := d[i2]; d[i2] := x;
  end;
end;

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

var
  i : integer;
begin
  writeln('Sortowanie  zwariowane');
  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(10000);
  writeln('Przed sortowaniem:'); writeln;
  for i := 1 to N do write(d[i] : 6);
  writeln; writeln;

// Sortujemy

  while not Posortowane do Tasuj;

// Wyświetlamy wynik sortowania

  writeln('Po sortowaniu:'); writeln;
  for i := 1 to N do write(d[i] : 6);
  writeln; writeln;
  writeln('Nacisnij Enter...');
  readln;
end.
Code::Blocks
// Sortowanie Zwariowane
//--------------------------------------------------------
// (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 = 8; // Liczebność zbioru. Nie wstawiaj liczb
                 // większych od 9, bo możesz się nie
                 // doczekać rozwiązania
int d[N];

// Funkcja sprawdzająca uporządkowanie w zbiorze
//-----------------------------------------------------
bool Posortowane()
{
  int i;

  for(i = 0; i < N - 1; i++) if(d[i] > d[i+1]) return false;
  return true;
}

// Procedura tasująca zbiór
//-------------------------
void Tasuj()
{
  int i,i1,i2;

  for(i = 1; i <= 3 * N; i++)
  {
    i1 = rand() % N; i2 = rand() % N;
    swap(d[i1], d[i2]);
  }
}

//******************************************************

int main()
{
  int i;

  cout << "Sortowanie  zwariowane\n"
          "----------------------\n"
          "(C)2005 Jerzy Walaszek\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() % 10000;
  cout << "Przed sortowaniem:\n\n";
  for(i = 0; i < N; i++) cout << setw(6) << d[i];
  cout << endl << endl;

// Sortujemy

  while(!Posortowane()) Tasuj();

// Wyświetlamy wynik sortowania

  cout << "Po sortowaniu:\n\n";
  for(i = 0; i < N; i++) cout << setw(6) << d[i];
  cout << endl << endl;
  return 0;
}
Free Basic
' Sortowanie Zwariowane
' --------------------------------------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'--------------------------------------------------------

  OPTION EXPLICIT

  CONST N = 8  ' Liczebność zbioru. Nie wstawiaj liczb
               ' większych od 9, bo możesz się nie
               ' doczekać rozwiązania

  DIM SHARED d(1 TO N) AS INTEGER

  DECLARE FUNCTION Posortowane() AS INTEGER

  DECLARE SUB Tasuj()

' Program główny
' --------------

  DIM i AS INTEGER

  PRINT "Sortowanie  zwariowane"
  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 * 10000): NEXT
  PRINT "Przed sortowaniem:"
  PRINT
  FOR i = 1 TO N: PRINT USING "######"; d(i);: NEXT
  PRINT
  PRINT

' Sortujemy

  WHILE Posortowane() = 0: Tasuj(): WEND

' 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

' Funkcja sprawdzająca uporządkowanie w zbiorze
'-----------------------------------------------------
PUBLIC FUNCTION Posortowane() AS INTEGER

  DIM  i AS INTEGER

  FOR i = 1 TO N - 1
    IF d(i) > d(i+1) THEN
      Posortowane = 0: EXIT FUNCTION
    END IF
  NEXT
  Posortowane = 1

END FUNCTION

' Procedura tasująca zbiór
'-------------------------
PUBLIC SUB Tasuj()

  DIM i AS INTEGER, i1 AS INTEGER, i2 AS INTEGER

  FOR i = 1 TO 3 * N
    i1 = 1 + INT(RND * N)
    i2 = 1 + INT(RND * N)
    SWAP d(i1), d(i2)
  NEXT

END SUB
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="frmbogosort">
      <h3 style="text-align: center">Sortowanie Zwariowane</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 Zwariowane
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

var N = 8; // Liczebność zbioru. Nie wstawiaj liczb
           // większych od 9, bo możesz się nie
           // doczekać rozwiązania

var d = Array(N);

// Funkcja sprawdzająca uporządkowanie w zbiorze
//-----------------------------------------------------
function Posortowane()
{
  var i;

  for(i = 0; i < N - 1; i++) if(d[i] > d[i+1]) return false;
  return true;
}

// Procedura tasująca zbiór
//-------------------------
function Tasuj()
{
  var i,i1,i2,x;

  for(i = 1; i <= 3 * N; i++)
  {
    i1 = Math.floor(Math.random() * N); i2 = Math.floor(Math.random() * N);
    x = d[i1]; d[i1] = d[i2]; d[i2] = x;
  }
}

//******************************************************

function main()
{
  var i,t;

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

  for(i = 0; i < N; i++) d[i] = Math.floor(Math.random() * 10000);
  t = "Przed sortowaniem:<BR><BR>";
  for(i = 0; i < N; i++) t += d[i] + " ";
  t += "<BR><BR>";

// Sortujemy

  while(!Posortowane()) Tasuj();

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

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


...

 

Podsumowanie

Zaprezentowany algorytm jest ekstremalnie złym algorytmem sortującym i na pewno nikt o zdrowych zmysłach nie będzie go stosował. Jednakże zawiera dwa ciekawe składniki, które można wykorzystywać w "poważniejszych" projektach programistycznych: sprawdzanie posortowania zbioru oraz tasowanie elementów zbioru.

Algorytmu Bogo Sort nie testujemy w naszym programie badania czasów sortowania, ponieważ, jak zdążyliście się zorientować, nawet posortowanie 10 elementów może zająć całkiem sporą chwilę czasu. W ramach eksperymentu próbowałem posortować tym algorytmem zbiór 12 liczb, lecz muszę szczerze przyznać, iż po dwóch godzinach czekania zniecierpliwiony zakończyłem program w sposób awaryjny. Posortowanie 1000 liczb wydaje się niewykonalne w tym miliardoleciu.

Jako ciekawostkę podam fakt, iż informatycy terminem "bogo sort" określają program lub algorytm, którego idea działania jest tak beznadziejnie głupia, iż praktycznie nie może dać rozwiązania w sensownym czasie. Zatem jeśli usłyszysz zdanie: "twój program to bogo sort", to już będziesz wiedział o co chodzi rozmówcy... :)

Cechy Algorytmu Sortowania Zwariowanego
klasa złożoności obliczeniowej O(n × n!)
Sortowanie w miejscu TAK
Stabilność NIE

 



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.