Gemäß dem XP-Motto EinfachesDesign habe ich hier eine ganz einfach gehaltene Implementation anzubieten.

void quicksort(int *array, int links, int rechts) { int pivot, temp; int l, r; if (links < rechts) { l = links; r = rechts; pivot = array[(links+rechts) >> 1]; do { while (array[l] < pivot) l++; while (array[r] > pivot) r--; if (l <= r) { temp = array[r]; array[r] = array[l]; array[l] = temp; l++; r--; } } while (l <= r); quicksort(array, links, r); quicksort(array, l, rechts); } }

qsort gemäß C-Lib (HelmutSchellong):

void qsort(void *,unsigned,unsigned, int(*)(const void*,const void*) ); void qsort(base, nel,width, cmp) void *base; unsigned nel, width; int (*cmp)(const void*, const void*); { register unsigned char *l, *r, *ve; unsigned char *lg, *rg; if (nel>1 && width<=64&&width>0 && base && cmp) { ve=l=r=base; r+=--nel*width; lg=l; rg=r; ve+=(nel/2)*width; do { while (l!=ve && (*cmp)(l,ve) < 0) l+=width; while (r!=ve && (*cmp)(r,ve) > 0) r-=width; if (l < r) { if ((*cmp)(l,r)) { static unsigned char t[64]; memcpy(t, l, width); memcpy(l, r, width); memcpy(r, t, width); if (ve==l) ve=r; else if (ve==r) ve=l; } l+=width; r-=width; } } while (l < r); if (l==r) if (l!=ve && (*cmp)(l,ve) > 0) r-=width; else l+=width; if (r>lg) qsort(lg,(r-lg)/width+1, width, cmp); if (rg>l) qsort( l,(rg-l)/width+1, width, cmp); } return; }

qsort-Variante von HelmutSchellong:

void qsort_(uint,uint, int(*)(uint,uint), void(*)(uint,uint) ); void qsort_(l, r, cmp, swap) register uint l, r; int (* cmp)(uint, uint); void (*swap)(uint, uint); { register uint ve; uint lg, rg; if (l < r) { lg=l; rg=r; ve=(l+r)>>1; do { while (l!=ve && (*cmp)(l,ve) < 0) ++l; while (r!=ve && (*cmp)(r,ve) > 0) --r; if (l < r) { if ((*cmp)(l,r)) { (*swap)(l,r); if (ve==l) ve=r; else if (ve==r) ve=l; } ++l; --r; } } while (l < r); if (l==r) if (l!=ve && (*cmp)(l,ve) > 0) --r; else ++l; qsort_(lg,r, cmp,swap); qsort_(l,rg, cmp,swap); } return; }

Siehe auch: c't 8/1984 S.70

QuickSort wird sehr gerne als Demonstration für die Schlichtheit von Programmen in der SpracheHaskell verwendet. Die Standardvariante finde ich aber immer noch recht umständlich. http://www.haskell.org/aboutHaskell.html

Wie wär's mit folgender:

qsort :: (Ord a) => [a] -> [a] qsort [] = [] qsort (x:xs) = let (xlt, xge) = partition (<x) xs in qsort xlt ++ [x] ++ qsort xge

Diese Implementation in Java wurde lediglich gemacht, um den PseudoCode auf der Seite QuickSort auszuprobieren. Für praktische Zwecke ist die Implementation deshalb nicht zu gebrauchen.

