DEV Community 👩‍💻👨‍💻

Pan Chasinga
Pan Chasinga

Posted on

What each sorting algorithm is good for

Anyone who has been through a CS school or into learning sorting algorithms should be well aware that today's most accepted algorithm is quicksort, since it boasts an average case of O(n log n) run times. Some algorithms with much less efficiency, such as insertion sort, which incurs on average O(n * n) time might be less favorable. However, there are many edge cases in which each may surprisingly shine brighter than the others.

Quicksort

The go-to sorting algorithm, quicksort's efficiency relies on two factors--its pivot or partitioned element and the entropy of the source array. If the array is partially or substantially sorted, and/or the pivot element is chosen in a way that it is closer to the start or end of the array, it can easily degrade to O(n * n).

Insertion Sort

Although insertion sort seems slow, when used on a small array of data, is quite efficient. Its O(n * n) quadratic run time can upgrade to a respectable O(n * k), where k is the steps it needs to tread back up the array to swap the previous element with the current one. Also, if the array is partially or already substantially sorted, insertion sort will shine even brighter than quick sort, which will perform quite poorly in such case. The reason being the mentioned k is very little because it does not need to go back up the array often.

Selection Sort

A pretty simple algorithm with a pretty neat O(1) constant space complexity. Although its run time is quadratic, it has a magical property of retaining the first N-sorted elements when run N times on an array. What does this mean? It means that if your sorted data is to be paginated and ordered i.e. search results, you only need to run selection sort algorithm that many times. Once you need the next set of results, you can resume where you left off and so on.

Top comments (5)

Collapse
 
nssimeonov profile image
Templar++

Bubble Sort - not good for anything, but demonstrating a terrible algorithm...

Collapse
 
kgashok profile image
kgashok • Edited on

Hybrid sorts like the TIMsort, a combination of InsertSort and MergeSort, is the way sorting happens in Python. Interestingly, Java 7 uses a Dual-Pivot Quicksort for primitives, TimSort for objects, and MergeSort for Object arrays and collections.

To know all about TIMsort, read dev.to/s_awdesh/timsort-fastest-so...

Collapse
 
pancy profile image
Pan Chasinga

Very interesting, thank you!

Collapse
 
amazing_leader profile image
Amazing Leader

Great write up. I am currently relearning sort and search algorithms to get started applying for jobs at companies I really want to work for.

Collapse
 
pancy profile image
Pan Chasinga

Thanks for the comment!

Let's team up together 🤝

We're Hiring

We're hiring for a Senior Full Stack Engineer to join the DEV team. Want the deets? Head here to learn more about who we're looking for.