/*
Class: cs312
Description: This program is written in C++, so you
need to translate it to java language.
The program is an array of numbers which you
have to sort by using linear sort. Also you
must find the range of the array.
*/
/*
#include<iostream>
using namespace std;
void CountSort(int A[], int B[], int size, int range)
//Assumptions, A[] is the usorted array of size integer values
//in the in the interval from 0 through "range"
//B[] is a second "empty" array of "size" integers
//Output: The array B[] will contain the sorted elements of A[]
//array A[] is unchanged. Note, array C[] is local to the procedure.
{
int* C = new int[range + 1];
int i;
for(i = 0; i <= range; i++)
C[i] = 0; //intialized to 0
for(i =0; i < size; i++)
C[A[i]]++; //C[i] is the number of elements of A[]
//equal to i
for(i = 1; i <= range; i++)
C[i] = C[i] + C[i-1]; //C[i] is now the number of
//elements of A[] that are <= i
for( i = size-1; i >= 0; i--)
{
B[C[A[i]]-1] = A[i]; //Store the elements of A[]
C[A[i]]--; //into B[] in sorted order
}
delete [] C;
}
void main()
{ //The given array x[] is integers in the range 0 through 100
int y[20], k;
int x[20] = {45, 76, 31, 29, 0, 83, 47, 11, 16, 99, 26, 54,
39, 17, 67, 91, 29, 43, 76, 12};
for(k=0; k< 20; k++)
cout <<x[k] <<" ";
cout <<endl;
CountSort(x, y, 20, 100);
cout <<"Test 1 \n";
for (k = 0; k < 20; k++)
cout << y[k] <<" ";
cout <<endl;
}
// output
// 45 76 31 29 0 83 47 11 16 99 26 54 39 17 67 91 29 43 76 12
// Test 1
// 0 11 12 16 17 26 29 29 31 39 43 45 47 54 67 76 76 83 91 99
*/
public class LinearSort
{
public static int findRange(int[] a)
{
int range = a[0];
for (int i = 1; i < a.length; i++)
{
if(a[i]> range)
range = a[i];
}
return range;
}
public static void CountSort(int [] A, int [] B, int size, int range)
{
//int* C = new int[range + 1];
int []C = new int[range + 1];
int i;
for(i = 0; i <= range; i++)
C[i] = 0;
for(i =0; i < size; i++)
C[A[i]]++;
for(i = 1; i <= range; i++)
C[i] = C[i] + C[i-1];
for( i = size-1; i >= 0; i--)
{
B[C[A[i]]-1] = A[i];
C[A[i]]--;
}
}
public static void main(String[] args)
{
int [] A = { 67, 43, 12, 85, 145, 3, 190, 15,
76, 101, 36, 173, 91, 24, 7, 143, 29};
int [] B = new int [ A.length ];
int Range = 0;
int size = A.length;
Range = findRange(A);
System.out.println("The range is: "+ Range);
System.out.println();
System.out.println("empty array");
for ( int i = 0; i < A.length; i++)
System.out.print(B[i] + " ");
System.out.println();
System.out.println();
System.out.println("The array un-sorted");
for(int i=0; i< A.length; i++)
System.out.print(A[i] + " ");
System.out.println();
System.out.println();
CountSort(A, B, size, Range);
System.out.println("Test2: The array sorted");
for(int k = 0; k < size; k++)
System.out.print(B[k] + " ");
}
}
/*
Z:\>java LinearSort
The range is: 99
empty array
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
The array un-sorted
45 76 31 29 0 83 47 11 16 99 26 54 39 17 67 91 29 43 76 12
Test1: The array sorted
0 11 12 16 17 26 29 29 31 39 43 45 47 54 67 76 76 83 91 99
Z:\>java LinearSort
The range is: 190
empty array
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
The array un-sorted
67 43 12 85 145 3 190 15 76 101 36 173 91 24 7 143 29
Test2: The array sorted
3 7 12 15 24 29 36 43 67 76 85 91 101 143 145 173 190
*/