001package algs23; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac Quick3way.java 005 * Execution: java Quick3way < 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 3-way quicksort. 011 * 012 * % more tiny.txt 013 * S O R T E X A M P L E 014 * 015 * % java Quick3way < tiny.txt 016 * A E E L M O P R S T X [ one string per line ] 017 * 018 * % more words3.txt 019 * bed bug dad yes zoo ... all bad yet 020 * 021 * % java Quick3way < words3.txt 022 * all bad bed bug dad ... yes yet zoo [ one string per line ] 023 * 024 *************************************************************************/ 025 026public class Quick3way { 027 028 // quicksort the array a[] using 3-way partitioning 029 public static <T extends Comparable<? super T>> void sort(T[] a) { 030 sort(a, 0, a.length - 1); 031 assert isSorted(a); 032 } 033 034 // quicksort the subarray a[lo .. hi] using 3-way partitioning 035 private static <T extends Comparable<? super T>> void sort(T[] a, int lo, int hi) { 036 if (hi <= lo) return; 037 int lt = lo, gt = hi; 038 T v = a[lo]; 039 int i = lo; 040 while (i <= gt) { 041 int cmp = a[i].compareTo(v); 042 if (cmp < 0) exch(a, lt++, i++); 043 else if (cmp > 0) exch(a, i, gt--); 044 else i++; 045 } 046 047 // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 048 sort(a, lo, lt-1); 049 sort(a, gt+1, hi); 050 assert isSorted(a, lo, hi); 051 } 052 053 054 055 /* ********************************************************************* 056 * Helper sorting functions 057 ***********************************************************************/ 058 059 // is v < w ? 060 private static <T extends Comparable<? super T>> boolean less(T v, T w) { 061 if (COUNT_OPS) DoublingTest.incOps (); 062 return (v.compareTo(w) < 0); 063 } 064 065 // does v == w ? 066 private static <T extends Comparable<? super T>> boolean eq(T v, T w) { 067 if (COUNT_OPS) DoublingTest.incOps (); 068 return (v.compareTo(w) == 0); 069 } 070 071 // exchange a[i] and a[j] 072 private static <T> void exch(T[] a, int i, int j) { 073 if (COUNT_OPS) DoublingTest.incOps (); 074 T swap = a[i]; 075 a[i] = a[j]; 076 a[j] = swap; 077 } 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 // print array to standard output 094 private static <T> void show(T[] a) { 095 for (T element : a) { 096 StdOut.println(element); 097 } 098 } 099 100 // test code 101 private static boolean COUNT_OPS = false; 102 public static void main(String[] args) { 103 //String[] cards = In.readStrings ("data/cards.txt"); 104 //StdRandom.shuffle (cards); 105 106 //StdIn.fromFile ("data/tiny.txt"); 107 //StdIn.fromFile ("data/cards.txt"); 108 StdIn.fromFile ("data/words3.txt"); 109 110 String[] a = StdIn.readAllStrings(); 111 sort(a); 112 show(a); 113 114 COUNT_OPS = true; 115 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandomUnique (N), (Integer[] x) -> sort (x)); 116 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandom (N, 2), (Integer[] x) -> sort (x)); 117 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x)); 118 119 } 120}