Counting Sort

Download Counting Sort

---

//

//  main.cpp

//  Counting_Sort

//

//  Created by Z Pei on 12/24/18.

//  Copyright © 2018 Z Pei. All rights reserved.

//

// C Program for counting sort

#include <stdio.h>

#include <string.h>

#define RANGE 255

// The main function that sort the given string arr[] in

// alphabatical order

void countSort(char arr[])

{

    // The output character array that will have sorted arr

    char output[strlen(arr)];

    

    // Create a count array to store count of inidividul

    // characters and initialize count array as 0

    int count[RANGE + 1], i;

    memset(count, 0, sizeof(count));

    

    // Store count of each character

    for(i = 0; arr[i]; ++i)

        ++count[arr[i]];

    

    // Change count[i] so that count[i] now contains actual

    // position of this character in output array

    for (i = 1; i <= RANGE; ++i)

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

    

    // Build the output character array

    for (i = 0; arr[i]; ++i)

    {

        output[count[arr[i]]-1] = arr[i];

        –count[arr[i]];

    }

    

    /*

     For Stable algorithm

     for (i = sizeof(arr)-1; i>=0; –i)

     {

     output[count[arr[i]]-1] = arr[i];

     –count[arr[i]];

     }

     

     For Logic : See implementation

     */

    

    // Copy the output array to arr, so that arr now

    // contains sorted characters

    for (i = 0; arr[i]; ++i)

        arr[i] = output[i];

}

// Driver program to test above function

int main()

{

    char arr[] = “geeksforgeeks”;//”applepp”;

    

    countSort(arr);

    

    printf(“Sorted character array is %sn \n”, arr);

    return 0;

}

---