Login lub e-mail Hasło   

Algorytmy sortujące - sortowanie naiwne

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
Sortowanie naiwne jest również bardzo złym algorytmem sortującym, lecz, w przeciwieństwie do opisanego w poprzednim rozdziale sortowania zwariowanego , daje zawsze popr...
Wyświetlenia: 4.774 Zamieszczono 17/10/2006

 

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 N

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

' 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"
PRINT
FOR
i = 1 TO N: PRINT USING "####"; d(i);: NEXT
PRINT
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
----------------------------------------
(C)2005 mgr J.Wałaszek I LO w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
1000 0.000006 1.087045 0.001226 0.002302 0.676225
2000 0.000012 7.998662 0.005473 0.010103 5.377530
4000 0.000024 64.041837 0.020801 0.030448 43.222395
8000 0.000050 513.938879 0.043996 0.087417 343.565348
-------------------------------------------------------------------
Koniec

Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):

n - ilość elementów w sortowanym zbiorze
tpo - czas sortowania zbioru posortowanego
tod - czas sortowania zbioru posortowanego malejąco
tpp - czas sortowania zbioru posortowanego z losowym elementem na początku
tpk - czas sortowania zbioru posortowanego z losowym elementem na końcu
tnp - czas sortowania zbioru z losowym rozkładem elementów

(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
tpp 1 tpk
2
tnp 2 tod
3
  1. Dla zbioru już posortowanego klasa czasowej złożoności obliczeniowej wynosi O(n) - liniowa. Czas sortowania jest pomijalnie mały.
  2. 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.
  3. 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.
  4. Dla zbioru posortowanego z losowym elementem na końcu klasa czasowej złożoności obliczeniowej wynosi O(n2) - kwadratowa.
  5. 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.

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

  2. Dlaczego czas tpo ma liniową czasową złożoność obliczeniową?

  3. Uzasadnij, iż dla czasów tpp i tpk algorytm wykazuje kwadratową złożoność obliczeniową.

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

Podobne artykuły


16
komentarze: 5 | wyświetlenia: 9002
9
komentarze: 0 | wyświetlenia: 2781
49
komentarze: 18 | wyświetlenia: 64970
37
komentarze: 9 | wyświetlenia: 28510
11
komentarze: 2 | wyświetlenia: 33147
7
komentarze: 1 | wyświetlenia: 34646
17
komentarze: 4 | wyświetlenia: 14158
15
komentarze: 5 | wyświetlenia: 32753
13
komentarze: 2 | wyświetlenia: 22958
12
komentarze: 2 | wyświetlenia: 18504
12
komentarze: 3 | wyświetlenia: 29777
11
komentarze: 1 | wyświetlenia: 86393
11
komentarze: 1 | wyświetlenia: 10466
10
komentarze: 1 | wyświetlenia: 34967
 
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