Classification of sorting algorithms

Sorting Algorithm and it’s classifications

In this module we are going to learn Classification of Sorting algorithms, their use cases, conditions, comparisons etc.

Stable Vs Unstable Sorting

Stable sort sorts the identical elements in their same order as they appear in the input.
Examples: Bubble sort, Insertion sort, Merge Sort, Counting sort

In unstable sort, order of identical elements is not guranteed to stay in the same order as they appeared in the input. Examples: Quick Sort, Heap Sort, Selection sort

• Stability is not an issue when equal elements are indistinguishable such as with integers.
• Any given sorting algorithm which is not stable can be modified to stable.
• Generally, unstable sorting is faster than stable sorting.
• We need a stable sort to sort the cards by their numbers and suit.

Internal Vs External Sort

Internal sorting is that which takes place entirely within the main memory of computer. It comes into role when the dataset is small.

External sorting is that which can handle massive amount of data at a time. Data reside in hard disk in case of external sorting.

Comparison based Sorting  and Counting based Sorting

In Comparison based sorting, a comparator is required to compare numbers or items. This comparator defines the ordering to arrange the elements.
Examples: Merge Sort, Quick Sort, Heap Sort

Counting based sorting is the algorithm that perform the sorting without comparing the elements rather by making certain assumption about the data they are going to sort.

In-Place and Not-In-Place Sorting

In-Place Sorting means to sort the array by modifying the element order directly within the array.

• No auxiliary data structure is used.
• There can be only constant amount of extra space usually less than log(n). So this algorithm is space efficient.

Examples: Bubble Sort, Selection Sort, Insertion Sort, Heap Sort

Not-In-Place Sorting is that which uses auxiliary data structure to sort the array.
Examples: Merge Sort ( It requires additional O(n) space to perform the merge operation), Quick Sort

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others