Are you the one who is just fed up learning all these different sorting algorithms? Are you the one who wants to explore what is the need of all these algorithms? Hmm… I mean why don’t we have just one and only one algorithm to use for sorting everywhere. Wanna explore? Keep reading. Aah! So, you already know that we have a lot of different and complex sorting algorithms in this world. Some people say that “quicksort” is the best, other say “mergesort” is the best, different people can give their opinions on this but what’s the truth?
I would say neither “quick” nor “merge” sort is the best and not even any other can be titled as the best algorithm. Why? Because if anyone among the bunch of algorithms would have been the best, all the people out there would have been using that one, right? But as you know that’s not the fact!
So, How can we determine the efficiency of sorting algorithms? Following terms of sorting algorithms can be useful to understand.
1) Data sensitivity: How sensitive a sorting algorithm is with respect to change in data. e.i from completely unsorted to partly sorted.
2) Stability: A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc.
3) Memory: How much and what type of memory requirement a particular sorting algorithm will consume. Depending on this factor we have two types of algorithms like (i) In-Place (ii) Not-In-Place
i.e:- an in-place algorithm is an algorithm which transforms input using no extra data structure. Although, a small amount of extra space is used for variables. In-place algorithm updates input sequence only through replacement or swapping of elements. That’s why the input is usually overwritten by the output as the algorithm succeed further. An algorithm which is not in-place is called not-in-place or out-of-place.
4)Time: How much time consuming an algorithm is. It is usually deal in 3 categories these are:
(i) Best case: denoted by “big-omega”
(ii) Average case: denoted by “theta”
(iii) Worst case: denoted by “big-O” (popularly known as big O notation)
Time complexities of different sorting algorithms are available here.
No single sorting algorithm can be termed as the best. Which sorting algorithm should be selected it is totally data dependent. On a particular data, we may check the above features of sorting algorithms. On the basis of a study, the following table is derived.
For furthermore visit her: Criteria for choosing a sorting algorithm
|Only a few items||Insertion Sort|
|Items are mostly sorted already||Insertion Sort|
|Concerned about worst-case scenarios||Heap Sort|
|Interested in a good average-case result||Quicksort|
|Items are drawn from a dense universe||Bucket Sort|
|Desire to write as little code as possible||Insertion Sort|
Alright with this we have reached the end of this post. Please give suggestions in the comment section below on how can I improve this post. See you on the next post till then this, is GeekyShacklebolt
bidding you goodbye!