basic-programs/CountingSort.java at master · BGatya/basic-programs · GitHub

40 lines (36 loc) · 1.2 KB

import java.util.Arrays;

import java.util.Random;

public class CountingSort {

//Implementation of Counting Sort

public static int[] sort(int[] inputArray) {

int[] countArray = new int[100000];

int[] sortedArray = new int[inputArray.length];

Arrays.fill(countArray, 0);

for (int i = 0; i < inputArray.length; i++) {

countArray[inputArray[i] - 1]++;

}

for (int i = 1; i < countArray.length; i++) {

countArray[i] += countArray[i - 1];

}

for (int i = inputArray.length - 1; i >= 0; i--) {

sortedArray[countArray[inputArray[i] - 1] - 1] = inputArray[i];

countArray[inputArray[i] - 1]--;

}

return sortedArray;

}

//Calling sort() function to test Counting Sort

public static void main(String[] args) {

Random rd = new Random();

int[] inputArray = new int[100];

System.out.println("Input Array:");

for (int i = 0; i < inputArray.length; i++) {

inputArray[i] = rd.nextInt(100000) + 1;

System.out.print(inputArray[i] + " ");

}

System.out.println("\nSorted Array:");

int[] sortedArray = sort(inputArray);

for (int i = 0; i < sortedArray.length; i++) {

System.out.print(sortedArray[i] + " ");

}

Expand file tree