Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Counting sort does not order the last element C

I have written this code in order to implement the Counting Sort in C. However it does not seem working properly.
I create an array of 10 elements and then I apply the steps of counting sort. Basically it orders the first elements, and then as last elements it uses the last elements of the original array. I am not understanding where is the problem.
The code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    // create an array of 100 random elements
    // int my_array[10];
    int my_array[] = { 10, 10, 9, 9, 6, 5, 4, 3, 2, 1 };
    srand(time(NULL));
    int i;
    int N = 10;

    /* for (i = 0; i < 10; i++) {
        my_array[i] = rand() % 100 + 1;
    } */

    // print the array 
    for (i = 0; i < 10; i++) {
        printf("%d\n", my_array[i]);
    } 

    // define the minimum and the maximum as the first element of the array
    int min_array = my_array[0];
    int max_array = my_array[0];

    printf("--------------\n");

    // find the minimum and the maximum of the array
    for (i = 0; i < N; i++) {
        if (my_array[i] < min_array) {
            min_array = my_array[i];
        }
        else if (my_array[i] > max_array) {
            max_array = my_array[i];
        }
    }

    // check if it worked
    printf("max_array %d\n", max_array);
    printf("min_array %d\n", min_array);

    //
    int range_array;
    range_array = max_array - min_array + 1;
    int count_array[range_array + 1];

    for (i = 0; i < range_array; i++)
        count_array[i] = 0;

    int j = 0;
    
    for (int i = 0; i < 10; i++) {
        count_array[my_array[i] - min_array] = count_array[my_array[i] - min_array] + 1;
    }
    
    int z = 0;

    for (i = min_array; i < max_array; i++) {
        for (j = 0; j < count_array[i - min_array]; j++)
            my_array[z++] = i;
            
        // z = z + 1;
    }

    for (i = 0; i < N; i++) {
        printf("%d\n", my_array[i]);
    }
}

And one possible output:

10 10 9 9 6 5 4 3 2 1
--------------
max_array 10
min_array 1
--------------
1 2 3 4 5 6 9 9 2 1

So as you can see the numbers from 1 to 9 are ordered, while the last one, 10, is not ordered, and it uses the first numbers, so 1 and 2.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>Solution :

When rebuilding the array, you want to include the elements with a value of max_array.

i<max_array

should be

i<=max_array

As a side note, you never use the last element of count_array, so it should be one element smaller.

int count_array[range_array + 1];

should be

int count_array[range_array];

(Spotted by @user3386109)

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading