0
\$\begingroup\$

So I came up with a "new" sorting algorithm:

function indexSort(array, min, max) {
    var newArray = Array.from({length:Math.abs(max-min)}, () => 0);
    for (let i = 0; i < max; i++) {
        if (array.includes(array[i])) {
            newArray[array[i]] = array[i];
        }
    }
    for (let i = 0; i < newArray.length; i++) {
        if (newArray[i] == 0) { 
            newArray.splice(i, 1); 
            i--;
        }
    }
    return newArray;
}

This algorithm sorts numbers in ascending orders so:

Input -> Output
indexSort([ 3, 1, 2 ], 1, 3) -> [ 1, 2, 3 ]
indexSort([ 64, 12, 9 ], 9, 64) -> [ 9, 12, 64 ]

This algorithm sorts arrays, pretty slow at that, and, has, in its current state some major downsides in comparison to other sorting algorithms:

  • Only works with positive integers.
  • Has to loop over the entire array twice.
  • Doesn't allow for duplicate items.

It has probably other downsides that I cannot currently think of.

So what I want to figure out is:

  • Why is this sorting algorithm so slow?
  • Is it possible to do everything in just one loop using an else statement?
  • Why is this sort outperformed by Bubble Sort?
  • What is the big O notation of this algorithm?
  • Has this already been discovered and if so, what is the name of it?
\$\endgroup\$
11
  • \$\begingroup\$ Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to edit and give it a different title if there is something more appropriate. \$\endgroup\$ Oct 11, 2021 at 22:37
  • 2
    \$\begingroup\$ If you're just trying to implement plain increasing order sort, then why are you using your own (very inefficient algorithm)? If you're trying to implement some other type of sort, then please describe the objective of the srot. I'm trying to figure out what you're trying to accomplish that is different than what you can already do with Array.prototype.sort()? \$\endgroup\$
    – jfriend00
    Oct 11, 2021 at 22:44
  • 2
    \$\begingroup\$ What's the point of if (array.includes(array[i])) {...}? Won't that ALWAYS be true? After all array will always include array[i], right as long as i is within the length of the array? I guess I really don't understand what you're trying to accomplish. I've asked and you've not added any description of the purpose or objective of the sort algorithm. For example, the ONLY place you use min is here Math.abs(max-min). What's the point of that. I guess I will give up until you add enough explanation to understand what you're trying to do. \$\endgroup\$
    – jfriend00
    Oct 11, 2021 at 22:56
  • 1
    \$\begingroup\$ How are you calling this function? What's min and max? Assuming max is the largest element in the array, the problem is you're considering the values, unlike most other sorting algorithms. So if the array has [12341231, 143] as input, you're doing some 12341231 more loops than a typical sort algorithm which would finish in about 4 iterations even if it was quadratic. Complexity for your approach would be non-polynomial. Beyond that, array.includes(array[i]) needlessly loops over the whole array, for every number from 0 to the max value, if things weren't bad enough. \$\endgroup\$
    – ggorlen
    Oct 11, 2021 at 23:08
  • 1
    \$\begingroup\$ newArray.splice(i, 1); also has O(n) time complexity, so even if you could toss out all of the "loop up to the max" business, this is still quadratic. Even with that simplification, given all the restrictions on the input, you're better off with any canonical sort like bubble sort. As wiith jfriend00, I'm confused about what/why. \$\endgroup\$
    – ggorlen
    Oct 11, 2021 at 23:16

1 Answer 1

2
\$\begingroup\$

I'll try to summarize what's been said in the comments into an answer and add my two cents to it.

First of all I suppose this was made because you had an idea on how to sort numbers and just tried implementing it to see how it'd work out. Nothing wrong with that, but as has been said said, sorting algorithms are very well researched and you'll always be better off using the build-in method or implementing someone else's algorithm if it satisfies some type of requirement (e.g. cycle sort. Not fast, but uses minimum writes). That doesn't mean you shouldn't mess around with sorting any more, as this could be a good way to learn about how they work and why.

As for the algorithm, it seems like your idea was the following:

  1. Create an array that fits every number
  2. Put the number where they belong, using their value as the index
  3. Remove all filler 0s

Now, the purpose of the min / max parameters is clear, they're used to limit the size of the step 1 array. As @ggorlen said, this information is usually not given to sorting algorithms. If this was needed you'd probably iterate over the input array and find them this way. This also prevents someone giving bogus values to the algorithm that result in an invalid output (ex: giving [1,2,3,4], 2, 2 as args yields [<1 empty value>, 1, 2]).

As for the complexity, it's at least O(n²). The oversimplified reason is that you're iterating over an entire array in O(n) and for every iteration you search or splice, which again is O(n), resulting in O(n²). However, since the loops don't iterate over n but over an array with the size max, your complexity can be WAY higher, as seen in @ggorlens comment about the [12341231, 143] case. This comment also answers the question of why this is outperformed by bubble sort; you're doing not one but two passes of bubble-sort complexity over an array that can be way larger than the one bubble sort has to manage.

To my knowledge, this hasn't been discovered, probably because it's neither as fast as the existing algorithms or as interesting as Bogosort, Stooge sort or Stalin sort.

As a final remark, Counting sort may be interesting to you.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the summary, I do know a fair bit about sorting algorithms and I'm currently trying to implement them in a language that doesn't have that many features as a challenge. I have looked at many sorting algorithms so far and was wondering if this one is a fast sorting algorithm because, in my mind, it had a complexity lower than anything I've implemented so far. Turns out I was wrong. \$\endgroup\$
    – gurkensaas
    Oct 12, 2021 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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