0
$\begingroup$

Is there some kind of "universal list" of performance of different algorithms in different situations?

I have different databases that save user input (numbers). However some of these sets of numbers are small and some of them are really big (such as the common one). There are negative numbers included.

I remember from when I took algorithms as a course that there are things such as "big-oh notation" and "theta notation", etc. What I am looking for is some way of looking up which algorithm I should use for different un-ordered lists of numbers.

I know that merge sort has the best over all performance with a worst-case time of $n \log n$ however I also know that both insertion sort and quick sort (worst-case $n^2$) sorts better with fewer elements in the given list. There are a few cases of lists being in reverse sort, where can I look up what is the most effective then?

How do I know which of insertion sort or quick sort I should use then?

What is "a small list of numbers that is quicker to sort with quick sort/insertion sort"?

$\endgroup$
11
  • $\begingroup$ Not answering your question, but by “databases” do you mean SQL databases? In this case, simply use the standard sorting, it’s likely to do it better than what you can possibly implement. $\endgroup$
    – user114966
    Feb 23, 2021 at 11:08
  • $\begingroup$ @Dmitry I have created these databases myself in C. $\endgroup$
    – linker
    Feb 23, 2021 at 11:21
  • $\begingroup$ Then you might need to experiment yourself. There isn't an "off the shelf" best algorithm, since we can usually only describe its running time in big-O and not the actual time it would run. But basically, try to implement all of them and check which one runs faster (or use the standard sorting instead, its the better option) $\endgroup$
    – nir shahar
    Feb 23, 2021 at 11:33
  • $\begingroup$ @nirshahar it takes a long time, I would guess that since algorithms are something that is widely used that there might be some simple condensed theory or some graph out there. How does negative numbers affect the algorithms? I cannot find a source for this. $\endgroup$
    – linker
    Feb 23, 2021 at 12:23
  • 1
    $\begingroup$ Sadly, there isn't a theory for the actual running time of algorithms, since there are too many factors to consider (the code, the compiler, the cpu, storage, etc). This is why we use big-O instead. However there are algorithms that usually are faster in practice than others. I dont really know the difference between them, but I think that mergesort is one of them. Try to find other algorithms and see if they suit your needs $\endgroup$
    – nir shahar
    Feb 23, 2021 at 12:27

2 Answers 2

1
$\begingroup$

There is a comparison of sorting algorithms on wikipedia which provides most of the information you're looking for, including separate tables for non-comparison based sorts (distribution, radix, etc).

The short answer this question usually gets is "use whatever built-in library you have". This is obviously frustrating because that's a practical answer to an abstract question. It's often phrased as "you shouldn't be worrying about this" yet this is something taught in every introduction to programming and tutorial site, with drastically fewer explanations of what standard library sorting algorithms do. So it shouldn't be surprising that the question is so common. In short, the built-in sorts usually are adaptive, so they use different algorithms depending on the data structure that way you're usually getting the best of all options.

There are lots of websites, animations and videos that visualize sorting algorithms. This tool has 75 different sorts built in as well as different input data like almost-sorted, reversed, duplicates. It's used to make lots of videos. Those can answer a lot of questions quickly just by visualizing the abstract concept of big O.

To answer one of your specific questions, negative numbers should generally be handled with no issue by any sorting algorithm unless its extremely specialized. Most sorts you read about are comparison based so they don't care if you're comparing (-∞ <= 2) or (red <= blue) as long as it can get a valid result out of the comparison.

For the more specific questions you mentioned, I've also wondered about those cases and considered making a big table just as an exercise to cement what I've learned and maybe satisfy someone else's curiosity. However once you start seriously considering publishing something like that you realize it's very difficult to choose a good "reference frame" (what test cases on what hardware) that won't give beginners the wrong idea or get a million corrections from people. It's a somewhat lose/lose scenario so I understand a bit more why people don't do it. (And I'm even more grateful to the people on Wikipedia and elsewhere who do).

The last thing I'll say is that another reason you'll be told to just use the built in sort is that it's very common to pre-optimize code, which can lead to more problems down the line. It's rare that you'll need to write your own sorting algorithm, but it can happen.

$\endgroup$
0
$\begingroup$

In practice you call a method or function provided by your computer’s operating system or your languages standard library.

The algorithm used is likely a mixture of different algorithms and designed to minimise average runtime - with “average” meaning the average over arrays that users actually try to sort. Methods that help us looking for a sorted sequence at the start and end of the array which can let you combine two sorted arrays and sort the result in O(n), checking for an array that is sorted with few changes (if you start with an array of n items and change k of them, you can sort the result in O(n + k log k)), possibly checking for small arrays.

Usually sorting will be comparison based, because that allows for a consistent interface.

Plus there is the possibility of partially sorting: You may want to display an array in sorted order, but then you only need to sort the part that is being displayed; quicksort can do that nicely.

$\endgroup$
1
  • $\begingroup$ to add onto this, timsort works by combining merge sort and insertion sort. The general idea is that for smaller arrays, insertion sort works faster as compared to merge sort and timsort takes advantage of this, of course with other implementation specific ideas too. $\endgroup$
    – Rinkesh P
    Apr 6 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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