Java/Radix_Sort.java at main · gulafsh/Java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Radix sort using Java

importjava.io.*;
importjava.util.*;

classRadix {

staticintgetMax(intarr[], intn)
 {
intmx = arr[0];
for (inti = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
returnmx;
 }

staticvoidcountSort(intarr[], intn, intexp)
 {
intoutput[] = newint[n]; // output array
inti;
intcount[] = newint[10];
Arrays.fill(count, 0);

// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;

for (i = 1; i < 10; i++)
count[i] += count[i - 1];

for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
 }

for (i = 0; i < n; i++)
arr[i] = output[i];
 }

// The main function to that sorts arr[] of
// size n using Radix Sort
staticvoidradixsort(intarr[], intn)
 {
intm = getMax(arr, n);

for (intexp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
 }

// A function to print an array
staticvoidprint(intarr[], intn)
 {
for (inti = 0; i < n; i++)
System.out.print(arr[i] + " ");
 }

publicstaticvoidmain(String[] args)
 {
intarr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
intn = arr.length;

// Function Call
radixsort(arr, n);
print(arr, n);
 }
}