001package algs22; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac MergeBU.java 005 * Execution: java MergeBU < input.txt 006 * Dependencies: StdOut.java StdIn.java 007 * Data files: http://algs4.cs.princeton.edu/22merge/tiny.txt 008 * http://algs4.cs.princeton.edu/22merge/words3.txt 009 * 010 * Sorts a sequence of strings from standard input using 011 * bottom-up mergesort. 012 * 013 * % more tiny.txt 014 * S O R T E X A M P L E 015 * 016 * % java MergeBU < tiny.txt 017 * A E E L M O P R S T X [ one string per line ] 018 * 019 * % more words3.txt 020 * bed bug dad yes zoo ... all bad yet 021 * 022 * % java MergeBU < words3.txt 023 * all bad bed bug dad ... yes yet zoo [ one string per line ] 024 * 025 *************************************************************************/ 026 027public class MergeBU { 028 029 // stably merge a[lo..m] with a[m+1..hi] using aux[lo..hi] 030 private static <T extends Comparable<? super T>> void merge(T[] a, T[] aux, int lo, int m, int hi) { 031 032 // copy to aux[] 033 for (int k = lo; k <= hi; k++) { 034 aux[k] = a[k]; 035 } 036 037 // merge back to a[] 038 int i = lo, j = m+1; 039 for (int k = lo; k <= hi; k++) { 040 if (i > m) a[k] = aux[j++]; 041 else if (j > hi) a[k] = aux[i++]; 042 else if (less(aux[j], aux[i])) a[k] = aux[j++]; 043 else a[k] = aux[i++]; 044 } 045 if (COUNT_OPS) DoublingTest.addOps (hi-lo); 046 047 } 048 049 // bottom-up mergesort 050 @SuppressWarnings("unchecked") 051 public static <T extends Comparable<? super T>> void sort(T[] a) { 052 int N = a.length; 053 T[] aux = (T[]) new Comparable[N]; 054 for (int n = 1; n < N; n = n+n) { 055 for (int i = 0; i < N-n; i += n+n) { 056 int lo = i; 057 int m = i+n-1; 058 int hi = Math.min(i+n+n-1, N-1); 059 merge(a, aux, lo, m, hi); 060 } 061 } 062 assert isSorted(a); 063 } 064 065 /* ********************************************************************* 066 * Helper sorting functions 067 ***********************************************************************/ 068 069 // is v < w ? 070 private static <T extends Comparable<? super T>> boolean less(T v, T w) { 071 if (COUNT_OPS) DoublingTest.incOps (); 072 return (v.compareTo(w) < 0); 073 } 074 075 076 /* ********************************************************************* 077 * Check if array is sorted - useful for debugging 078 ***********************************************************************/ 079 private static <T extends Comparable<? super T>> boolean isSorted(T[] a) { 080 for (int i = 1; i < a.length; i++) 081 if (less(a[i], a[i-1])) return false; 082 return true; 083 } 084 085 // print array to standard output 086 private static <T> void show(T[] a) { 087 for (T element : a) { 088 StdOut.println(element); 089 } 090 } 091 092 // test code 093 private static boolean COUNT_OPS = false; 094 public static void main(String[] args) { 095 StdIn.fromFile ("data/words3.txt"); 096 097 String[] a = StdIn.readAllStrings(); 098 sort(a); 099 show(a); 100 101 COUNT_OPS = true; 102 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandomUnique (N), (Integer[] x) -> sort (x)); 103 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandom (N, 2), (Integer[] x) -> sort (x)); 104 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x)); 105 } 106} 107 108