Sorting is one of the most common tasks done in programming needed for organising lists of items. Generally, sorting implies arranging items in an ascending order unless specified.
While there are a variety of sorting algorithms, they can be broadly classified into:
In this strategy, array elements are selected and compared against each other to sort them. This includes popular algorithms such as
- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge sort
- Heap Sort
- Quick Sort
These use a strategy of bucketing elements based on some conditions. Examples include,
- Radix Sort
- Counting Sort
- Bucket Sort
Other classifications for these sorting techniques are
- Inplace/Outplace Technique : If a sorting method requires extra memory (comparable to the number of elements in the source array), it is considered to be an Outplace Technique. If it uses no additional space or uses a small constant space, then its considered as a Inplace Technique.
|InPlace Technique||Outplace Technique|
|Bubble sort||Merge sort|
|Selection sort||Radix sort|
|Insertion sort||Counting sort|
|Heap sort||Bucket sort|
- Online/Offline Technique : This describes the ability of a sorting strategy to handle addition of items to the array while the sorting procedure is going on. An offline sorting technique needs all the data upfront, and cannot accept data while its in progress. It will add the new data only after its done sorting its current dataset. Online Technique evaluates incoming data and re-”sorts” its data as frequently as needed and maintains a sorted set at any given point. This technique is very useful for streaming data.
|Offline Technique||Online Technique|
|Bubble sort||Insertion sort|
|Selection sort||Heap sort|
|and many more..|
- Stable/Unstable Algortihms : A cursory glance of this sorting techniques would not be immediately obvious for primitive values like numbers, or characters. However if you are sorting an array of objects, based on the value of one of their properties, the order of items in which they appear in the original array could potentially be important. Stable algorithms ensure that duplicate items upon sorting, appear in the order they appeared in the source array. With Unstable algorithms, it is difficult to predict the order without additional work.
|Stable Technique||Unstable Technique|
|Insertion sort||Quick sort|
|Bubble sort||Heap sort|