Skip to content

Instantly share code, notes, and snippets.

@davps
Created March 22, 2018 20:25
Show Gist options
  • Save davps/9fcf7df85c936164b6c013f4f653dff3 to your computer and use it in GitHub Desktop.
Save davps/9fcf7df85c936164b6c013f4f653dff3 to your computer and use it in GitHub Desktop.
Radix sort implementation, archived from here: http://www.topjavatutorial.com/java/java-programs/radix-sort-in-java/
package com.javatutorial;
import java.util.ArrayList;
import java.util.List;
public class ExampleRadixSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] num = {170, 45, 75, 90, 802, 2, 24, 66,23,234,3,232,44};
radixsort(num);
for (int h : num)
System.out.print(h + " ");
}
public static void radixsort(int[] input) {
List<Integer>[] buckets = new ArrayList[10];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<Integer>();
}
// sort
boolean flag = false;
int tmp = -1, divisor = 1;
while (!flag) {
flag = true;
// split input between lists
for (Integer i : input) {
tmp = i / divisor;
buckets[tmp % 10].add(i);
if (flag && tmp > 0) {
flag = false;
}
}
// empty lists into input array
int a = 0;
for (int b = 0; b < 10; b++) {
for (Integer i : buckets[b]) {
input[a++] = i;
}
buckets[b].clear();
}
// move to next digit
divisor *= 10;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment