001package algs23;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac QuickDualPivot.java
005 *  Execution:    java QuickDualPivot < input.txt
006 *  Dependencies: StdOut.java StdIn.java
007 *  Data files:   http://algs4.cs.princeton.edu/23quicksort/tiny.txt
008 *                http://algs4.cs.princeton.edu/23quicksort/words3.txt
009 *
010 *  Sorts a sequence of strings from standard input using dual-pivot
011 *  quicksort.
012 *
013 *  [Warning: not thoroughly tested.]
014 *
015 *  % more tiny.txt
016 *  S O R T E X A M P L E
017 *
018 *  % java QuickDualPivot < tiny.txt
019 *  A E E L M O P R S T X                 [ one string per line ]
020 *
021 *  % more words3.txt
022 *  bed bug dad yes zoo ... all bad yet
023 *
024 *  % java QuickDualPivot < words3.txt
025 *  all bad bed bug dad ... yes yet zoo    [ one string per line ]
026 *
027 *************************************************************************/
028
029public class XQuickDualPivot {
030
031        // quicksort the array a[] using dual-pivot quicksort
032        public static <T extends Comparable<? super T>> void sort(T[] a) {
033                sort(a, 0, a.length - 1);
034                assert isSorted(a);
035        }
036
037        // quicksort the subarray a[lo .. hi] using dual-pivot quicksort
038        private static <T extends Comparable<? super T>> void sort(T[] a, int lo, int hi) {
039                if (hi <= lo) return;
040
041                // make sure a[lo] <= a[hi]
042                if (less(a[hi], a[lo])) exch(a, lo, hi);
043
044                int lt = lo + 1, gt = hi - 1;
045                int i = lo + 1;
046                while (i <= gt) {
047                        if       (less(a[i], a[lo])) exch(a, lt++, i++);
048                        else if  (less(a[hi], a[i])) exch(a, i, gt--);
049                        else                         i++;
050                }
051                exch(a, lo, --lt);
052                exch(a, hi, ++gt);
053
054                // recursively sort three subarrays
055                sort(a, lo, lt-1);
056                if (less(a[lt], a[gt])) sort (a, lt+1, gt-1);
057                sort(a, gt+1, hi);
058
059                assert isSorted(a, lo, hi);
060        }
061
062
063
064        /* *********************************************************************
065         *  Helper sorting functions
066         ***********************************************************************/
067
068        // is v < w ?
069        private static <T extends Comparable<? super T>> boolean less(T v, T w) {
070                return (v.compareTo(w) < 0);
071        }
072
073        // exchange a[i] and a[j]
074        private static void exch(Object[] a, int i, int j) {
075                Object swap = a[i];
076                a[i] = a[j];
077                a[j] = swap;
078        }
079
080        /* *********************************************************************
081         *  Check if array is sorted - useful for debugging
082         ***********************************************************************/
083        private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
084                return isSorted(a, 0, a.length - 1);
085        }
086
087        private static <T extends Comparable<? super T>> boolean isSorted(T[] a, int lo, int hi) {
088                for (int i = lo + 1; i <= hi; i++)
089                        if (less(a[i], a[i-1])) return false;
090                return true;
091        }
092
093
094
095        // print array to standard output
096        private static <T> void show(T[] a) {
097                for (T element : a) {
098                        StdOut.println(element);
099                }
100        }
101
102        // Read strings from standard input, sort them, and print.
103        public static void main(String[] args) {
104                String[] a = StdIn.readAllStrings();
105                sort(a);
106                show(a);
107        }
108
109}