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.
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 C++ i JavaScript 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 C++ JavaScript
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 i1, i2 - losowe indeksy elementów zbioru d[ ], i1, i2
Algorytm główny BogoSort
krok 1: Dopóki Posortowane = false: Tasuj krok 2: Zakończ algorytm Algorytm funkcji Posortowane
krok 1: Dla i = 1,2,...,n - 1, jeśli d[i] > d[i + 1], to Posortowane false i zakończ algorytm
krok 2: Posortowane Algorytm procedury Tasuj
krok 1: Dla i = 1,2,...,3 krok 2: Wylosuj indeksy i1 i i2 w przedziale od 1 do n krok 3: Wymień zawartości d[i1] d[i2]
krok 4: Zakończ algorytm
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.
Sprawdź, jak zachowa się ten algorytm dla zbioru pustego (tzn. 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).
Sprawdź co się stanie, gdy wylosowane zostaną dwa takie same indeksy. Czy musimy się tego obawiać przy tasowaniu zbioru?
Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.
| Efekt uruchomienia programu |
|---|
// Sortowanie Zwariowane
//-------------------------------------------------
// (C)2005 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.
// Sortowanie Zwariowane
//-------------------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-------------------------------------------------
#include <cmath>
#include <iostream>
#include <iomanip>
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;
system("PAUSE");
return 0;
}
' Sortowanie Zwariowane
' -------------------------------------------------
' (C)2005 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"
' 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:"
FOR i = 1 TO N: PRINT USING "######"; d(i);: NEXT
' Sortujemy
WHILE Posortowane() = 0: Tasuj(): WEND
' Wyświetlamy wynik sortowania
PRINT "Po sortowaniu:"
FOR i = 1 TO N: PRINT USING "######"; d(i);: NEXT
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
<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)2005 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)2005 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>
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 okresie czasu. 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 x n!) |
| Sortowanie w miejscu | TAK |
| Stabilność | NIE |
GNU Free Documentation License.
Źródło: mgr Jerzy Wałaszek