001    package de.hska.info1.sortieren;
002    
003    /**
004     * Implementierung von Quicksort.
005     * 
006     * @author Christian Pape
007     *
008     */
009    public class Quicksort implements Sortieren {
010    
011            public void sortieren(int a[]) {
012                    quickSortieren(a, 0, a.length - 1);
013            }
014            
015            private void quickSortieren(int [] a, int links, int rechts) {
016                    if (links < rechts) {
017                            int pivot = a[(links + rechts) / 2];
018                            int l = links;
019                            int r = rechts;
020                            while ( l < r) {
021                                    while ( a[l] < pivot) {
022                                            l++;
023                                    }
024                                    while ( a[r] > pivot) {
025                                            r--;
026                                    }
027                                    if (l <= r) {
028                                            int t = a[l];
029                                            a[l] = a[r];
030                                            a[r] = t;
031                                            r--;
032                                            l++;
033                                    }
034                            }
035                            quickSortieren(a, links, r);
036                            quickSortieren(a, l, rechts);
037                    }
038            }
039            
040            /**
041             * Misst die Zeit in ns für zufällig gefüllte Felder.
042             */
043            public static void main(String [] argv) {
044                    Sortieren quicksort = new Quicksort();
045                    Zeitmessen.zeitmessen(quicksort);
046            }
047    }