Click here to Skip to main content
11,487,979 members (79,721 online)
Click here to Skip to main content

Tagged as

C++ Count Sort Implementation

, 28 Nov 2011 CPOL 20.3K 2
Rate this:
Please Sign up or sign in to vote.
A basic copiable count sort implementation.

Introduction

Counting sort is an algorithm generally used for sorting smaller integers. It is able to sort integer input in linear time and is ideal for situations where a large number of integer keys need to be sorted. For smaller sets, a comparison sort is probably more appropriate. It is best used when the integer keys are not larger than the number of items in the set and is thus, frequently combined with radix sort, which allows for larger input keys.


Background

Based on Introduction to Algorithms Third Edition p. 195.

Counting sort assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When k=O(n), the sort runs in theta(n) time. Counting sort determines, for each input element x, the number of elements less than x. It uses this information to place element x directly into its position in the output array. For example, if 17 elements are less than x, then x belongs in output position 18.

CONFUSING NOTE: This algorithm assumes that the C array starts at index 0 and
the A array starts at index 1. This had to be accounted for in the actual code.
I did this by making the bounds of some of the loops go from 0 to k inclusive
and by subtracting 1 in from the array index of B in line 11 of the algorithm.

COUNTING-SORT(A, B, k)
 
1)     let C[0..k] b. a new array<<br mode="hold" />2)     for i=0 to k do
3)          C[i] = 0
4)     for j to length[A] do
5)          C [ A[ j ]] C [ A[ j ]] + 1
6)     //C[i] now contains the number of elements equal to i.
7)     for i = 1 to k do
8)          C[i] = C[i] + C[i − 1]
9)     // C[i] now contains the number of elements less than or equal to i.
10)    for j length[A] down to 1 do
11)         B[C[A[j]]] = A[j]
12)         C[A[j]] = C[A[j]] − 1



Using the Code

To use the code in your own program, copy and paste the count sort function below into your code. The code is designed to be modular. It takes as input the array to be sorted and a value k, which represents the largest value in the array.


/* Count Sort
	Input: int arrayA - An array that contains the data to be sorted.
	       int k - An integer representing the largest input value.
	Output: int* - The function returns a pointer to the original array
		       with the sorted output.
        Compiled With: g++ for i686-apple-darwin10
                       gcc version 4.2.1 (Apple Inc. build 5666)
*/
int *countSort(int arrayA[], int k) {
 
	//Calculate the length of arrayA.
	int arrayA_length = sizeof(arrayA);
 
	//Declare a new array B. B holds the sorted output.
	int * arrayB = (int *)malloc(arrayA_length * sizeof(int));
 
	//Declare a new array C. C provides a temporary workspace.
	int * arrayC = (int *)malloc((k+1) * sizeof(int));
		
	//Initialize the elments of that array to 0.
	for(int i = 0; i <= k; i++)
		arrayC[i] = 0;
 
	//Count the number of each number (confusing I know) and place that
	//value into the array C.
	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.
	for(int i = 0; i < sizeof(arrayA); i++)
		arrayA[i] = arrayB[i];
 
	//Release any used memory. You want to do this because you don't want
	//multiple calls to the sort to use an increasingly large amount of
	//memory.
	free(arrayB);
	free(arrayC);
 
	//Return a pointer to the output arrayB.
	return arrayA;
}
...

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Grant Curell

United States United States
Grant is a specialist in computer security and networking. He holds a bachelors degree in Computer Science and Engineering from the Ohio State University. Certs: CCNA, CCNP, CCDA, CCDP, Sec+, and GHIH. More info at grantcurell.com.

Comments and Discussions

 
QuestionThis method was published in ACM algorithms in 1962? Algorithm #23 "mathsort" Pin
Member 84827825-Nov-14 9:20
memberMember 84827825-Nov-14 9:20 
GeneralReason for my vote of 1 wrong Pin
Alex Cohn29-Nov-11 2:52
memberAlex Cohn29-Nov-11 2:52 
GeneralRe: Could you explain why? Too be quite honest, I'm not particul... Pin
Grant Curell29-Nov-11 5:12
memberGrant Curell29-Nov-11 5:12 
General1) Not so optimal code (indexing): //Count the number of e... Pin
martin.capousek28-Nov-11 1:55
membermartin.capousek28-Nov-11 1:55 
GeneralRe: Thanks for catching that bug, coincidentally it still worked... Pin
Grant Curell28-Nov-11 10:02
memberGrant Curell28-Nov-11 10:02 
General[My vote of 1] C++ treatment of sizeof() Pin
Alex Cohn29-Nov-11 2:52
memberAlex Cohn29-Nov-11 2:52 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150520.1 | Last Updated 28 Nov 2011
Article Copyright 2011 by Grant Curell
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid