Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
Jeśli przeczytałeś uważnie poprzednie dwa rozdziały, to zasadę sortowania przez kopcowanie zrozumiesz od razu - w zbiorze tworzymy kopiec, a następnie dokonujemy jego rozbioru. W wyniku wykonania tych dwóch operacji zbiór zostanie posortowany.
d[ ] | - Zbiór zawierający elementy do posortowania, które są numerowane począwszy od 1. |
n | - Ilość elementów w zbiorze, n ∈ N |
d[ ] | - Zbiór zawierający elementy posortowane rosnąco |
Twórz_kopiec | - | procedura budująca kopiec z elementów zbioru d[ ]. Kopiec powstaje w zbiorze d[ ]. |
Rozbierz_kopiec | - | procedura dokonująca rozbioru kopca utworzonego w zbiorze d[ ]. Wynik rozbioru trafia z powrotem do zbioru d[ ]. |
K01: | Twórz_kopiec |
K02: | Rozbierz_kopiec |
K03: | Zakończ algorytm |
Ponieważ sortowanie przez kopcowanie składa się z dwóch następujących
bezpośrednio po sobie operacji o klasie czasowej złożoności obliczeniowej
C++// Sortowanie przez kopcowanie //-------------------------------------------------------- // (C)2012 mgr Jerzy Wałaszek // I Liceum Ogólnokształcące // im. K. Brodzińskiego // w Tarnowie //-------------------------------------------------------- #include <iostream> #include <iomanip> #include <cstdlib> #include <time.h> using namespace std; int main() { const int N = 20; // liczebność zbioru int d[N + 1],i,j,k,m,x; srand((unsigned)time(NULL)); cout << " Sortowanie przez kopcowanie \n" "-----------------------------\n" " (C)2005 Jerzy Walaszek\n\n" "Przed sortowaniem:\n\n"; // Wypełniamy tablicę liczbami pseudolosowymi i wyświetlamy je for(i = 1; i <= N; i++) { d[i] = rand() % 100; cout << setw(4) << d[i]; } cout << endl; // Budujemy kopiec for(i = 2; i <= N; i++) { j = i; k = j / 2; x = d[i]; while((k > 0) && (d[k] < x)) { d[j] = d[k]; j = k; k = j / 2; } d[j] = x; } // Rozbieramy kopiec for(i = N; i > 1; i--) { swap(d[1], d[i]); j = 1; k = 2; while(k < i) { if((k + 1 < i) && (d[k + 1] > d[k])) m = k + 1; else m = k; if(d[m] <= d[j]) break; swap(d[j], d[m]); j = m; k = j + j; } } // Wyświetlamy wynik sortowania cout << "Po sortowaniu:\n\n"; for(i = 1; i <= N; i++) cout << setw(4) << d[i]; cout << endl; return 0; } |
Pascal// Sortowanie przez kopcowanie //-------------------------------------------------------- // (C)2012 mgr Jerzy Wałaszek // I Liceum Ogólnokształcące // im. K. Brodzińskiego // w Tarnowie //-------------------------------------------------------- program heap_sort; const N = 20; // liczebność zbioru var d : array[1..N] of integer; i,j,k,m,x : integer; begin writeln(' Sortowanie przez kopcowanie '); writeln('-----------------------------'); writeln(' (C)2005 Jerzy Walaszek'); writeln; writeln('Przed sortowaniem:'); writeln; // Wypełniamy tablicę liczbami pseudolosowymi i wyświetlamy je randomize; for i := 1 to N do begin d[i] := random(100); write(d[i] : 4); end; // Budujemy kopiec for i := 2 to N do begin j := i; k := j div 2; x := d[i]; while (k > 0) and (d[k] < x) do begin d[j] := d[k]; j := k; k := j div 2; end; d[j] := x; end; // Rozbieramy kopiec for i := N downto 2 do begin x := d[1]; d[1] := d[i]; d[i] := x; j := 1; k := 2; while k < i do begin if (k + 1 < i) and (d[k + 1] > d[k]) then m := k + 1 else m := k; if d[m] <= d[j] then break; x := d[j]; d[j] := d[m]; d[m] := x; j := m; k := j + j; end; end; // Wyświetlamy wynik sortowania writeln('Po sortowaniu:'); writeln; for i := 1 to N do write(d[i] : 4); writeln; writeln('Nacisnij Enter...'); readln; end. |
Basic' Sortowanie przez kopcowanie '-------------------------------------------------------- ' (C)2012 mgr Jerzy Wałaszek ' I Liceum Ogólnokształcące ' im. K. Brodzińskiego ' w Tarnowie '-------------------------------------------------------- CONST N = 20 ' liczebność zbioru DIM d(N) AS INTEGER, i AS INTEGER, j AS INTEGER DIM k AS INTEGER, m AS INTEGER, x AS INTEGER PRINT " Sortowanie przez kopcowanie" PRINT "-----------------------------" PRINT " (C)2005 Jerzy Walaszek" PRINT PRINT "Przed sortowaniem:": PRINT ' Wypełniamy tablicę liczbami pseudolosowymi i wyświetlamy je RANDOMIZE FOR i = 1 TO N d(i) = INT(RND * 100): PRINT USING "####";d(i); NEXT PRINT ' Budujemy kopiec FOR i = 2 TO N j = i: k = j \ 2 x = d(i) WHILE (k > 0) AND (d(k) < x) d(j) = d(k) j = k: k = j / 2 WEND d(j) = x NEXT ' Rozbieramy kopiec FOR i = N TO 2 STEP -1 SWAP d(1), d(i) j = 1: k = 2 WHILE k < i IF (k + 1 < i) AND (d(k + 1) > d(k)) THEN m = k + 1 ELSE m = k END IF IF d(m) <= d(j) THEN EXIT WHILE SWAP d(j), d(m) j = m: k = j + j WEND NEXT ' Wyświetlamy wynik sortowania PRINT "Po sortowaniu:": PRINT FOR i = 1 TO N: PRINT USING "####";d(i);: NEXT PRINT PRINT "Nacisnij Enter..." SLEEP END |
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="frmheapsort"> <h3 style="text-align: center">Sortowanie Przez Kopcowanie</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 Przez Kopcowanie //-------------------------------------------------------- // (C)2012 mgr Jerzy Wałaszek // I Liceum Ogólnokształcące // im. K. Brodzińskiego // w Tarnowie //-------------------------------------------------------- function main() { var N = 20; // liczba elementów var d = new Array(N + 1); var i,j,k,x,t; // Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi for(i = 1; i <= N; i++) d[i] = Math.floor(Math.random() * 100); t = "Przed sortowaniem:<BR><BR>"; for(i = 1; i <= N; i++) t += d[i] + " "; t += "<BR><BR>"; // Budujemy kopiec for(i = 2; i <= N; i++) { j = i; k = Math.floor(j / 2); x = d[i]; while((k > 0) && (d[k] < x)) { d[j] = d[k]; j = k; k = Math.floor(j / 2); } d[j] = x; } // Rozbieramy kopiec for(i = N; i > 1; i--) { x = d[1]; d[1] = d[i]; d[i] = x; j = 1; k = 2; while(k < i) { if((k + 1 < i) && (d[k + 1] > d[k])) m = k + 1; else m = k; if(d[m] <= d[j]) break; x = d[j]; d[j] = d[m]; d[m] = x; j = m; k = j + j; } } // Wyświetlamy wynik sortowania t += "Po sortowaniu:<BR><BR>"; for(i = 1; i <= N; i++) t += d[i] + " "; document.getElementById("t_out").innerHTML = t; } </script> </body> </html> |
Wynik: |
Sortowanie przez kopcowanie ----------------------------- (C)2005 Jerzy Walaszek Przed sortowaniem: 48 40 48 29 21 11 12 63 77 89 99 97 80 62 64 32 28 5 16 36 Po sortowaniu: 5 11 12 16 21 28 29 32 36 40 48 48 62 63 64 77 80 89 97 99 |
W celach badawczych testujemy czas wykonania algorytmu sortowania przez kopcowanie w środowisku opisanym we wstępie. Program testujący jest następujący:
Pascal// Program testujący czas sortowania dla // danego algorytmu sortującego //-------------------------------------- // (C)2012 mgr Jerzy Wałaszek // I Liceum Ogólnokształcące // w Tarnowie //-------------------------------------- program TestCzasuSortowania; uses Windows; const NAZWA = 'Sortowanie przez kopcowanie'; K1 = '-----------------------------------------------------------'; K2 = '(C)2011/2012 I Liceum Ogolnoksztalcace w Tarnowie'; K3 = '------n---------tpo---------tod---------tpp---------tpk---------tnp'; K4 = '-------------------------------------------------------------------'; MAX_LN = 8; // 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 //------------------------------------------------------- procedure HeapSort; var i,j,k,m : integer; x : real; begin // Budujemy kopiec for i := 2 to n do begin j := i; k := j div 2; x := d[i]; while (k > 0) and (d[k] < x) do begin d[j] := d[k]; j := k; k := j div 2; end; d[j] := x; end; // Rozbieramy kopiec for i := n downto 2 do begin x := d[1]; d[1] := d[i]; d[i] := x; j := 1; k := 2; while k < i do begin if (k + 1 < i) and (d[k + 1] > d[k]) then m := k + 1 else m := k; if d[m] <= d[j] then break; x := d[j]; d[j] := d[m]; d[m] := x; j := m; k := j + j; end; end; end; function Sort : extended; begin QueryPerformanceCounter(addr(qpc1)); HeapSort; 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):
Zawartość pliku wygenerowanego przez program | ||||||||||||||||||
Nazwa: Sortowanie przez kopcowanie Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):
|
(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)
(Arkusz kalkulacyjny Excel do wyznaczania wzrostu prędkości sortowania)
Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów sortowania dla algorytmu sortowania przez kopcowanie wyciągamy następujące wnioski:
Cechy Algorytmu Sortowania Przez Kopcowanie | |
klasa złożoności obliczeniowej optymistyczna | |
klasa złożoności obliczeniowej typowa | |
klasa złożoności obliczeniowej pesymistyczna | |
Sortowanie w miejscu | TAK |
Stabilność | NIE |
Klasy złożoności obliczeniowej szacujemy następująco:
Własności algorytmu | |||||
Algorytm | tpo | tod | tpp | tpk | tnp |
Sortowanie przez kopcowanie | |||||
Wzrost prędkości sortowania | |||||
Algorytmy | tpo | tod | tpp | tpk | tnp |
Sortowanie przez
scalanie Sortowanie przez kopcowanie |
źle |
źle |
źle |
źle |
źle |
Z porównania czasów sortowania wynika jasno, iż przedstawiony tutaj algorytm sortowania przez kopcowanie jest około dwa razy wolniejszy od wcześniej podanego algorytmu sortowania przez scalanie. Zaletą jest sortowanie w miejscu - poprzedni algorytm wymaga dodatkowej pamięci, co może go dyskwalifikować przy sortowaniu dużych zbiorów danych. Do dalszych porównań czasów sortowania będziemy dalej stosowali algorytm sortowania przez scalanie.
Zobacz również na: Drzewo binarne | Tworzenie kopca | Rozbiór kopca
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.