In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the maximum key value, so it is only suitable for use directly in situations where the keys are not significantly larger than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.

Here is the C# implementation of Counting Sort

class Program { static void Main(string[] args) { //create an input array with maximum value of an element is 1024 int[] input = new int[10000]; Random random = new Random(); for (int i = 0; i < 10000; i++) { input[i] = random.Next(0, 1024); } Sorting.CountingSort(input); } }

public class Sorting { public static void CountingSort(int[] arrayA) { Console.WriteLine("Original Array"); for (int i = 0; i < arrayA.Length; i++) { Console.Write(arrayA[i] + " , "); } Console.WriteLine(""); int k = 1024; int[] arrayB = new int[arrayA.Length]; int[] arrayC = new int[k]; for (int i = 0; i < arrayC.Length; i++) { arrayC[i] = 0; } for (int j = 0; j < arrayA.Length; j++) { arrayC[arrayA[j]] = arrayC[arrayA[j]] + 1; } //Place the number of elements less than each value at i into array C. for (int i = 1; i < k; i++) arrayC[i] = arrayC[i] + arrayC[i - 1]; //Place each element of arrayA into its correct sorted position in the //output array B. for (int j = arrayA.Length - 1; j >= 0; j--) { arrayB[arrayC[arrayA[j]] - 1] = arrayA[j]; arrayC[arrayA[j]] = arrayC[arrayA[j]] - 1; } //Overwrite the original arrayA with the output arrayB. Console.WriteLine("Sorted Array"); for (int i = 0; i < arrayA.Length; i++) { arrayA[i] = arrayB[i]; Console.Write(arrayA[i] + " , "); } Console.WriteLine(""); } }

in this program I am showing output on console, it can be easily saved on file also.

Leave a comment