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++;
 }
 }
}
}

• greybeard: (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?)
• Malachi: 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
• janos: 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.
• 200_success: I think that these comments should be written as answers.
• Yurim: 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.

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

• greybeard: (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?
• Deepan: Like @Yurim said in the comments on the question, It is called the Counting Sort here's wiki page for the explanation
• Alex: 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
• chux: Simplification: if (v3[i] != 0) not needed.
• Deepan: 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.

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);
}

• greybeard: The one thing I'd do differently (apart from formatting) would be for (int j = tmp[i] ; 0 <= --j ; ) array[++index] = i + min;.
• klutt: @greybeard Thank you. I named it list at first, but later changed it to array.
• klutt: @chux Very late, but I fixed the problem with length == 0 and overflow problem.
• chux: 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.