Adding a simple implementation of the sorting algorithm which is called "Counting Algorithm". #3230
Description
I implemented the counting algorithm in a few lines of code which i think it would be easy to be understood by beginners. And i would like to be accepted and added to your repository.
class CountingSort {
private final int[] OriginalArray;
private final int MaxRange;
/**
* @param arr is the input array which holds the integer values to be sorted
* @param Max is the number of digits that the max item in this array has
*/
CountingSort(int[] arr, int Max) {
this.OriginalArray = arr;
this.MaxRange = Max;
}
/**
* sort the numbers using 'counting algorithm'
* @return the sorted array based on counting algorithm
*/
protected int[] StartSorting() {
var OccurArray = new int[MaxRange];
for (var i : OriginalArray)
OccurArray[i] += 1;
for (var i = 0; i < OccurArray.length - 1; i++)
OccurArray[i + 1] += OccurArray[i];
var SortedArray = new int[OriginalArray.length + 1];
for (var i : OriginalArray) {
SortedArray[OccurArray[i]] = i;
OccurArray[i]--;
}
return SortedArray;
}
public static void main(String[] args) {
// generate 100000 random numbers between 0 and 1000000000
var arr = new Random().ints(100000, 0, 1000000000).toArray();
// define a sorting object from counting sort class
var SortingEngine = new CountingSort(arr, 1000000000);
// get the start time
var Start = System.currentTimeMillis();
// start sorting
var Result = SortingEngine.StartSorting();
// get the end time
var End = System.currentTimeMillis();
// System.out.println(Arrays.toString(Result));
// print the duration time of sorting
System.out.println("time of sorting : " + "\t" + (End - Start) + " ms");
}
}
the output :
time of sorting : 2109 ms