Couting Sort - How it Works Steps

NoteGPT - AI Generated Image

 

Here's a cleaner and simpler version with an example in Step 4:

Counting Sort – How it Works

1. Find the maximum value (or minimum & maximum if negatives exist).

2. Create a count array(zero's newarray) of size max + 1 , and feel it with same 0

3. Traverse the original array.

4. Use original array each element as the index of the count array(new array) and increase that position its count by 1.
   Example: If the element is 3 in original array, do count[3]++ in coutn array.

5. Traverse the count array.

6. For each index, add that value to the sorted array as many times as its count.
   Example: If count[3] = 2, add 3 two times.

7. Rebuild the original (or sorted) array: For each index, put that index value into the array as many times as its count.

   • If count[0] = 0 → put 0 zero times.
   • If count[2] = 3 → put 2 three times (2, 2, 2).
   • If count[5] = 1 → put 5 one time.

Memory Trick

Find Max → Create Count → Count → Rebuild

Example

Original Array : [ 4  2  2  8  3 ]

Here maximum element is 8

Now we create a new array with same size of 8

count array: [ ] ,size = 8

Now fill with 0's

count array: [0,0,0,0,0,0,0,0]

Index :  0  1  2  3  4  5  6  7  8

Count :  0  0  0  0  0  0  0  0  0

Now look Original Array : [ 4  2  2  8  3 ] dude we goign traverse here one by one

First is here element 4 

Now at count array  4th position we do increment 

count array; [0,0,0,0,1,0,0,0]

Element 4 → count[4]++

Element 2 → count[2]++

Element 2 → count[2]++

Element 8 → count[8]++

Element 3 → count[3]++

this Final output looks like : 

Index :  0  1  2  3  4  5  6  7  8

Count :  0  0  2  1  1  0  0  0  1

count[2] = 2 → 2, 2

count[3] = 1 → 3

count[4] = 1 → 4

count[8] = 1 → 8