import java.util.Arrays; import java.util.Random; class QuickSort { static Random random = new Random(); public static void swap(int[] array, int x, int y) { int tmp = array[x]; array[x] = array[y]; array[y] = tmp; } public static int partition(int[] array, int l, int r) { // l < r, t := array[l] int l0 = l; int r0 = r; int pivot = array[l0]; while (l < r) { if (array[r] > pivot) { --r; } else if (array[l] <= pivot) ++l; else { // Must swap array swap(array, l, r); } } swap(array, l0, r); return r; } public static void quicksort(int[] array, int l, int r) { if (l < r) { int m = partition(array, l, r); quicksort(array, l, m-1); quicksort(array, m+1, r); } } public static void fillArray(int[] array) { int r = random.nextInt(3*array.length); for (int i = 0 ; i < array.length; i++) { array[i] = random.nextInt(r+1); } } /** * Ein primitiver UnitTest */ public static void main(String args[]) { int [] array = new int[100]; for (int i=0; i<1000; ++i) { fillArray(array); int[] array2 = (int[])array.clone(); quicksort(array, 0, array.length-1); Arrays.sort(array2); if (!Arrays.equals(array,array2)) { System.out.print("Problem:["); printArray(array); System.out.println("]"); System.out.print("Anstatt:["); printArray(array2); System.out.println("]"); } } } public static void printArray(int array[]) { for (int j = 0; j < array.length; ++j) { System.out.print(array[j] + " "); } } public static void printArray(int array[], int l, int r) { for (int j = l; j <= r; ++j) { System.out.print(array[j] + " "); } } }

Laufzeit

O(n*log(n))

Speicherbedarf

Daten: Sortiert vor Ort; Runtime: im Allgemeinen O(log_2(n)) Stacktiefe. Allerdings kann das im Worst-Case (Pivotelement ve wird immer maximal oder minimal im Bereich [lg,rg] gewählt) zu O(n) ausarten.

Anmerkung

Nicht stabil

;;; Hoch-rekursives stable quicksort von Henry Baker. (In Lisp) ;;; Langsam und stackintensiv, für scheme allerdings okay. ;;; ftp://ftp.netcom.com/pub/hb/hbaker/Share-Unify.html ;;; (setq l '((1 1) (2 1) (1 2) (3 1) (1 3) (3 2) (3 3) (4 1) (1 4))) ;;; (std-%stable-qsort l '(lambda (x y)(< (car x) (car y)))) ;;; => ((1 1) (1 2) (1 3) (1 4) (2 1) (3 1) (3 2) (3 3) (4 1)) (defun std-%stable-qsort (x cmp) (if (null x) nil (append (std-%stable-qsort (std-%low (cdr x) (car x) cmp) cmp) (cons (car x) (std-%stable-qsort (std-%high (cdr x) (car x) cmp) cmp))))) (defun std-%high (x i cmp) (cond ((null x) nil) ((apply cmp (list (car x) i)) (std-%high (cdr x) i cmp)) (t (cons (car x) (std-%high (cdr x) i cmp))))) (defun std-%low (x i cmp) (cond ((null x) nil) ((not (apply cmp (list (car x) i))) (std-%low (cdr x) i cmp)) (t (cons (car x) (std-%low (cdr x) i cmp)))))

Für andere Lisp qsort/merge-sort versionen und timings siehe http://xarch.tu-graz.ac.at/autocad/stdlib/test/SORTTST.LSP

Hier eine nahezu 1:1-Umsetzung des C-Algorithmus, vgl. auch "Programmieren mit Modula-3. Eine Einführung in stilvolle Programmierung.", Böszörményi/Weich, Seite 298. Herauszuheben ist, dass man in der SpracheModula3 einen Abschnitt eines Feldes wieder als Feld verwenden kann. So kann man sicher sein, dass der Unteraufruf von QuickSort nur auf dem ihm zugewiesenen Feldabschnitt arbeitet. Die QuickSort-Variante in der Standardbibliothek libm3 (m3-libs/libm3/src/sort/ArraySort?.mg) ist etwas aufwändiger.

PROCEDURE QuickSort (VAR x: ARRAY OF T; ) = VAR i := FIRST(x); j := LAST(x); m: T; BEGIN IF NUMBER(x) <= 1 THEN RETURN END; m := x[(i + j) DIV 2]; REPEAT WHILE x[i] < m DO INC(i); END; WHILE x[j] > m DO DEC(j); END; IF i <= j THEN VAR swap := x[i]; BEGIN x[i] := x[j]; x[j] := swap; END; INC(i); DEC(j); END; UNTIL i > j; QuickSort(SUBARRAY(x, FIRST(x), j - FIRST(x) + 1)); QuickSort(SUBARRAY(x, i, LAST(x) - i + 1)); END QuickSort;

def quicksort(a): if not a: return [] return quicksort([x for x in a if x < a[0]]) + [a[0]] + quicksort([ [x for x in a[1:] if x >= a[0]] ]) #im 2. quicksort-Aufruf ist ein Klammerpaar zu viel, aber Wiki zeigt es sonts nicht an

sub quicksort { my ( $aref , $links , $rechts , $compare ) = @_; my ($l,$r,$pivot) = ( $links,$rechts, $aref->[ int +($links+$rechts) / 2 ] ); while( $l <= $r ){ $l++ while $compare->( $aref->[$l], $pivot ) == -1; $r-- while $compare->( $pivot , $aref->[$r] ) == -1; if ( $l <= $r ) { @{$aref}[$l,$r] = @{$aref}[$r,$l]; $l++;$r--; } } quicksort( $aref, $links, $r, $compare) if $links < $r; quicksort( $aref, $l, $rechts, $compare) if $l < $rechts; } # Aufrufbeispiel: my @ar = qw/3 1 5 9 6 0 7 11 8/; quicksort( \@ar , 0 , @ar-1 , sub { $_[0] <=> $_[1] } ); print "@ar\n";

Siehe auch:

• /Diskussion
• /TestScript