/******************************************************************************
* Compilation: javac AmericanFlag.java
* Execution: java AmericanFlag < input.txt
* java AmericanFlag int < input-non-negative-ints.txt
* Dependencies: StdIn.java StdOut.java Stack.java
* Data files: https://algs4.cs.princeton.edu/51radix/words3.txt
* https://algs4.cs.princeton.edu/51radix/shells.txt
*
* Sort an array of strings or integers in-place using American flag sort.
*
* % java AmericanFlag < shells.txt
* are
* by
* sea
* seashells
* seashells
* sells
* sells
* she
* she
* shells
* shore
* surely
* the
* the
*
******************************************************************************/
/**
* The {@code AmericanFlag} class provides static methods for sorting an
* array of extended ASCII strings or integers in-place using
* American flag sort. This is a non-recursive implementation.
*
* For additional documentation,
* see Section 5.1 of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
* and
* Engineering Radix Sort by McIlroy and Bostic.
* For a version that uses only one auxiliary array, see {@link AmericanFlagX}.
*
* @author Robert Sedgewick
* @author Kevin Wayne
* @author Ivan Pesin
*/
public class AmericanFlag {
private static final int BITS_PER_BYTE = 8;
private static final int BITS_PER_INT = 32; // each Java int is 32 bits
private static final int R = 256; // extend ASCII alphabet size
private static final int CUTOFF = 15; // cutoff to insertion sort
// do not instantiate
private AmericanFlag() { }
// return dth character of s, -1 if d = length of string
private static int charAt(String s, int d) {
assert d >= 0 && d <= s.length();
if (d == s.length()) return -1;
return s.charAt(d);
}
/**
* Rearranges the array of extended ASCII strings in ascending order.
* This is an unstable sorting algorithm.
*
* @param a the array to be sorted
*/
public static void sort(String[] a) {
sort(a, 0, a.length - 1);
}
// sort from a[lo] to a[hi], starting at the dth character
public static void sort(String[] a, int lo, int hi) {
// one-time allocation of data structures
Stack st = new Stack();
int[] first = new int[R+2];
int[] next = new int[R+2];
int d = 0; // character index to sort by
st.push(lo);
st.push(hi);
st.push(d);
while (!st.isEmpty()) {
d = st.pop();
hi = st.pop();
lo = st.pop();
if (hi <= lo + CUTOFF) {
insertion(a, lo, hi, d);
continue;
}
// compute frequency counts
for (int i = lo; i <= hi; i++) {
int c = charAt(a[i], d) + 1; // account for -1 representing end-of-string
first[c+1]++;
}
// first[c] = location of first string whose dth character = c
first[0] = lo;
for (int c = 0; c <= R; c++) {
first[c+1] += first[c];
if (c > 0 && first[c+1]-1 > first[c]) {
// add subproblem for character c (excludes sentinel c == 0)
st.push(first[c]);
st.push(first[c+1] - 1);
st.push(d+1);
}
}
// next[c] = location to place next string whose dth character = c
for (int c = 0; c < R+2; c++)
next[c] = first[c];
// permute data in place
for (int k = lo; k <= hi; k++) {
int c = charAt(a[k], d) + 1;
while (first[c] > k) {
exch(a, k, next[c]++);
c = charAt(a[k], d) + 1;
}
next[c]++;
}
// clear first[] and next[] arrays
for (int c = 0; c < R+2; c++) {
first[c] = 0;
next[c] = 0;
}
}
}
// insertion sort a[lo..hi], starting at 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
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();
}
/**
* Rearranges the array of 32-bit integers in ascending order.
* Currently, assumes that the integers are nonnegative.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
sort(a, 0, a.length-1);
}
// MSD sort from a[lo] to a[hi]
private static void sort(int[] a, int lo, int hi) {
// one-time allocation of data structures
Stack st = new Stack();
int[] first = new int[R+1];
int[] next = new int[R+1];
int mask = R - 1; // 0xFF;
int d = 0; // byte to sort by
st.push(lo);
st.push(hi);
st.push(d);
while (!st.isEmpty()) {
d = st.pop();
hi = st.pop();
lo = st.pop();
if (hi <= lo + CUTOFF) {
insertion(a, lo, hi, d);
continue;
}
// compute frequency counts (need R = 256)
int shift = BITS_PER_INT - BITS_PER_BYTE*d - BITS_PER_BYTE;
for (int i = lo; i <= hi; i++) {
int c = (a[i] >> shift) & mask;
first[c+1]++;
}
// first[c] = location of first int whose dth byte = c
first[0] = lo;
for (int c = 0; c < R; c++) {
first[c+1] += first[c];
if (d < 3 && first[c+1]-1 > first[c]) {
// add subproblem for byte c
st.push(first[c]);
st.push(first[c+1] - 1);
st.push(d+1);
}
}
// next[c] = location to place next string whose dth byte = c
for (int c = 0; c < R+1; c++)
next[c] = first[c];
// permute data in place
for (int k = lo; k <= hi; k++) {
int c = (a[k] >> shift) & mask;
while (first[c] > k) {
exch(a, k, next[c]++);
c = (a[k] >> shift) & mask;
}
next[c]++;
}
// clear first[] and next[] arrays
for (int c = 0; c < R+1; c++) {
first[c] = 0;
next[c] = 0;
}
}
}
// insertion sort a[lo..hi], starting at dth byte
private static void insertion(int[] 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(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// is v less than w, starting at byte d
private static boolean less(int v, int w, int d) {
int mask = R - 1; // 0xFF;
for (int i = d; i < 4; i++) {
int shift = BITS_PER_INT - BITS_PER_BYTE*i - BITS_PER_BYTE;
int a = (v >> shift) & mask;
int b = (w >> shift) & mask;
if (a < b) return true;
if (a > b) return false;
}
return false;
}
/**
* Reads in a sequence of extended ASCII strings or non-negative ints from standard input;
* American flag sorts them;
* and prints them to standard output in ascending order.
*
* @param args the command-line arguments: "int" to read input as non-negative integers
*/
public static void main(String[] args) {
if (args.length > 0 && args[0].equals("int")) {
int[] a = StdIn.readAllInts();
sort(a);
// print results
for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
}
else {
String[] a = StdIn.readAllStrings();
sort(a);
// print results
for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
}
}
}