Login lub e-mail Hasło   

Algorytmy sortujące - sortowanie zwariowane

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
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....
Wyświetlenia: 4.381 Zamieszczono 17/10/2006

 


 

 

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

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

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 true i zakończ algorytm

Algorytm procedury Tasuj

krok 1: Dla i = 1,2,...,3 n,  wykonuj kroki 2 i 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"
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

<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

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

Podobne artykuły


16
komentarze: 5 | wyświetlenia: 9006
9
komentarze: 0 | wyświetlenia: 2784
49
komentarze: 18 | wyświetlenia: 64978
37
komentarze: 9 | wyświetlenia: 28520
11
komentarze: 2 | wyświetlenia: 33152
7
komentarze: 1 | wyświetlenia: 34649
17
komentarze: 4 | wyświetlenia: 14183
15
komentarze: 5 | wyświetlenia: 32761
13
komentarze: 2 | wyświetlenia: 22961
12
komentarze: 2 | wyświetlenia: 18506
12
komentarze: 3 | wyświetlenia: 29779
11
komentarze: 1 | wyświetlenia: 86405
11
komentarze: 1 | wyświetlenia: 10475
10
komentarze: 1 | wyświetlenia: 34971
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska