Video courses for company/skill based Preparation
Purchase mock tests for company/skill building
Classification of Sorting Algorithms
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.
Examples: Counting sort, Radix 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