Last active
February 13, 2017 20:15
-
-
Save ttungl/09a0ac7b27f34234e687f8617e0dd0bf to your computer and use it in GitHub Desktop.
Counting sort
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // http://ideone.com/7RLpDt | |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| void Print_Array(int * array, int array_size){ | |
| for (int i = 0; i < array_size; ++i) | |
| { | |
| if(i == (array_size-1)){ | |
| printf("%d \n", array[i]); | |
| } else { | |
| printf("%d, ", array[i]); | |
| } | |
| } | |
| } | |
| int Maximum_Number(int * array, int array_size){ | |
| int max_no = array[0]; | |
| for (int i = 0; i < array_size; ++i) | |
| { | |
| if(array[i]> max_no){ | |
| max_no = array[i]; | |
| } | |
| } | |
| return max_no; | |
| } | |
| void Counting_Sort(int * array, int array_size){ | |
| int max = Maximum_Number(array, array_size); | |
| int arrayB[array_size]; | |
| int arrayC[max]; | |
| int k = 0; | |
| for (int i = 0; i < array_size; ++i) // init B | |
| { | |
| arrayB[i] = 0; | |
| } | |
| for (int i = 0; i <= max; ++i) // init C | |
| { | |
| arrayC[i] = 0; | |
| } | |
| for (int i = 0; i < array_size; ++i) | |
| { | |
| arrayC[array[i]]++; // C[A[i]] = C[A[i]] + 1; | |
| } | |
| for(int i = 0; i <= max; i++){ | |
| for(int j = 0; j < arrayC[i]; j++){ | |
| arrayB[k] = i; | |
| k++; | |
| } | |
| } | |
| printf("Input array: "); Print_Array(array, array_size); | |
| printf("Sorted array: "); Print_Array(arrayB, array_size); | |
| } | |
| int main(){ | |
| int arrayA[] = {2, 6, 4, 3, 2, 3, 4, 6, 3, 4, 3, 5, 2, 6}; | |
| int sizeA = sizeof(arrayA)/sizeof(int); // size of array A. | |
| Counting_Sort(arrayA, sizeA); // caller | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment