001package algs51; 002 003import java.util.Arrays; 004import java.util.Random; 005import java.util.function.Consumer; 006import stdlib.*; 007 008/* 009 * Using random.nextInt (): 010 * RESULTS WITH Arrays.sort (Quicksort - Bentley/McIlroy 3-way) 011 * 012 * 2560000 [0.383 1.544] 013 * 5120000 [0.672 1.755] 014 * 10240000 [1.238 1.842] 015 * 016 * RESULTS WITH LSD 017 * 018 * 2560000 [0.064 0.889] 019 * 5120000 [0.127 1.984] 020 * 10240000 [0.195 1.535] 021 */ 022 023public class XLSDInt { 024 private static int byteAt(int i, int d) { 025 return (i>>>(d*8)) & 0xff; 026 } 027 public static void sort(int[] a, boolean show) { 028 int W = 4; 029 int N = a.length; 030 int R = 256; // one byte 031 int[] b = new int[N]; 032 for (int d = 0; d <= W-1; d++) { 033 int[] count = new int[R+1]; 034 for (int i = 0; i < N; i++) 035 count[byteAt(a[i], d) + 1]++; 036 for (int r = 0; r < R; r++) 037 count[r+1] += count[r]; 038 for (int i = 0; i < N; i++) 039 b[count[byteAt(a[i], d)]++] = a[i]; 040 041 // copy back -- assumes that W is even! 042 { int[] tmp = b; b = a; a = tmp; } 043 if (show) show(a); 044 } 045 } 046 private static boolean isSorted(int[] a) { 047 for (int i = a.length-1; i > 0; i--) 048 if (a[i] < a[i-1]) return false; 049 return true; 050 } 051 private static void show(int[] a) { 052 int W = 4; 053 for (int i = 0; i < a.length; i++) { 054 for (int d = W-1; d >= 0; d--) 055 StdOut.format ("%02x ", byteAt(a[i], d)); 056 StdOut.println (); 057 } 058 StdOut.println (); 059 } 060 061 062 063 /* ********************************************************************************* 064 * Test code 065 ***********************************************************************************/ 066 private static void exch(int[] a, int i, int j) { 067 int swap = a[i]; 068 a[i] = a[j]; 069 a[j] = swap; 070 } 071 private static double time; 072 private static void countops (int N, Consumer<int[]> sort) { 073 Random random = new Random(); 074 int[] a = new int[N]; 075 for (int i = 0; i < a.length; i++) a[i] = random.nextInt () & 0x7fffffff; // positive numbers 076 077 Stopwatch sw = new Stopwatch (); 078 sort.accept (a); 079 time = sw.elapsedTime (); 080 if (!isSorted(a)) throw new Error(); 081 } 082 public static void run(String name, Consumer<int[]> sort) { 083 StdOut.println (name); 084 int N = 1280000; 085 countops (N, sort); 086 double prevTime = time; 087 for (int i=0; i<3; i++) { 088 N *= 2; 089 countops (N, sort); 090 StdOut.format("%8d [%5.3f %5.3f]\n", N, time, time/prevTime); 091 prevTime = time; 092 } 093 } 094 095 public static void main(String[] args) { 096 run ("LSD", (a) -> sort (a, false)); 097 run ("Quicksort", (a) -> Arrays.sort (a)); 098 } 099 public static void main1(String[] args) { 100 Random random = new Random(); 101 int[] a = new int[10]; 102 for (int i = 0; i < a.length; i++) a[i] = random.nextInt () & 0x7fffffff; // positive numbers 103 show (a); 104 sort (a, true); 105 } 106}