Counting Sort Algorithm (Non-Comparison Sorting)

Counting Sort ek non-comparison based linear time sorting algorithm hai. Standard comparison-based algorithms (jaise Merge Sort, Quick Sort) lower bound Ω(n log n) se fast nahi ho sakte. Lekin Counting Sort elements ko compare karne ke bajay unki frequencies (counts) calculate karta hai, jisse yeh O(n + k) time me sort kar leta hai, jahan k input numbers ki range (max value) hai.

Algorithm Steps

1. Input array me se maximum element k find karte hain.
2. Size k + 1 ka ek Count Array initialize karte hain with zeroes.
3. Har element ke occurrence count ko store karte hain.
4. Count array ko Cumulative (Prefix Sum) Array me convert karte hain. Isse har element ka exact output index pata chal jata hai.
5. Input array ko reverse order me iterate karke output array me elements place karte hain (reverse iteration stability maintain rakhta hai).

Input Array A: [ 4, 2, 2, 8, 3, 3, 1 ]  (Max k = 8)

1. Frequency Count Array C:
Index: 0  1  2  3  4  5  6  7  8
Count: [0, 1, 2, 2, 1, 0, 0, 0, 1]

2. Cumulative Prefix Sum:
Count: [0, 1, 3, 5, 6, 6, 6, 6, 7]

3. Output Placement (Stable):
Output: [ 1, 2, 2, 3, 3, 4, 8 ]

Complexity and Limitations

• Time Complexity: O(n + k) sabhi cases me (Best, Average, Worst). Agar k = O(n) ho, toh algorithm linear O(n) time me run karta hai.
• Space Complexity: O(n + k) auxiliary space (Count array aur Output array ke liye).
• Stability: Stable sorting algorithm.
• Limitation: Agar range k bohot badi ho jaye (e.g. 5 elements hain lekin numbers 1 se 1,000,000 tak hain), toh count array impractical aur memory inefficient ho jati hai. Yeh negative numbers ya floating-point values ke liye direct suitable nahi hoti bina coordinate shifting ke.

Agli post me hum cover karenge Radix Sort Algorithm and Bucket Distribution.