# My own algorithm to sort integers

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

• (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?) Commented Dec 8, 2018 at 15:49
• 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 Commented Dec 8, 2018 at 15:49
• 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. Commented Dec 8, 2018 at 16:07
• I think that these comments should be written as answers. Commented Dec 8, 2018 at 16:50
• 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. Commented Dec 8, 2018 at 18:08

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
• (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? Commented Dec 8, 2018 at 18:16
• Like @Yurim said in the comments on the question, It is called the Counting Sort here's wiki page for the explanation Commented Dec 8, 2018 at 20:15
• 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
– Alex
Commented Dec 8, 2018 at 20:53
• Simplification: if (v3[i] != 0) not needed. Commented Dec 11, 2018 at 10:11
• 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. Commented Dec 11, 2018 at 12:24

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

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