You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
128 lines
3.5 KiB
Java
128 lines
3.5 KiB
Java
|
|
|
|
import edu.princeton.cs.introcs.StdIn;
|
|
import edu.princeton.cs.introcs.StdOut;
|
|
import edu.princeton.cs.introcs.StdRandom;
|
|
|
|
/***********************************************************************************
|
|
* Compilation: javac Quick3string.java
|
|
* Execution: java Quick3string < input.txt
|
|
*
|
|
* Reads string from standard input and 3-way string quicksort them.
|
|
*
|
|
* % java Quick3string < shell.txt
|
|
* are
|
|
* by
|
|
* sea
|
|
* seashells
|
|
* seashells
|
|
* sells
|
|
* sells
|
|
* she
|
|
* she
|
|
* shells
|
|
* shore
|
|
* surely
|
|
* the
|
|
* the
|
|
*
|
|
*
|
|
***********************************************************************************/
|
|
|
|
public class Quick3string {
|
|
private static final int CUTOFF = 15; // cutoff to insertion sort
|
|
|
|
// sort the array a[] of strings
|
|
public static void sort(String[] a) {
|
|
StdRandom.shuffle(a);
|
|
sort(a, 0, a.length-1, 0);
|
|
assert isSorted(a);
|
|
}
|
|
|
|
// return the dth character of s, -1 if d = length of s
|
|
private static int charAt(String s, int d) {
|
|
assert d >= 0 && d <= s.length();
|
|
if (d == s.length()) return -1;
|
|
return s.charAt(d);
|
|
}
|
|
|
|
|
|
// 3-way string quicksort a[lo..hi] starting at dth character
|
|
private static void sort(String[] a, int lo, int hi, int d) {
|
|
|
|
// cutoff to insertion sort for small subarrays
|
|
if (hi <= lo + CUTOFF) {
|
|
insertion(a, lo, hi, d);
|
|
return;
|
|
}
|
|
|
|
int lt = lo, gt = hi;
|
|
int v = charAt(a[lo], d);
|
|
int i = lo + 1;
|
|
while (i <= gt) {
|
|
int t = charAt(a[i], d);
|
|
if (t < v) exch(a, lt++, i++);
|
|
else if (t > v) exch(a, i, gt--);
|
|
else i++;
|
|
}
|
|
|
|
// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
|
|
sort(a, lo, lt-1, d);
|
|
if (v >= 0) sort(a, lt, gt, d+1);
|
|
sort(a, gt+1, hi, d);
|
|
}
|
|
|
|
// sort from a[lo] to a[hi], starting at the dth character
|
|
private static void insertion(String[] a, int lo, int hi, int d) {
|
|
for (int i = lo; i <= hi; i++)
|
|
for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
|
|
exch(a, j, j-1);
|
|
}
|
|
|
|
// exchange a[i] and a[j]
|
|
private static void exch(String[] a, int i, int j) {
|
|
String temp = a[i];
|
|
a[i] = a[j];
|
|
a[j] = temp;
|
|
}
|
|
|
|
// is v less than w, starting at character d
|
|
// DEPRECATED BECAUSE OF SLOW SUBSTRING EXTRACTION IN JAVA 7
|
|
// private static boolean less(String v, String w, int d) {
|
|
// assert v.substring(0, d).equals(w.substring(0, d));
|
|
// return v.substring(d).compareTo(w.substring(d)) < 0;
|
|
// }
|
|
|
|
// is v less than w, starting at character d
|
|
private static boolean less(String v, String w, int d) {
|
|
assert v.substring(0, d).equals(w.substring(0, d));
|
|
for (int i = d; i < Math.min(v.length(), w.length()); i++) {
|
|
if (v.charAt(i) < w.charAt(i)) return true;
|
|
if (v.charAt(i) > w.charAt(i)) return false;
|
|
}
|
|
return v.length() < w.length();
|
|
}
|
|
|
|
// is the array sorted
|
|
private static boolean isSorted(String[] a) {
|
|
for (int i = 1; i < a.length; i++)
|
|
if (a[i].compareTo(a[i-1]) < 0) return false;
|
|
return true;
|
|
}
|
|
|
|
|
|
public static void main(String[] args) {
|
|
|
|
// read in the strings from standard input
|
|
String[] a = StdIn.readAllStrings();
|
|
int N = a.length;
|
|
|
|
// sort the strings
|
|
sort(a);
|
|
|
|
// print the results
|
|
for (int i = 0; i < N; i++)
|
|
StdOut.println(a[i]);
|
|
}
|
|
}
|