001package algs51; 002 003import java.util.Arrays; 004import java.util.Random; 005import java.util.function.Consumer; 006import stdlib.*; 007 008/* 009 * Using random.nextLong (): 010 * RESULTS WITH Arrays.sort (Quicksort - Bentley/McIlroy 3-way) 011 * 012 * 2560000 [0.388 1.672] 013 * 5120000 [0.657 1.693] 014 * 10240000 [1.284 1.954] 015 * 016 * RESULTS WITH LSD 017 * 018 * 2560000 [0.149 1.355] 019 * 5120000 [0.276 1.852] 020 * 10240000 [0.520 1.884] 021 */ 022 023public class XLSDLong { 024 private static int byteAt(long i, int d) { 025 return (int) (i>>>(d*8)) & 0xff; 026 } 027 public static void sort(long[] a, boolean show) { 028 int W = 8; 029 int N = a.length; 030 int R = 256; // one byte 031 long[] b = new long[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 // copy back -- assumes that W is even! 041 { long[] tmp = b; b = a; a = tmp; } 042 if (show) show(a); 043 } 044 } 045 private static boolean isSorted(long[] a) { 046 for (int i = a.length-1; i > 0; i--) 047 if (a[i] < a[i-1]) return false; 048 return true; 049 } 050 private static void show(long[] a) { 051 int W = 8; 052 for (int i = 0; i < a.length; i++) { 053 for (int d = W-1; d >= 0; d--) 054 StdOut.format ("%02x ", byteAt(a[i], d)); 055 StdOut.println (); 056 } 057 StdOut.println (); 058 } 059 060 061 062 /* ********************************************************************************* 063 * Test code 064 ***********************************************************************************/ 065 private static void exch(int[] a, int i, int j) { 066 int swap = a[i]; 067 a[i] = a[j]; 068 a[j] = swap; 069 } 070 private static double time; 071 private static void countops (int N, Consumer<long[]> sort) { 072 Random random = new Random(); 073 long[] a = new long[N]; 074 for (int i = 0; i < a.length; i++) a[i] = random.nextLong () & 0x7fffffffffffffffL; // positive numbers 075 076 Stopwatch sw = new Stopwatch (); 077 sort.accept (a); 078 time = sw.elapsedTime (); 079 if (!isSorted(a)) throw new Error(); 080 } 081 public static void run(String name, Consumer<long[]> sort) { 082 StdOut.println (name); 083 int N = 1280000; 084 countops (N, sort); 085 double prevTime = time; 086 for (int i=0; i<3; i++) { 087 N *= 2; 088 countops (N, sort); 089 StdOut.format("%8d [%5.3f %5.3f]\n", N, time, time/prevTime); 090 prevTime = time; 091 } 092 } 093 094 public static void main(String[] args) { 095 run ("LSD", (a) -> sort (a, false)); 096 run ("Quicksort", (a) -> Arrays.sort (a)); 097 } 098}