Improve the time complexity of my implementation of Counting Sort (C)

Question

Consider the following code:

#define SIZE 12

void randomize(int* array, int array_size);
void print(int* array, int array_size);
void counting_sort(int* array, int array_size);
int get_max(int* array, int array_size);
void construct(int* sorted, int sorted_array_size, int* values);

int main(void)
{
    srand(time(NULL));
    int* array = (int*)malloc(sizeof(int) * SIZE);
    randomize(array, SIZE);
    print(array, SIZE);
    counting_sort(array, SIZE);
    free(array);

    return 0;
}

void randomize(int* array, int array_size) {...}

void print(int* array, int array_size) {...}

void counting_sort(int* array, int array_size) {
    int minVal, maxVal;
    int* sorted = (int*)malloc(sizeof(int) * SIZE);
    maxVal = get_max(array, array_size);

    int* values = (int*)malloc(maxVal * sizeof(int));

    memset(values, 0, maxVal * sizeof(int));

    for (int i = 0; i < array_size; i++) {
        values[array[i]]++;
    }

    construct(sorted, SIZE, values);

    free(values);
    free(sorted);
    }

int get_max(int* array, int array_size) {...}

void construct(int* sorted, int array_size, int* values) {
    for (int i = 0, j = 0; i < array_size; i++) {
        while (!values[++j]);
        sorted[i] = j;
        --values[j];
    }
    print(sorted, SIZE);
}

main() declares an array, the size of which is controlled by the macro SIZE. Then there are a few functions to randomize, print and find the max value of that array. After that is the implementation of Counting Sort itself, which uses the construct(..) function to create the sorted array. I've tested it a few times and couldn't find any bugs. However this bit right here is what I'm concerned about.

for (int i = 0, j = 0; i < array_size; i++) {
            while (!values[++j]);...

We have 2 inner loops, and the variables in these loops are incremented. This means that the time complexity of the construct(...) function becomes quadratic, and not linear. The issue is that I can't figure out a good way to discard all of the 0 in values[]. Linear solutions are most welcome.

Added full code:

#include <stdlib.h>
#include <cassert>
#include <time.h>
#include <limits.h>
#include <string.h>

#define SIZE 160

void randomize(int* array, int array_size);
void print(int* array, int array_size);
void counting_sort(int* array, int array_size);
int get_max(int* array, int array_size);
void construct(int* sorted, int sorted_array_size, int* values);

int main(void)
{
    srand(time(NULL));
    int* array = (int*)malloc(sizeof(int) * SIZE);
    randomize(array, SIZE);
    print(array, SIZE);
    counting_sort(array, SIZE);
    free(array);

    return 0;
}

void randomize(int* array, int array_size) {
    for (int i = 0; i < array_size; i++) {
        array[i] = rand() % array_size;
    }
}

void print(int* array, int array_size) {
    for (int i = 0; i < array_size; i++) {
        printf("%4d ", array[i]);
    }
    putchar('\n');
}

void counting_sort(int* array, int array_size) {
    int minVal, maxVal;
    int* sorted = (int*)malloc(sizeof(int) * SIZE);
    maxVal = get_max(array, array_size);

    int* values = (int*)malloc(maxVal * sizeof(int));

    memset(values, 0, maxVal * sizeof(int));

    for (int i = 0; i < array_size; i++) {
        values[array[i]]++;
    }

    construct(sorted, SIZE, values);

    free(values);
    free(sorted);
}

int get_max(int* array, int array_size) {
    int max = INT_MIN;
    for (int i = 0; i < array_size; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

void construct(int* sorted, int array_size, int* values) {
    for (int i = 0, j = 0; i < array_size; i++) {
        while (!values[j]) {
            ++j;
        }
        sorted[i] = j;
        --values[j];
    }
    print(sorted, SIZE);
}

Does that code even work? Have you tried it with an array like `{5,5,5,0,0,0}`? — user3386109, Jun 05 '19 at 07:29
Possible duplicate: [Correctly allocating multi-dimensional arrays](https://stackoverflow.com/questions/42094465/correctly-allocating-multi-dimensional-arrays). The obvious performance loss in this program is the lack of 2D arrays - instead you are working with segments scattered all over the heap. Also, calloc might potentially be ever so slightly faster than malloc + memset. — Lundin, Jun 05 '19 at 07:42
"_becomes quadratic, and not linear._" no because you never reset _j_ nor decrements it, so the complexity is 2*array_size (values have the same size as sorted if I well understand) ... supposing your algo is correct (like @user3386109 I a not sure of that, but you do not give all the code) — bruno, Jun 05 '19 at 07:45
First of all you have UB by accessing out of bound, suppose you have an array `{0,5,4}` maximum element being `5` then you allocate `values` with size `5` and you access `values[5]` in the loop (`values[array[i]]++;`). — kiran Biradar, Jun 05 '19 at 07:49
The full code has no resemblance to the original code. You should delete the original, and fix the snippet you're asking about to match the full code. — user3386109, Jun 05 '19 at 07:53

score 2 · Accepted Answer · answered Jun 05 '19 at 07:52

2

Your implementation is linear. You have an inner while loop, but the value of j is never reset to 0, it keeps growing in each iteration of the for loop. Overall i will count from 0 to size and j will count from 0 to n.

answered Jun 05 '19 at 07:52

Shuki Avraham

1,033
1
7
14

Improve the time complexity of my implementation of Counting Sort (C)

1 Answers1