Quick Sort / Implementation
  
 StartSeite | QuickSort/ | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern
Hier finden sich Implementationen von QuickSort.

C

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


Haskell

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

Java

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


Lisp

;;; 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

Modula-3

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;

Python

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

Perl

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:

KategorieAlgorithmus KategorieC KategorieCee KategorieLisp
StartSeite | QuickSort/ | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern
Text dieser Seite ändern (zuletzt geändert: 29. November 2007 8:45 (diff))
Suchbegriff: gesucht wird
im Titel
im Text