3
\$\begingroup\$

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++;
        }
    }
}
}
\$\endgroup\$
  • 1
    \$\begingroup\$ (Without comments, this code is not maintainable. Whom do you expect to bother to analyse its behaviour from scratch? And foremost what does make a good sorting algorithm good?) \$\endgroup\$ – greybeard Dec 8 '18 at 15:49
  • 1
    \$\begingroup\$ could you perhaps add more information about the task that you have been given? something like Acceptance Criteria, what type of sort you are being asked to create, any limitations provided by the text, etc \$\endgroup\$ – Malachi Dec 8 '18 at 15:49
  • 2
    \$\begingroup\$ It would be good to provide at least a brief description of how this algorithm works, including reasoning about how it's better than bubble sort. If you are not able to reason why it's better overall than bubble sort, at least think about the conditions under which it is clearly better. If you cannot come up with even a basic reasoning, then there's no reason to believe it's better in any way. \$\endgroup\$ – Stop ongoing harm to Monica Dec 8 '18 at 16:07
  • 2
    \$\begingroup\$ I think that these comments should be written as answers. \$\endgroup\$ – 200_success Dec 8 '18 at 16:50
  • 2
    \$\begingroup\$ It looks like you're implementing a Counting Sort. That can indeed be a good choice for a sorting algorithm if the range of values is small. Be careful about negative numbers, though. \$\endgroup\$ – Yurim Dec 8 '18 at 18:08
3
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ (Welcome to Code Review!) I especially like the Note:s. Do you happen to know a name that could be/is given to this sorting method? Do you have remarks/advice about how it is coded? \$\endgroup\$ – greybeard Dec 8 '18 at 18:16
  • \$\begingroup\$ Like @Yurim said in the comments on the question, It is called the Counting Sort here's wiki page for the explanation \$\endgroup\$ – Deepan Dec 8 '18 at 20:15
  • \$\begingroup\$ counting sort is just what I wanted to do. I did not know It. I just tried to make a more efficient algorithm of the Bubble Sort \$\endgroup\$ – Alex Dec 8 '18 at 20:53
  • \$\begingroup\$ Simplification: if (v3[i] != 0) not needed. \$\endgroup\$ – chux - Reinstate Monica Dec 11 '18 at 10:11
  • \$\begingroup\$ yes programmatically it is not needed, but if we were to omit that computationally it will go to for loop and create k and then assign 0 to k and then compare k<v[i] which would increase the computational overhead by a small margin. \$\endgroup\$ – Deepan Dec 11 '18 at 12:24
4
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ The one thing I'd do differently (apart from formatting) would be for (int j = tmp[i] ; 0 <= --j ; ) array[++index] = i + min;. \$\endgroup\$ – greybeard Dec 10 '18 at 9:04
  • \$\begingroup\$ @greybeard Thank you. I named it list at first, but later changed it to array. \$\endgroup\$ – klutt Dec 11 '18 at 14:35
  • \$\begingroup\$ @chux Very late, but I fixed the problem with length == 0 and overflow problem. \$\endgroup\$ – klutt Mar 12 at 6:53
  • \$\begingroup\$ Minor idea: max - min + 1 can overflow int math leading to UB. A better behaved alternative: 1LU + max - min or even better (size_t)1 + max - min. \$\endgroup\$ – chux - Reinstate Monica Mar 12 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.