Vergleich von Sortieralgorithmen

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
%% Die Funktion implementiert den Insertion-Sort Algorithmus
%  Parameter:
%       x: Das Array, das sortiert werden soll
function y = insertionSort(x)
    n = length(x);
    for ii = 2:n % Fange bei 2 an da immer mit der vorherigen Stelle im Array verglichen wird (die erste Stelle hat keinen Vorgänger)
        zw = x(ii); % Speichere den Wert an der aktuellen Stelle, der verglichen werden soll, in einer Zwischenvariable
        jj = ii ; % Nutze einen Zähler und inkrementiere den mit dem Wert von ii, um es in der nächsten Schleife zu nutzen
        while (jj > 1 && x(jj-1) > zw) % Benutze eine while Schleife, weil nicht vorher bekannt ist, wie oft iteriert werden muss
                                    % Die Bedingungen für die Schleife sind:
                                    % 1. stoppe wenn das erste Element erreicht wurde
                                    % 2. iteriere solange, bis die Zwischenvariable an der richtigen Stelle im sortierten Feld ist.

            % Hier ist zw noch nicht an der richtigen Stelle im sortierten Feld, verschiebe also das vorherige Element um eins nach hinten
            x(jj) = x(jj-1);
            jj = jj-1; % und setze die Stelle um eine Position weiter nach vorne

        end
        % Hier sind alle größeren Werte als zw einmal nach hinten
        % verschoben worden und jj ist an der richtigen Position, um den
        % Wert einzufügen
        x(jj) = zw; % Füge also den Wert an die Position jj ein
    end
    y = x;
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 Variablen 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