Algorytmy Sortujące - Sortowanie Zwariowane

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(n •n!). 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.

do podrozdziału do strony

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.

Krok 1:

Do zmiennej pomocniczej przenosimy drugi element.

X ← B

Krok 2:

Na miejsce drugiego elementu przenosimy element pierwszy.

B ← A

Krok 3:

Na miejsce pierwszego elementu przenosimy element drugi ze zmiennej pomocniczej.

A ← X

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

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 wbudowany generator liczb pseudolosowych. Wygenerowany indeks powinien być liczbą pseudolosową z zakresu od 1 do n (w C++, JavaScript i Pythonieobowią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);
Python	import random ... indeks = random.randrange(n)

do podrozdziału do strony

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
i₁, i₂	- losowe indeksy elementów zbioru d[ ], i₁, i₂ ∈ N

Lista kroków

Algorytm procedury Tasuj

K01:	Dla i = 1,2,...,3 × n: Wykonuj kroki K02...K03
K02:	Wylosuj indeksy i₁, i₂ ∈ [1,n]
K03:	d[i₁] ↔ d[i₂]
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

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

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?

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?

do podrozdziału do strony

C++

// Sortowanie Zwariowane
//---------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie

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

using namespace std;

const int N = 9; // 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;
  system("pause");
  return 0;
}

Pascal

// Sortowanie Zwariowane
//---------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie

program Bogo_Sort;

const N = 9; // Liczebność zbioru. Nie wstawiaj
             // iczb 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.

Basic

' Sortowanie Zwariowane
'---------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' w Tarnowie

  CONST N = 9 ' 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 AS INTEGER i, i1, i2

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

END SUB

Python (dodatek)

# Sortowanie Zwariowane
#---------------------------
# (C)2026 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# w Tarnowie

import random

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

# sortowany zbiór
d = [random.randrange(10000) for i in range(n)]

# Funkcja sprawdzająca uporządkowanie
# w zbiorze d[]
#------------------------------------
def posortowane():
    for i in range(n-1):
        if d[i] > d[i+1]: return False
    return True

# Procedura tasująca zbiór d[]
#-----------------------------
def tasuj():
    for i in range(3 * n):
        i1 = random.randrange(n)
        i2 = random.randrange(n)
        d[i1],d[i2] = d[i2],d[i1]

# Program główny
# --------------

print("Sortowanie  zwariowane")
print("----------------------")
print("(C)2026 Jerzy Wałaszek")
print()

# wyświetlamy zawartość zbioru d[]

print("Przed sortowaniem:")
print()
for i in range(n):
    print(d[i],end=" ")
print()
print()

# Sortujemy zbiór d[]
while not posortowane(): tasuj()

# Wyświetlamy wynik sortowania
print("Po sortowaniu:")
print()
for i in range(n):
    print(d[i], end=" ")
print()
print()

input("Naciśnij Enter...")

Wynik:

Sortowanie  zwariowane
----------------------
(C)2026 Jerzy Wałaszek

Przed sortowaniem:

8668 2322 8017 5362 6492 8771 4723 4643 5743 

Po sortowaniu:

2322 4643 4723 5362 5743 6492 8017 8668 8771

Naciśnij Enter...

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

var N = 9; // 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>

do podrozdziału do strony

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
Sortowanie w miejscu	TAK
Stabilność	NIE

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 zwariowane
Bogo Sort, Bozo Sort, Blort Sort

Algorytm

Szczegóły implementacji

Sprawdzenie posortowania elementów

Losowe potasowanie elementów zbioru

Krok 1:

Krok 2:

Krok 3:

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Algorytm procedury Tasuj

Algorytm funkcji Posortowane

Algorytm główny BogoSort

Schemat blokowy

Uwaga:

Uwaga:

Przykładowe programy

Sortowanie Zwariowane

Podsumowanie

Sortowanie zwariowane Bogo Sort, Bozo Sort, Blort Sort

Algorytm

Szczegóły implementacji

Sprawdzenie posortowania elementów

Losowe potasowanie elementów zbioru

Krok 1:

Krok 2:

Krok 3:

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Algorytm procedury Tasuj

Algorytm funkcji Posortowane

Algorytm główny BogoSort

Schemat blokowy

Uwaga:

Uwaga:

Przykładowe programy

Sortowanie Zwariowane

Podsumowanie

Sortowanie zwariowane
Bogo Sort, Bozo Sort, Blort Sort