Sortieralgorythmen

« MIME Type in Delphi ermitteln | Home | Einsteigertutorium zu Ruby »

Von Bastian in Allgemeine Artikel | 1.August 2007

Hiermit leite ich ein allgemeineres Tutorial ein, welches seinen Schwerpunkt auf Sortieralgorithmen richtet.
Die Aufgabe irgendwelche Daten nach einer logischen Reihenfolge zu sortieren ist ein Problem, dass sicherlich bereits vielen Programmierern vertraut sind.

In die meisten Programmiersprachen sind Funktionen wie sort() bereits in den Standard Bibliotheken enthalten. Diese erfüllen ihre Aufgabe im Regelfall völlig ausreichend, aber was ist, wenn man etwas anders machen möchte, man beispielsweise keinen Speicherplatz verschwenden darf, oder einem die Bibliotheken nicht zur Verfügung stehen (oder man einfach neugierig ist zu erfahren was unter der Haube passiert)?

Ich werde mich in diesem Tutorial auf Iterative und Rekursive Versionen der Algorithmen beschränken (ich bin mit funktionaler und deduktiver Programmierung nicht sonderlich vertraut). Bevor ich nun die üblichen Algorithmen zum Sortieren vorstellen, insbesondere ihre Idee und eventuell etwas Code (in verschiedenen Sprachen).
Im folgenden sei angenommen, das wir eine Liste (also eine Reihe von Werten, auch Feld oder Array genannt) von Elementen, bei denen eine eindeutige Reihenfolge definiert ist, sortieren wollen.

Selection Sort

Die Idee hinter Selection Sort ist, dass wir immer das Minimum (respektive Maximum) der Liste, die wir sortieren wollen ermitteln und dieses dann am vordersten Platz einfügen. Dieser vorderste Platz wandert durch die Liste durch, somit wird die Liste in aufsteigender (respektive absteigender) Reihenfolge sortiert. Hier nun eine kleine Implementation in C++:

void selSort(vector< int >& arr){
    for(int i = 0; i < arr.size(); i++){
        int min = i;
        for(int j = i + 1; j < arr.size(); j++){
            if(arr[min] > arr[j])
                min = j;
        }
        int t = arr[i];
        arr[i] = arr[min];
        arr[min] = t;
    }
}

Insertion Sort

Wenn man sich eine Liste, die man sortieren möchte aufgeteilt vorstellt. In einen sortierten und einen unsortierten Teil. Wir nehmen nun das erste Element des unsortierten Teils und schieben es solange in den sortierten Teil hinein, bis es seine richtigig einsortierte Position erreicht hat. Dieser Vorgang wird wiederholt, bis die gesamte Liste sortiert ist (diesmal in Java):

void insSort(int[] arr){
    for(int i = 0; i < arr.length - 1; i++){
        for(int j = i + 1; j > 0  && arr[j] < arr[j-1]; j--){
            int t = arr[j - 1];
            arr[j - 1] = arr[j];
            arr[j] = t;
        }
    }
}

Quicksort

Quicksort ist ein wenig schwieriger zu verstehen als die, die vorher implementiert wurden. Wir suchen in unserer Liste nach einer Position, wo links von dieser Position alle Elemente kleiner sind als ein bestimmtes Pivot-Element (Pivot ist das Element an dem wir uns orientieren) und wo rechts davon alle Elemente größer sind.

Dann wird Quicksort rekursiv auf diese neuen Listen angewand, solange bis eine Liste nurnoch ein Element hat, denn dann ist die Liste trivialerweise sortiert. Wie man durch kurzes Überlegen sicherlich schnell bemerkt ist die Wahl des Pivot-Elementes kritisch für die Qualität dieses Algorithmus. Das einfachste wäre das Element in der Mitte der Liste zu nehmen, aber es gibt viele verschiedene Möglichkeiten.

Hier jetzt eine Beispielimplementation in C++ unter Verwendung von templates (damit der Algorithmus nicht nur auf einer Art von Daten läuft)(In meinem Code ist func eine übergebene Vergleichsfunktion, die 0 bei Gleichheit, -1 wenn der erste Wert kleiner, 1 wenn der erste Wert größer als der zweite ist):

template <class T> class QuickSort{
     public:
        void operator()(T* start, T* end, int (*func)(T, T)){
            if(start < end){
                T median = *(start + ((end - start) / 2 / sizeof(T)));
                T *r =end, *l = start;
                while(l <= r){
                    while(func(*l, median) == -1) l++;
                    while(func(*r, median) == 1)  r--;
                    if(func(*l, *r) == 1) swap(r, l);
                    l++;
                    r--;
                }
                (*this)(start, r, func);
                (*this)(l, end, func);
            }
        }
 
        void swap(T* a, T* b){
            T tmp = *a;
            *a = *b;
            *b = tmp;
        }
    };

Heapsort

Die Idee hinter Heapsort ist äußerst elegant, wenn auch etwas schwierig zu verstehen, denn vorher muss man erst noch einen ADT (Abstrakten DatenTyp) definieren. In diesem Fall nehmen wir den ADT Max-Heap. Ein Max-Heap ist ein binärer Baum (was ein Baum ist spare ich mir für ein späteres Tutorial), für den gilt, dass die Kinder eines Knotens K kleiner sind als K, die Kinder stehen untereinander in keinerlei Beziehung. Der Trick ist nun eine Liste, die nunmal linear ist intern als einen Max-Heap zu betrachten, bzw in einen zu verwandeln. Durch überlegen erhält man folgende Regeln:

