You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
64 lines
1.9 KiB
Java
64 lines
1.9 KiB
Java
/**
|
|
** Java Program to Implement Radix Sort
|
|
**/
|
|
|
|
import java.util.Scanner;
|
|
|
|
/** Class RadixSort **/
|
|
public class RadixSort
|
|
{
|
|
/** Radix Sort function **/
|
|
public static void sort( int[] a)
|
|
{
|
|
int i, m = a[0], exp = 1, n = a.length;
|
|
int[] b = new int[10];
|
|
for (i = 1; i < n; i++)
|
|
if (a[i] > m)
|
|
m = a[i];
|
|
while (m / exp > 0)
|
|
{
|
|
int[] bucket = new int[10];
|
|
for (i = 0; i < n; i++)
|
|
bucket[(a[i] / exp) % 10]++;
|
|
for (i = 1; i < 10; i++)
|
|
bucket[i] += bucket[i - 1];
|
|
for (i = n - 1; i >= 0; i--)
|
|
b[--bucket[(a[i] / exp) % 10]] = a[i];
|
|
for (i = 0; i < n; i++)
|
|
a[i] = b[i];
|
|
exp *= 10;
|
|
}
|
|
}
|
|
/** Main method **/
|
|
public static void main(String[] args)
|
|
{
|
|
Scanner scan = new Scanner( System.in );
|
|
System.out.println("Radix Sort Test\n");
|
|
int n, i;
|
|
/** Accept number of elements **/
|
|
System.out.println("Enter number of integer elements");
|
|
n = scan.nextInt();
|
|
/** Create integer array on n elements **/
|
|
int arr[] = new int[ n ];
|
|
/** Accept elements **/
|
|
System.out.println("\nEnter "+ n +" integer elements");
|
|
for (i = 0; i < n; i++)
|
|
arr[i] = scan.nextInt();
|
|
/** Call method sort **/
|
|
sort(arr);
|
|
/** Print sorted Array **/
|
|
System.out.println("\nElements after sorting ");
|
|
for (i = 0; i < n; i++)
|
|
System.out.print(arr[i]+" ");
|
|
System.out.println();
|
|
}
|
|
}
|
|
|
|
/*Enter number of integer elements
|
|
10
|
|
|
|
Enter 10 integer elements
|
|
877 567 3456 876 467 26 934 9876 1 4567
|
|
|
|
Elements after sorting
|
|
1 26 467 567 876 877 934 3456 4567 9876*/ |