My own algorithm to sort integers

Question

I'm studying the C language with a Harvey Deitel book.

Trying to solve an exercise that asked to write a good sorting algorithm, I did this:

void sort(int v[], int d){

int max = 0;
for(int i = 0; i < d; i++){
    if(v[i] > max)max = v[i];
}

int v2[max+1];  
int v3[max+1];  
for(int i = 0; i < max+1; i++){
    v2[i] = -1;
    v3[i] = 0;
}

for(int i = 0; i < d; i++){
    if(v3[v[i]] == 0){
        v2[v[i]] = v[i];
        v3[v[i]]++;
    }
    else {
        v3[v[i]]++;
    }
}

int j = 0;
for(int i = 0; i < max+1; i++){
    if(v2[i] != -1){
        for(int k = 0; k < v3[i]; k++){
            v[j] = v2[i];
            j++;
        }
    }
}
}

Answer 1

basically you are trying to create a space the size of max value and fill it with values(count of the array values in their position in v3) >=0, then refill our array with the values from the space v3

the only change I'd suggest is to completely remove the v2 array

void sort(int *v, int d) {

    int max = 0;
    for (int i = 0; i < d; i++) {
        if (v[i] > max)max = v[i];
    }

    int v3[max + 1];
    for (int i = 0; i < max + 1; i++) {
        v3[i] = 0;
    }

    for (int i = 0; i < d; i++) {
        v3[v[i]]++;
    }

    int j = 0;
    for (int i = 0; i < max + 1; i++) {
        if (v3[i] != 0) {
            for (int k = 0; k < v3[i]; k++) {
                v[j] = i;
                j++;
            }
        }
    }
}

Note:

1. this sort mechanism takes up too much memory in case of numbers with greatly varying differences
2. will not support negative values

Answer 2

I would do six changes:

• Better variable names, especially for the arguments
• Remove unnecessary temporary array
• Handle negative numbers
• Initialize temporary array with memset instead of a loop.
• Comments with pre and post conditions
• Dynamically allocate the temporary array to avoid problems with the stack for large arrays.

The code looks like this:

/* Preconditions:
   array is a pointer to the array that should be sorted
   length is the number of elements in the array

   Postconditions:
   array is sorted
*/
void sort(int *array, size_t length) {
    if(!array || length<1) return;

    int max = array[0];
    int min = max;

    for (int i = 0; i < length; i++) {
        if(max < array[i]) max = array[i];
        if(min > array[i]) min = array[i];
    }

    const size_t range = max - min + 1;
    const size_t size = range * sizeof *array;
    int *tmp = malloc(size);
    if(!tmp) { /* Handle allocation error */ }
    memset(tmp, 0, size);

    for (int i = 0; i < length; i++) tmp[array[i] - min]++;

    int index = 0;
    for (int i = 0; i < range; i++) {
        for (int j = 0; j < tmp[i]; j++) {
                array[index] = i + min;
                index++;
        }
    }
    free(tmp);
}