Need Of Different Sorting Techniques.

 

Why are there so many sorting techniques?

Hi guys!
Are you the one who is just fed up learning all these different sorting techniques? Are you the one who wants to explore what is the need of all these techniques? I mean why don’t we have just one and only one technique to use for sorting everywhere. if you guys want to explore more about sorting techniques then keep reading. 

What is Sorting ?

First of all lets understand what is Sorting. Sorting refers to the operation or technique of arranging and rearranging sets of data in some specific order. A collection of records called a list where every record has one or more fields. The fields which contain a unique value for each record is termed as the key field. For example, a phone number directory can be thought of as a list where each record has three fields - 'name' of the person, 'address' of that person, and their 'phone numbers'. Being unique phone number can work as a key to locate any record in the list. Sorting is the operation performed to arrange the records of a table or list in some order according to some specific ordering criterion. Sorting is performed according to some key value of each record. The records are either sorted either numerically or alphanumerically. The records are then arranged in ascending or descending order depending on the numerical value of the key. Here is an example, where the sorting of a lists of marks obtained by a student in any particular subject of a class.

Categories in Sorting :

The techniques of sorting can be divided into two categories. These are:

• Internal Sorting
• External Sorting

Internal Sorting : If all the data that is to be sorted can be adjusted at a time in the main memory, the internal sorting method is being performed.

External Sorting : When the data that is to be sorted cannot be accommodated in the memory at the same time and some has to be kept in auxiliary memory such as hard disk, floppy disk, magnetic tapes etc. then external sorting methods are performed.

Types of Sorting Techniques :

• Selection Sort
• Bubble Sort
• Recursive Bubble Sort
• Insertion Sort
• Recursive Insertion Sort
• Merge Sort
• Iterative Merge Sort
• Quick Sort
• Iterative Quick Sort
• Heap Sort
• Counting Sort
• Radix Sort

So, you already know that we have a lot of different and complex sorting techniques 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 we want to know is fact not anyone's opinion.

And the fact is neither “quick” nor “merge” sort is the best and not even any other can be titled as the best technique. Because if anyone among the bunch of techniques available would have been the best, all the people around the world would have been using that one. But as you know that’s not the fact!

Now the question that arises is which sorting technique is the best for us individually..?? Well that depends on the efficiency of the Sorting Technique that we choose. 

Efficiency Of Sorting Techniques :

Now to determine the efficiency of a sorting technique following terms can be useful to understand.

1) Data sensitivity: How sensitive a sorting technique is with respect to change in data. i.e. from completely unsorted to partly sorted.

2) Stability: A sorting technique 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 techniques 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 technique will consume. Depending on this factor we have two types of techniques like : (i) In-Place (ii) Not-In-Place

(an in-place technique is an technique which transforms input using no extra data structure. Although, a small amount of extra space is used for variables. In-place technique updates input sequence only through replacement or swapping of elements. That’s why the input is usually overwritten by the output as the technique succeed further. An technique which is not in-place is called not-in-place or out-of-place.)

4)Time: How much time consuming an technique 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)

Now to get a clear idea about which Sorting technique will be the best for you. The following Table will give you a brief synopsis. 

Criteria	Sorting Technique
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

Conclusion:
No single sorting technique can be termed as the best. Which sorting technique should be selected it is totally data dependent. On a particular data, we may check the above features of sorting techniques. On the basis of a study, the following table is derived.

Alright with this we have reached the end of this blog. Please give suggestions in the comment section below on how can we improve this blog. 

Thank You !!

***

Project : Advanced Data Structures (Home Assignment)

Division : IT - A     Group : 11

Members :

55_Ubed Shaikh

06_Prajwal Atram

27_Prathamesh Londhe

37_Omkar Nimase

32_Dhiraj Mukane