Das erste Element der Liste ist die Wurzel
Das linke Kind hat den Index 2k, wobei k der index des Elternknotens ist
Das rechte Kind hat den Index 2k+1
Der Elternknoten eines knoten k hat den indes k/2 (abgerundet)

Das bedeutet, wir machen aus unserer Liste einen Max-Heap (d.h. das größte Element der Liste steht am Anfang) und tauschen dann das erste Element mit dem letzten unseres Max-Heaps und bauen wieder einen Max-Heap, diesmal aber um ein Element verringert. Das wird solange wiederholt, bis die Liste sortiert ist. Beispielimplementation ist in Ruby:

class Heapsort
	def left(k)
		return 2*k
	end
 
	def right(k)
		return 2*k+1
	end
 
	def maxHeapify(arr, k)
		max = k
		max = left(k) if(left(k) <= @heapsize && arr[left(k)] > arr[max])
		max = right(k) if(right(k) <= @heapsize && arr[right(k)] > arr[max])
		if k != max
			arr[k], arr[max] = arr[max], arr[k]
			maxHeapify(arr, max)
		end
	end
 
	def buildMaxHeap(arr)
		@heapsize = arr.length - 1
		(arr.length / 2).downto 0 do |i|
			maxHeapify(arr, i)
		end
	end
 
	def heapsort(arr)
		buildMaxHeap(arr)
		(arr.length - 1).downto(1) do |i|
			arr[0], arr[i] = arr[i], arr[0]
			@heapsize -= 1
			maxHeapify(arr, 0)
		end
	end
end

Mergesort

Mergesort ist nun unser erster Algorithmus, der nicht in-place sortiert, er braucht also zusätzlichen Speicher zum sortieren. Wir teilen die Liste, die wir sortieren wollen, in zwei Teile auf und zwar solange bis nurnoch Listen mit zwei Element vorhanden sind, dann werden die Listenteile sortiert zusammengefügt. Beispielimplementation ebenfalls in Ruby:

def mergesort(arr, l, r)
	if l < r
		m = (r + l)/2
		mergesort(arr, l, m)
		mergesort(arr, m+1, r)
		merge(arr, l, m, r)
	end
end
 
def merge(arr, l, m, r)
	left, right = Array.new, Array.new
	0.upto(m-l){ |i| left[i] = arr[l+i] }
	0.upto(r - (m + 1)) { |i| right[i] = arr[m+i+1] }
	j = i = 0
	l.upto(r) do |k|
		if right[j] == nil || (left[i] != nil && left[i] < right[j])
			arr[k] = left[i]
			i += 1
		else
			arr[k] = right[j]
			j += 1
		end
	end
end

Countingsort

Countingsort ist ein Verfahren eine Liste in linearer Zeit zu sortieren, indem man einige Annahmen über die zu sortierenden Daten macht. Die zu sortierenden Zahlen müssen alle natürliche Zahlen zwischen 0, .., k mit k Element der Natürlichen Zahlen . Wir bestimmen für jede Zahl die Anzahl der Vorkommen, danach generieren wir aus der Liste mit der Anzahl der einzelnen Zahlen eine neue sortierte Liste. Z.B. würde in dem folgenden Code bei count[50] die Anzahl der Vorkommen der Nummer 50 gespeichert sein und so oft fügen wir die Nummer 50 in unsere Liste ein (natürlich erst, wenn sie dran ist, also nicht vor der 49 *g*). Beispielcode in Ruby:

def countingsort(arr, max)
	count = Array.new(max, 0)
	0.upto(arr.length - 1) { |i| count[arr[i]] += 1 }
	arr.clear
	0.upto(count.length - 1) do |i|
		count[i].times{ |j| arr.push(i) }
	end
end

Dies waren bei weitem nicht alle, aber die Grundlegensten. Nun noch zum Abschluss die Komplexität und Besonderheiten der Algorithmen in einer kurzen Übersicht (in-place bedeutet, dass der Algorithmus keinen extra Speicher zum sortieren benötigt, Je höher die Laufzeit, desto schneller wächst die Ausführungsdauer für mehr Elemente):

Selectionsort: Quadratische Laufzeit (n²), in-place
Insertionsort: Quadratische Laufzeit (n²), in-place
Quicksort: Laufzeit (n log n) bis (n²), in-place
Heapsort: Laufzeit (n log n), in-place
Mergesort: Laufzeit (n log n), nicht in-place
Countingsort: Lineare Laufzeit (n), nicht in-place

Literaturempfehlungen

Cormen et al., Algorithmen - Eine Einführung, ISBN 3-486-27515-1, 1188 Seiten, EUR 69,80
Bernd Owsnicki-Klewe, Algorithmen und Datenstrukturen, ISBN3-89639-172-0, 224 Seiten, EUR 15,80

Besondere Anmerkung des Authors: Jeglicher Code hier ist unter der GNU General Public License Version 2 oder später, freigegeben.

[Author Firewing | Diskussionsthread im Forum]

Themen: Allgemeine Artikel |