In this article, we will cover Radix sort algorithm in java.
Radix sort
Radix sort algorithm sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.
Rather than directly applying bucket sort to a set of elements, this performs bucket sorting the set digit by digit.
There are two general types of radix sort :
- LSD radix sort : Sorting starts with the least significant digit (LSD), and continuing on until the most significant digit (MSD).
- MSD radix sort : Sorting starts with the most significant digit and ends with the least significant digit.
In this article, we will look at LSD Radix sort.
LSD Radix sort Java program
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; } } }
Output
2 3 23 24 44 45 66 75 90 170 232 234 802
Reference
https://en.wikipedia.org/wiki/Radix_sort
http://web.engr.oregonstate.edu/~budd/Books/jds/info/src/jds/sort/RadixSort.java
© 2016, https:. All rights reserved. On republishing this post, you must provide link to original post
#