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.

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)

Counting sort does not order the last element C

Related

Recent Posts