Sortowanie naiwne 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 naiwnego 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).
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
krok 1: Dla i = 1,2,...,n - 1: wykonuj krok 2 krok 2: Jeśli d[i] > d[i + 1], to zamień d[i] d[i + 1] i rozpocznij od nowa pętlę w kroku 1
krok 3: Zakończ algorytm
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.
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 Naiwne
//-------------------------------------------------
// (C)2005 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 naiwne ');
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.
// Sortowanie Naiwne
//-------------------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-------------------------------------------------
#include
#include
#include
using namespace std;
const int N = 20; // Liczebność zbioru.
// Program główny
//---------------
int main()
{
int d[N],i;
cout << " Sortowanie naiwne\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;
system("PAUSE"); return 0;
}
' Sortowanie Naiwne
'-------------------------------------------------
' (C)2005 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 naiwne "
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 * 100): NEXT
PRINT "Przed sortowaniem:"
FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
' 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"
FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
PRINT "Nacisnij Enter...";
SLEEP
END
"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">
"text-align: center">Sortowanie Naiwne
"TEXT-ALIGN: center">
(C)2005 mgr Jerzy Wałaszek - I LO w Tarnowie
"TEXT-ALIGN: center">
"main()" type="button" value="Sortuj" name="B1">
"t_out" style="TEXT-ALIGN: center">...
javascript>
// Sortowanie Naiwne
//-------------------------------------------------
// (C)2005 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:
";
for(i = 0; i < N; i++) t += d[i] + " ";
t += "
";
// 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:
";
for(i = 0; i < N; i++) t += d[i] + " ";
document.getElementById("t_out").innerHTML = t;
}
W celach badawczych testujemy czas wykonania algorytmu sortowania naiwnego 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:
// Program testujący czas sortowania dla
// danego algorytmu sortującego
//--------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie
//--------------------------------------
program TestCzasuSortowania;
uses Windows;
const
NAZWA = 'Sortowanie Naiwne - Stupid Sort';
K1 = '----------------------------------------';
K2 = '(C)2005 mgr J.Wałaszek I LO 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 Naiwne - Stupid Sort Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):
|
(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)
Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów sortowania dla algorytmu sortowania naiwnego wyciągamy następujące wnioski
| Cechy Algorytmu Sortowania Naiwnego | |
|---|---|
| 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:
- optymistyczna - dla zbiorów uporządkowanych (z niewielką liczbą elementów nie na swoich miejscach) - na podstawie czasów tpo, tpp, tpk
- typowa - dla zbiorów o losowym rozkładzie elementów - na podstawie czasu tnp
- pesymistyczna - dla zbiorów posortowanych odwrotnie - na podstawie czasu tod.
| Własności algorytmu | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Algorytm | tpo | tod | tpp | tpk | tnp | |||||||
| Sortowanie naiwne | O(n) | O(n3) | O(n2) | O(n2) | O(n3) | |||||||
| tpo << tod |
|
| ||||||||||
- Dla zbioru już posortowanego klasa czasowej złożoności obliczeniowej wynosi O(n) - liniowa. Czas sortowania jest pomijalnie mały.
- 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.
- 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.
- Dla zbioru posortowanego z losowym elementem na końcu klasa czasowej złożoności obliczeniowej wynosi O(n2) - kwadratowa.
- 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.
-
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 naiwnego. Na podstawie otrzymanych 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.
-
Dlaczego czas tpo ma liniową czasową złożoność obliczeniową?
-
Uzasadnij, iż dla czasów tpp i tpk algorytm wykazuje kwadratową złożoność obliczeniową.
GNU Free Documentation License.
Źródło: http://www.i-lo.tarnow.pl/edu/inf/alg/algsort/index.html