3

I have recently implemented a sorting algorithm in c and decide to time it against quicksort (see here for the timing method). As I expected, it was slower by multitudes, but when I lowered the difference between the minimum and maximum values in the array the times for my homebrew sorting algorithm became progressively smaller. I eventually made the difference between the minimum and maximum values to 5 and it became lightning fast. On 3 runs with an array with 100 000 elements, I got speeds of 0.0391 milliseconds, 0.0504 milliseconds, and 0.0372 milliseconds!

Here is the code I used:

#include<string.h>

void sort(int* unsorted, const int size) {
    int sorted_index[size];
    int sorted[size];
    int unsorted_copy[size];
    
    memcpy(unsorted_copy, unsorted, sizeof unsorted_copy);
    
    int unsorted_min = unsorted[0];
    for (int i = 0; i < size; i++) {
        if (unsorted[i] < unsorted_min) {
            unsorted_min = unsorted[i];
        }
    }
    
    int sorted_length = 0;
    int i = 0;
    while (sorted_length < size) {
        for (; i < size; i++) {
            if (unsorted[i] == NULL) {
                continue;
            }
            if (unsorted[i] == unsorted_min) {
                sorted_index[sorted_length] = i;
                unsorted[i] = NULL;
                sorted_length++;
            }
            else {
                unsorted[i]--;
            }
        }
        i = 0;
    }
    
    for (int j = 0; j < size; j++) {
        sorted[j] = unsorted_copy[sorted_index[j]];
    }
    
    memcpy(unsorted, sorted, sizeof sorted);
}

As you can see, the program recursively diminishes the values in the array, until they reach the minimum value in the array. At that point, it inserts the index of the value into a new array. At the end of the loops, it inserts the value of unsorted copy[sorted index] into the original array.

Is this technique already a thing or have I invented this.

Thanks in advance!

drake14w
  • 157
  • 9
  • 2
    Oh, you're sorting integers. What a shame, I was really excited :( As far as I know, this is called gravity sort. – Captain Trojan Aug 06 '21 at 23:11
  • 8
    `if (unsorted[i] == NULL)` is not correct. `NULL` should only be used with pointers, not integers. – Barmar Aug 06 '21 at 23:12
  • ^ @Barmar agreed. `NULL` is basically `0` with extra steps, if your array contained that, woo wee that would be very bad. – Captain Trojan Aug 06 '21 at 23:13
  • This algorithm looks like it will only work if the array contains positive numbers. – Barmar Aug 06 '21 at 23:15
  • 1
    It's also called [bead sort](https://en.wikipedia.org/wiki/Bead_sort) – Barmar Aug 06 '21 at 23:16
  • 7
    It however takes skill to develop something like this by yourself independently! Congratz OP, very nice. – Captain Trojan Aug 06 '21 at 23:18
  • Typical quicksort implementations don’t do all that well with many duplicate values in the data. – 500 - Internal Server Error Aug 06 '21 at 23:34
  • I'm also glad for OP:s sake but - is this a programming question? If so, the answer is "no", as Captain Trojan & Barmar hinted. – Ted Lyngmo Aug 06 '21 at 23:35
  • 3
    You're trying to use `NULL` as some special value, but it's not. On most systems it's represented as zero, in which case you might as well use `0`, but that probably exposes a bug in your algorithm. You should also be getting warnings about trying to assign a pointer to an integer. Don't ignore those warnings. Fix them. – Tom Karzes Aug 07 '21 at 00:30
  • The bugs not withstanding, this is essentially a very bad version of [bingo sort](https://en.wikipedia.org/wiki/Selection_sort#Variants), which is a variant of [selection sort](https://en.wikipedia.org/wiki/Selection_sort). Like bingo sort, on each pass, it finds all instances of the smallest value. But it needlessly keeps an index array, rather than moving the values directly to the result, and it tries to skip over previously extracted values, rather than simply closing the gaps. And rather than simply finding the new minimum value each time, it instead counts down one at a time. – Tom Karzes Aug 07 '21 at 00:56
  • These sorting algorithms work well when dealing with multiple instances of a very small number of different values. In this case, you should just use straight bingo sort, which should be faster than this in all cases (and much faster if there's a significant range of values). – Tom Karzes Aug 07 '21 at 00:58
  • 1
    +one for discovering/creating the algorithm ur self. It really *is* a good work. /(^_^) – p._phidot_ Aug 07 '21 at 07:42

0 Answers0