www.jammni.de

Sortieralgorithmen in Haskell

So jetzt schreib ich mal ’ne kleine Zusammenfassung aller Sortieralgorithmen in Haskell die ich so kenne... Kann man ja immer gebrauchen ;-)

Insertion Sort

Die Funktion insert fügt ein Element in eine bereits sortierte Liste an der richtigen Stelle ein. insertsort sortiert eine Liste durch den sukzessiven Aufbau einer sortierten Liste.

Listing 1 - InsertionSort.hs:

1:	insert:: Ord a => a -> [a] -> [a]
2:	insert x [] = [x]
3:	insert x (y:ys)
4:	\|x<=y =x:y:ys
5:	\|otherwise = y:insert x ys
6:
7:	insertsort:: Ord a => [a] -> [a]
8:	insertsort [] = []
9:	insertsort (x:xs) = insert x (insertsort xs)
10:
11:	-- alternativ:
12:
13:	iSort :: [Int] -> [Int]
14:	iSort xs = foldr (insert) [] xs

Quick Sort

Die Funktion quicksort wählt ein Element aus einer unsortierten Liste aus (Pivotelement z.B. das erste) und zerlegt die Liste in zwei Teillisten. Die eine Liste enthält dabei alle kleineren Elemente, die andere Liste alle größeren Elemente. Diese werden rekursiv nach demselben Muster sortiert. Zum Schluss fügt quicksort diese drei Teile in der richtigen Reihenfolge wieder zusammen.

Die noch unsortierten Teillisten werden über denselben Algorithmus mittels Rekursion in noch kleinere Teillisten zerlegt und, sobald nur noch Listen mit je einem Element vorhanden sind, wieder zusammengesetzt.

Listing 2 - QuickSort.hs:

1:	qsort:: Ord a => [a] -> [a]
2:	qsort [] = []
3:	qsort (x:xs) = (qsort kleiner) ++ [x] ++ (qsort groesser)
4:	where kleiner = [y\|y <- xs, y<x]
5:	groesser = [y\|y <- xs, y>x]

Merge Sort

Die Hillfs-Funktion merge fügt zwei sortierte Listen zu einer sortierten Liste zusammen.

Und mergesort halbiert eine Liste, sortiert diese rekursiv nach demselben Verfahren und fügt die dann sortierten beiden Teillisten zu einer sortierten Liste mit merge (engl. To merge) zusammen.

Listing 3 - MergeSort.hs:

1:	merge [] ys = ys
2:	merge (x:xs) [] = x:xs
3:	merge (x:xs) (y:ys)
4:	\| x<=y = x:merge xs (y:ys)
5:	\| x>y = y:merge (x:xs) ys
6:
7:	mergesort:: Ord a => [a] -> [a]
8:	mergesort xs
9:	\| n < 2 = xs
10:	\| otherwise = merge (mergesort links) (mergesort rechts)
11:	where links = take h xs
12:	rechts = drop h xs
13:	n = length xs
14:	h = div n 2

Bubble Sort

Die Hilfs-Funktion bubble durchläuft eine Liste und vertauscht dabei ggf. zwei benachbarte Elemente (so dass das größere rechts steht). Nach dem einmaligen Aufruf von bubble befindet sich das größte Element der Liste am Ende der Liste. Die Funktion bubblesort ruft die Funktion bubble so oft auf, bis die Gesamtliste sortiert ist.

Listing 4 - BubbleSort.hs:

1:	bubble:: Ord a => [a] -> [a]
2:	bubble [] = []
3:	bubble [x] = [x]
4:	bubble (x:y:xs)
5:	\| x>y = y : bubble (x:xs)
6:
7:	bsort:: Ord a => [a] -> [a]
8:	bsort [] = []
9:	bsort (x:xs) = bsort (init ys) ++ [last ys]
10:	where ys = bubble (x:xs)

Selection Sort

Selection-Sort ist Sortieren durch Auswählen. Es wird (rekursiv) das kleinste Element gesucht und vor die (noch zu sortierende) Liste gestellt, aus der genau dieses Element entfernt wird.

Sobald das vorderste Element gleich dem Gesuchten ist, gibt remel die Restliste zurück. Es wird also das erste Auftreten des Elements gefunden – genau wie minel das Kleinste findet.

Listing 5 - SelectionSort.hs:

1:	selsort [] = []
2:	selsort l = kl : selsort (remel kl l)
3:	where kl = minel l
4:
5:	remel el [] = []
6:	remel el (x:xs) \| el == x = xs
7:	\| otherwise = x : remel el xs
8:
9:	minel [x] = x
10:	minel (x:xs) = if x < me then x
11:	else me
12:	where me = minel xs