Lösung

Bubblesort

bubbleSort.m

 function bubbleSort(X)
 global maxval n swaps
 
 for ii = 1:n-1
 for jj=n-1:-1:ii
 if X(jj)>X(jj+1)
 zw = X(jj);
 X(jj) = X(jj+1);
 X(jj+1) = zw;
 swaps = swaps + 1;
 end
 end
 end

Insertionsort

insertionSort.m

 function insertionSort(X)
 global maxval n swaps
 
 for ii = 1:n
 zw = X(ii);
 jj = 1;
 
 while X(jj) < X(ii)
 jj = jj+1;
 end
 
 for kk = ii:-1:jj+1
 X(kk) = X(kk-1);
 swaps = swaps + 1;
 end
 
 X(jj) = zw;
 end

Selectionsort

selectionSort.m

function W = selectionSort(W)
 swaps = 0;
 vergleiche = 0;
 n = length(W);
 
 for ii=1:n-1
 nextElement = ii;
 
 for jj = ii+1:n
 vergleiche = vergleiche+1;
 
 if W(nextElement) > W(jj)
 nextElement = jj;
 end
 end
 
 if ~(nextElement == ii)
 zw = W(ii);
 W(ii) = W(nextElement);
 W(nextElement) = zw;
 swaps = swaps+1;
 end
 end
 
 disp([num2str(vergleiche) ' ist die Anzahl der Vergleiche']);
 disp([num2str(swaps) ' ist die Anzahl der Vertauschungen']);

Quicksort

quicksort.m

function quicksort(l,r)
 global V swaps
 
 if r > l
 v = V(r);
 ii = l-1;
 jj = r;
 
 while true
 while true
 ii = ii + 1;
 if (V(ii) >= v) | (ii == r)
 break
 end
 end
 
 while true
 jj = jj-1;
 if (V(jj) <= v) | (jj == l)
 break
 end
 end
 
 t = V(ii);
 V(ii) = V(jj);
 V(jj) = t;
 swaps = swaps +1;
 
 if jj <= ii
 break
 end
 end
 
 V(jj) = V(ii);
 V(ii) = V(r);
 V(r) = t;
 swaps = swaps +1;
 quicksort(l,ii-1);
 quicksort(ii+1,r);
 end

Kontroll-Programm

Im Folgenden wird ein Programm dargestellt, welches verschiede ne Vektoren mit zufälligen Zahlen generiert und auf diese dann die Sortier-Algorithen anwendet. Besonders interessant sind dabei die Vergleichsoperationen, die Vertauschungoperationen und die Laufzeit.

Es sollen verschiedene Feldmengen überprüft werden, daher wird die Anzahl der Feldelemente sukzessive erhöht. Erst ab einer bestimmten Anzahl von Elementen erkennt man die besseren Laufzeiten mancher Algorithmen.

compare.m

% compares the performance of sorting algorithms
 
 %% Initialisierung
 % alles löschen
 clear all
 clc
 close all
 tic
 
 % hier werden die globalen Varialben definiert.
 global V maxval n step swaps
 
 % Definition der Laufparameter
 multiplier = 500; % Schrittweite für die Länge der Vektoren
 maxval = 1;
 swaps = 0;
 
 runs = 12; % Anzahl der Durchläufe
 P_times = zeros(runs,4);
 p_swaps = zeros(runs,4);
 num_elements = [1:runs]*multiplier; % Berechnung der verschiedenen Längen der Zufallsvektoren
 
 %% Hier gehen die verschiedenen Testläufe los
 fprintf(' %5.3f Start calc 
 %5i run ',toc,runs)
 for ii=1:runs
 n = num_elements(ii);
 Org = rand(n,maxval); % Generieren des Zufallsvektors
 V = Org;
 
 tzw = cputime; % Zwischenzeit aufzeichnen
 swaps = 0; % Zurücksetzen der vertauschungsvorgänge
 quicksort(1,n); % Ausführen des Algorithmus
 p_times(ii,1) = cputime - tzw; % aufzeichnen der Laufzeit
 p_swaps(ii,1) = swaps; % aufzeichnen der Vertauschungvorgänge (global)
 
 tzw = cputime;
 swaps = 0;
 selectionSort(Org);
 p_times(ii,2) = cputime - tzw;
 p_swaps(ii,2) = swaps;
 
 tzw = cputime;
 swaps = 0;
 bubbleSort(Org)
 p_times(ii,3) = cputime - tzw;
 p_swaps(ii,3) = swaps;
 
 tzw = cputime;
 swaps = 0;
 insertSort(Org)
 p_times(ii,4) = cputime - tzw;
 p_swaps(ii,4) = swaps;
 
 fprintf('\b\b\b\b\b\b\b %5i ',ii); % Fortschrittsanzeige
 end
 
 
 %% Ausgabe der Ergebnisse
 % die Laufzeiten einmal unskaliert, dann halblogarithmisch
 fprintf('

 %5.3f ENDE calc
',toc)
 fh1 = figure('Name','Laufzeiten');
 subplot(2,1,1)
 plot(num_elements,p_times(:,1),num_elements,p_times(:,2), ...
 num_elements,p_times(:,3),num_elements,p_times(:,4))
 legend('Quick','Selection','Bubble','Insert',2)
 grid on
 ylabel('Laufzeit [s]')
 
 subplot(2,1,2)
 semilogy(num_elements,p_times(:,1),num_elements,p_times(:,2), ...
 num_elements,p_times(:,3),num_elements,p_times(:,4))
 grid on
 xlabel('Anzahl der Elemente')
 ylabel('Laufzeit [s]')
 
 % Analog die Tauschoperationen.
 fh2 = figure('Name','Tauschoperationen');
 subplot(2,1,1)
 plot(num_elements,p_swaps(:,1),num_elements,p_swaps(:,2), ...
 num_elements,p_swaps(:,3),num_elements,p_swaps(:,4))
 legend('Quick','Selection','Bubble','Insert',2)
 grid on
 ylabel('Tauschvorgänge')
 subplot(2,1,2)
 semilogy(num_elements,p_swaps(:,1),num_elements,p_swaps(:,2), ...
 num_elements,p_swaps(:,3),num_elements,p_swaps(:,4))
 grid on
 xlabel('Anzahl der Elemente')
 ylabel('Tauschvorgänge')
 
 % Die Vergleichsoperatoinen werden hier leider nicht dargestellt

« Vorheriges | Nächste »