Sort algorithm in c

Question

I wrote this algorithm a while ago, and decided to revisit it and polish it up. It basically works by comparing each number with all the other numbers once, so comparing the first number to all except itself, the second to all numbers after itself etc, to avoid double comparison. I'm sure it has an official name, but have no idea what that would be as I put it together myself.

#include <stdio.h>
#include<stdlib.h>///only needed for example code
#include<time.h>///only needed for example code
int number,scan,totalnumbers;
int main()
{
 totalnumbers=10;///just for the example. functional code would need an input system.
 int array[totalnumbers][3];//one for input, second tallying values, third for transfer output.
 ///for the example choose random numbers :
 srand(time(NULL));
 for (scan=0;scan<totalnumbers;scan++)
 {
 array[scan][0]=rand()%200;
 }
 //fill [2] with zeros, as will be incremented to work out location.
 for (scan=0;scan<totalnumbers;scan++)//formatting the whole array
 {
 array[scan][1]=0;
 }
 for(number=0;number<totalnumbers;number++)
 {
 for(scan=number+1;scan<totalnumbers;scan++)///compare to all numbers, excluding itself
 {
 if(array[number][0]>array[scan][0])
 {
 array[number][1]++;
 }
 else
 {
 array [scan][1]++;///this includes when they are equal, and can be adjusted if you want earlier or later instanses of the same number to be displayed first 
 }
 }
 }
 ///now we put each number into its place in the third 'array'
 for(number=0;number<totalnumbers;number++)
 {
 array[array[number][1]][2]=array[number][0];///the position in array[number] [1] tells us wher the one in array[number][0]should go, and we place it there in [2]
 }
 printf("Results\n");
 for(number=0;number<totalnumbers;number++)
 {
 printf("%d\n",array[number][2]);
 }
}

• Loki Astari: Bubble Sort without the move Followed by Bucket Sort where each bucket has a size of one.

Answer 1

Central

1. In showing the algorithm, it is far better to clearly delineate the test driver code from the core code-under-test. The mixture of the algorithm with test code in main() blurs that boundary. Suggest using a function to set off your algorithm. Something like the following and have main() call it:

   void my_sort(int *destination, const int *source, int *tally, int size)
   

2. The 3 arrays rolled into a 2D array is disconcerting. Code then uses 0,1,2 to note which array rather than a more meaningful #define SOURCE 1 #define TALLY 2, .... Further, the N*N for() loop accesses array[][], yet has to skip over every third element array[][2]. This needlessly spreads out the data, likely increasing cache misses. Also, the type of array[][0] needs to match type of array[][2], yet not type array[][1]. To rectify all these, suggest making 3 separate arrays, 2 of type data_t and the 3rd (tally array) of type size_t. By clearly using data_T, code can readily be adapted to cope with "number" as stated in the post, be it int, double, etc.

   data_T source[totalnumbers];
   data_T destination[totalnumbers];
   size_t tally[totalnumbers];
   

3. A subtle good aspect about this sort is that elements of the same value do not change order. This property is useful in more complicated data types and compares.

4. An important weakness to this sort in that is in O(n*n) rather than a O(n*log2(n)). Yet it does minimize the movement of elements.

5. A weakness to this sort, is that the source and destination array cannot be the same array. Not an in-place sort.

6. I found the description imprecise "It basically works by comparing each number with all the other numbers once" should be "It basically works by comparing each number with all subsequent numbers once"

Minor

1. Why asymmetric spacing in #include statement?

   #include <stdio.h>
   // #include<stdlib.h>
   // #include<time.h>
   #include <stdlib.h> // Add space
   #include <time.h>
   

2. Why /// versus // ? WET vs DRY.

   // #include<stdlib.h>///only needed for example code
   #include <stdlib.h> // only needed for example code
   

3. Avoid unneeded pluralizing totalnumbers  totalnumber

4. Unclear why the blank line after array[] below.

    {
    array[number][1]++;
    }
   

5. With a separate tally array, suggest a memset() call instead

   // for (scan=0;scan<totalnumbers;scan++) {
   // array[scan][1]=0;
   //}
   memset(tally, 0, sizeof tally);
   

6. Respect the presentation width and check spelling (at least 3 words misspelled). Reeding comments ahtat arent spellled korreclty is mor dificult.

    // Too long
    // array [scan][1]++;///this includes when they are equal, and can be adjusted if you want earlier or later instanses of the same number to be displayed first 
   

Instead

 // This includes when they are equal, and can be adjusted if you want 
 // earlier or later instances of the same number to be displayed first 
 array [scan][1]++;

Pedantic

1. srand() expects unsigned. Cast to indicate possible loss of precision is OK

   // srand(time(NULL));
   srand((unsigned) time(NULL));
   

2. Not a fan of the missing return 0; at the end. Although not needed, it adds pause in the review – was this OP’s intent?

3. Suggest a name and date in your code

   // Orangesandlemons 2016