eli5 what’s the point of having so many sorting algorithms if the primary objective is to sort, i mean why can’t we just use one algorithm for all
In: 6
Sorting algorithms have strengths and weaknesses: memory usage, number of comparisons, varying performance in edge cases, multithreading capability, ease of implementation, etc. This means that there is usually some algorithm or a variation of one that fits your specific use case and available resources better than most or all other algorithms. An algorithm that performs marginally better than another can save minutes, hours, or days of data processing on ginormous amounts of data.
For sorting, there are three major characteristics and a few secondary ones that are of interest. Different algorithms have differing values for those characteristics that may adjust their suitability for a given application.
The major characteristics are:
* Average and Worst case run-time. The best possible worst case, according to known mathematics, is O(N ln N)*, meaning the run time is based on the number of items in the list times the log of the number of items in the list.
* Memory usage. Some algorithms sort in place, and take only a constant amount of memory, while others need to copy chunks of the data to sort. If memory is tight, a O(1) (constant) amount of memory usage is preferable to one that has to use enough memory to hold an entire temporary copy of the data.
* Stability. If two items are equal, what order are they put in? A stable sort will maintain the order in original data, while non-stable sorts may have an effectively random result order. While this does not matter for simple data like numbers, it may if you are sorting people by name or any other set. Some applications may require a stable sort, while many do not. An unstable sort can always be made stable by using extra memory and time to record the original order and include that in the compare, but that may not be ideal.
Secondary characteristics include:
* Best case run-time.
* How long does the algorithm take if the data is already sorted. Checking for already sorted takes more time, so an algorithm known to handle it innately can be useful if your data is likely already sorted.
* Similarly, how about data nearly sorted or in other clear patterns such as reversed? These can be much more important, as its not uncommon to need to guarantee data is sorted, knowing that you likely only added or changed a few items from the last check.
* Performance with short data. Practically, a lot of data is small, and more complicated algorithms that might meet the other needs are often slower to startup but faster for large data. Basically, there is some size of data where a simple algorithm is faster than a “better” one.
* Code size. While generally not super important for most applications, sometimes keeping the code tiny, and generally simple, is a huge benefit.
* Is it an online sort? If you constantly have new data coming in that you need to maintain sorted, some algorithms exist to do so more efficiently than collecting all the data and sorting it. These are especially useful if you have a large chunk of initial data and new data coming in live.
Practically, only a few of the general purpose algorithms are commonly used, with most of the others being more specialized in nature.
* To be complete, there are some types of data that can be sorted faster, such as Radix Sort for integers, but no general purpose solutions. When working with large data sets of these types, using one of these specialized algorithms is generally more efficient, though their specialized nature makes them harder to use.
A bonus consideration to all of this is that writing and explaining sorting algorithms can be fun and educational! It’s a simple task with a clear goal, and the activity of the algorithm is easy to visualize. Students learn a lot of sorting algorithms both because e.g. bubble sort is an easy coding project for a beginner *and* because contrasting it with quicksort is a good way of teaching complexity/efficiency. When those students grow up to be coders, they probably won’t be thinking hard about what sorting algorithm to use, but they may apply the principles of those algorithms to new tasks.
Also, bogosort and stooge sort are just funny. Everyone loves a clumsy robot.
A bonus consideration to all of this is that writing and explaining sorting algorithms can be fun and educational! It’s a simple task with a clear goal, and the activity of the algorithm is easy to visualize. Students learn a lot of sorting algorithms both because e.g. bubble sort is an easy coding project for a beginner *and* because contrasting it with quicksort is a good way of teaching complexity/efficiency. When those students grow up to be coders, they probably won’t be thinking hard about what sorting algorithm to use, but they may apply the principles of those algorithms to new tasks.
Also, bogosort and stooge sort are just funny. Everyone loves a clumsy robot.
Latest Answers