Count Sort

Counting sort is a technique that counts the frequency of number of distinct elements in the array. Number of counts is stored separately in an auxiliary or Count array and the range of this array depends upon the maximum value of number in the given array.

Given array=A[]

We will follow the below mentioned steps:

STEP 1: We have taken the range 7 for auxiliary or count array which is the max value in the given array. Then initialize all its indexes with 0.

STEP 2:

We match the value of Given array with the index of Count array and increment the value within it to 1 at each occurrence(as you see 1 is incremented 2 times and other 1 times).

STEP 3: Next we will update the Count array so that we get the exact position of elements in our final sorted array. Firstly check out the below array.

We will copy the 0 index value 1 from our previous Count array to our updated Count array. After that we will add the next value in the Count array with previous value and so on till the end of array.

We will use both Given and Count array to create our sorted array whose size will be 6 i.e. the same as size of Given array. Follow the procedure discussed below:

1.We will start from the end of array to maintain the stability of elements in the sorted array. So, First pick the last value of Given array which is 3.

2.Then find the value at index 3 in the Count array which is 5, decrement it to 4. As we got 4 so place the Given array value 3 that we had picked at the index 4 in the Sorted array.

Repeat for the value 2 in the Given array.

1. Pick next value from Given array which is 2.
2. Again find the value at index 2 in the Count array which is 4 then decrement it to 3. So, place the picked value 2 from Given array to index 3 in the Sorted array.

Repeat for the value 1 in the Given array.

1. Pick next value from given array which is 1.
2. Then find the index 1 value in the Count sort which is 3 decrement it to 2. Then place the picked Given array value 1 at index 2 in Sorted array.

Repeat the above procedure same for the pending elements in the Given array

Program:

Count Sort Program

<?php

$A =[7,0,1,1,2,3,56,23] ; 
$A = countSort($A,count($A));
printArray($A,count($A));

function countSort($A,$length){
    $count = [];$i=0;$max=0;
    $max = maxValue($A,$length);
    echo("Max value: ".$max).'<br>';

    //Initialise Count array
    for($i=0;$i<=$max;$i++){
        $count[$i] = 0;
    }
    
    // Increment Count array from
    // 0 to no. of occurences within the given array
    for($i=0;$i<$length;$i++){
        $count[$A[$i]] =  $count[$A[$i]]+1;
    }
    // To find position of elements
    for($i=1;$i<=$max;$i++){
        $count[$i] = $count[$i-1]+$count[$i];
    }
    for($i= $length-1 ; $i>=0 ; $i--){
        $B[--$count[$A[$i]]] = $A[$i];
    }
    for ($i = 0; $i < $length; $i++) {
        $A[$i] = $B[$i];
    }
    return $A;
}

 function maxValue($A,$length){
    $max = $A[0] ;

    for($i=0;$i<=$length-1;$i++){
        if($A[$i]>$max){
            $max = $A[$i];
        }
    }
    return $max;
}
function printArray($arr,$n){
    echo "Sorted Array:";
    for($i= 0 ; $i<$n ;$i++){
        printf("%d\n", $arr[$i]);
    }
}



?>

#include<stdio.h>

int maxValue(int A[],int length);
void printArray(int A[], int length);
void countSort(int A[], int length);

void main(){
    int A[100],length,i,max;
    printf("Enter the size of array\n");
    scanf("%d",&length);
    printf("Enter the %d elements\n",length);

    for(i=0 ;i<=length-1; i++){
        scanf("%d",&A[i]);
    }
    countSort(A,length);
    printArray(A,length);
}
void countSort(int A[], int length){
    int count[100],i,max,B[100];
    max = maxValue(A,length);
    printf("Max value %d\n",max);

    //Initialise Count array
    for(i=0;i<=max;i++){
        count[i] = 0;
    }
    
    // Increment Count array from
    // 0 to no. of occurences within the given array
    for(i=0;i<length;i++){
        count[A[i]] =  count[A[i]]+1;
    }
    // To find position of elements
    for(i=1;i<=max;i++){
        count[i] = count[i-1]+count[i];
    }
    for(i= length-1 ; i>=0 ; i--){
        B[--count[A[i]]] = A[i];
    }
    for (int i = 0; i < length; i++) {
        A[i] = B[i];
    }
}

int maxValue(int A[],int length){
    int max = A[0] ,i;

    for(i=0;i<=length-1;i++){
        if(A[i]>max){
            max = A[i];
        }
    }
    return max;
}
void printArray(int arr[],int n){
    printf("Sorted Array\n");
    for(int i= 0 ; i<n ;i++){
        printf("%d\n", arr[i]);
    }
}