Top 5 Sorting Algorithms, built-in function in programming languages which sorting internally used? When to use which sorting technique?
Find out which is the best sorting algorithm. Understand how to use the different types of sorting algorithms with simple examples.
Sorting means putting items in a particular order(ascending or descending).
Why Study Sorting?
A quick Google search reveals that there are over 40 different sorting algorithms used in the computing world today.
Well, you will be astonished when you realize just how useful sorting algorithms are in real life. Some of the best examples of real-world implementation of the same are —
- Bubble sorting is used in programming TV to sort channels based on audience viewing time!
- Sports scores are quickly organized by Quick sort algorithm in real-time!
- Databases use external Merge sort to sort sets of data that are too large to be loaded entirely into memory!
- A9 Algorithm is a sorting algorithm used by Amazon to decide how products are ranked in search results!
- PageRank is a search algorithm used by google to measuring the importance of website pages!
Types of Sorting in Data Structures
- Comparison-based sorting: In comparison-based sorting techniques, a comparator is defined to compare elements or items of a data sample. This comparator defines the ordering of elements. Examples are: Bubble Sort, Merge Sort.
- Counting-based sorting: There’s no comparison involved between elements in these types of sorting algorithms but rather work on calculated assumptions during execution. Examples are Counting Sort, Radix Sort.
- In-Place vs Not-in-Place Sorting: In-place sorting techniques in data structures modify the ordering of array elements within the original array. ‘In place’ means whenever you are sorting and you don’t require any extra space except the input space excluding the constant space which is used for variables or iterators. It also doesn’t include the space used for stack in the recursive algorithms. On the other hand, Not-in-Place sorting techniques use an auxiliary data structure to sort the original array. Examples of In-place sorting techniques are Bubble Sort, Selection Sort, Quick Sort. Some examples of Not in Place sorting algorithms are: Merge Sort.
Stable and Not stable Sorting:-
- A sorting algorithm when two objects with equal keys appear in the same order in the sorted output as they appear in the unsorted input.
- Whereas a sorting algorithm is called as an unstable sorting if there are two or more objects with equal keys which don’t appear in the same order before and after sorting.
Adaptive and Non–Adaptive Sorting Algorithm:-
When the occurrence of the elements to be sorted of an input array matters the time complexity of a sorting algorithm, then that algorithm is called “Adaptive” sorting algorithm.
For example, Insertion sort is an adaptive sorting algorithm like in the case if the input is already sorted then we know that time complexity will be O(n). That’s why If the input array is almost sorted then choose insertion sort, though this is not the only thing to be kept in mind for Insertion sort over other sorting algorithms.
Merge Sort is a “Non-Adaptive” Sorting algorithm because the order of the elements in the array doesn’t matter So the time complexity of the algorithm will always be O(nlogn).
Adaptive sorting algorithms:
- Bubble Sort
- Insertion Sort
- Quick Sort
Non-adaptive sorting algorithms:
- Selection Sort
- Merge Sort
- Heap Sort
Sorting Algorithms:
1. Bubble Sort
Simplest sorting algorithm. Iterates over the list, in each iteration it compares elements in pairs and keeps swapping them such that the larger element is moved towards the end of the list.
Implementation
Void bubbleSort(int arr[], int n){//outer loop for iterating to n-1 elements for( int i= 0; i< n-1; i++){ //inner loop for checking each element
for( int j = 0; j < n-i-1; j++){
if (arr[ j ] > arr[ j+1 ]{ // For swapping if previous element is greater than next one swap( arr[ j ], arr[ j+1 ]);
}
}
}
}
Non-recursive
Stable
In place
O(n²)
Use Cases
- It is used to introduce the concept of a sorting algorithm to Computer Science students.
- In computer graphics, bubble sorting is quite popular when it comes to detecting a very small error (like swapping of just two elements) in almost-sorted arrays.
2. Selection Sort
Selection sort is a sorting algorithm in which the given array is divided into two subarrays, the sorted left section, and the unsorted right section.
Implementation
Void SelectionSort(int arr[ ], int n){
int i, j, minIndex;
for(i=0; i<n-1; i++){
minIndex=i; //index of minimum element
for(j=i+1; j<n; j++){
if(arr[ j ] < arr[ minIndex ]){
minIndex=j; //update the min element
swap(arr[ minIndex ], arr[ i ]); //Swapping
}
}
}
}Non recursive
Unstable
In place
O(n²)
Use Cases
- It is used when the size of a list is small. (Time complexity of selection sort is O(N²) which makes it inefficient for a large list.)
- It is also used when memory space is limited because it makes the minimum possible number of swaps during sorting.
3. Insertion Sort
Insertion sort is a sorting algorithm in which the given array is divided into a sorted and an unsorted section. Then we iterate over the unsorted section and insert the element from this section into the correct position in the sorted section.
Implementation
Void insertionSort(int arr[ ], int n){
int i, temp, j;
for(i=1; i<n; i++) {
temp=arr[ i ];
//Will store the value in a temporary variable j= i-1;//check the which value is greater
While(j>=0 and arr[ j ] > temp){
arr[ j+1] = arr[ j ];
j--;
}
arr[ j+1 ] = temp; //Replace that value with the temporary variable
}
}
Non-recursive
Stable
In place
O(n²)
Use Cases
- This algorithm is stable and is quite fast when the list is nearly sorted.
- It is very efficient when it comes to sorting very small lists (for example say 40 elements.)
4. Quick Sort
Quick sort is a divide and conquer algorithm. It is based on partition. It is also known as partition exchange sorting.
The intuitive idea behind quick sort is it picks an element as the pivot from a given array of elements and then partitions the array around the pivot element. Subsequently, it calls itself recursively and partitions the two subarrays thereafter.
Implementation
Void quicksort( int arr[],int low,int high){
If (low < high) {
Int pivot_index = partition(arr, low, high);
//Partition on basis of starting and end index for getting pivotquicksort(arr, low, pivot_index-1);
quicksort(arr, pivot_index+1, high);//Recursively Sort into two parts
}
}private static int partition(int[] array, int low, int high) {
int left, right, pivot_item = array[low];
left = low;
right = high;
while (left < right) {
while (array[left] <= pivot_item)
left++;
while (array[right] > pivot_item)
right--;
if (left < right) {
swap(array, left, right);
}
}
// array[low] = array[right];
// array[right] = pivot_item;
swap(array, right,low);
return right;
}
private static void swap(int[] array, int left, int right) {
int temp;
temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
Recursive
In place
Unstable
O(nlogn)
The logical steps involved in the Quick Sort algorithm are as follows:
- Pivot selection: Picks an element as the pivot (here, we choose the last element as the pivot)
- Partitioning: The array is partitioned in a fashion such that all elements less than the pivot are in the left subarray while all elements strictly greater than the pivot element are stored in the right subarray.
- Recursive call to Quicksort: Quicksort function is invoked again for the two subarrays created above and steps are repeated.
Use Cases
- Quicksort is probably more effective for datasets that fit in memory.
- Quick Sort is appropriate for arrays since is an in-place sorting algorithm (i.e. it doesn’t require any extra storage)
What is the worst case of quick sort?
That condition happed when a list or array of elements are already sorted. In that case, pivot will be :
- pivot : array(low+high)/2.
- pivot: random(low,high).
- In that case, quicksort time complexity should be O(n2) and space complexity should be O(n) due to recursive stack.
5. Merge Sort
This is a divide and conquer algorithm. In this algorithm, we split a list in half and keeps splitting the list by 2 until it only has a single element.
Implementation
public static void mergeSort(int input[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(input, left, mid);
mergeSort(input, mid + 1, right);
merge1(input, left, mid, right);
}
}
static void merge1(int a[], int l, int mid, int r) {
int b[] = new int[a.length];
int i = l;
int j = mid + 1;
int k = l;
while (i <= mid && j <= r) {
if (a[i] < a[j]) {
b[k] = a[i];
i++;
} else {
b[k] = a[j];
j++;
}
k++;
}
if (i > mid) {
while (j <= r) {
b[k] = a[j];
// b[k++] = a[j++];
k++;
j++;
}
} else {
while (i <= mid) {
b[k] = a[i];
k++;
i++;
}
}
for (k = l; k <= r; k++) {
a[k] = b[k];
}
}Recursive
Stable
Needs extra space
O(nlogn)
Use Cases
- Merge sort is quite fast in the case of linked lists.
- It is widely used for external sorting where random access can be quite expensive compared to sequential access.
Although there is no. of sorting algorithms mostly used are discussed above and others are also important which is used in advanced Data Structure such as-Heap Sort
- Counting Sort
- Bucket Sort
- Radix Sort
- Shell Sort
- Comb Sort
- Cycle Sort
- Bitonic Sort
- Tree Sort
- Stooge Sort
Built-in function in programming languages which sorting internally used?
C++ sort function(STL) is based on IntroSort(hybrid algorithm of quick Sort and heap Sort) and many more.
Java sorting function is based on Quicksort.
Python sorting function is based on TimSort(hybrid algorithm of mergeSort and insertion Sort.
- The various JavaScript engines implement this method using different sort algorithms: V8: Quicksort or Insertion Sort (for smaller arrays) Firefox: Merge sort.
Arrays.sort() uses mainly Quicksort, internally and used for primitive arrays dual-pivot with O(n log(n)) performance. Also Arrays.sort() is a sequential sorting while Arrays.ParallelSort() is a parallel sorting.
Collections.sort() uses Mergesort internally used for compare arrays of objects, mostly sorted arrays.
Hybrid algorithm of mergeSort and insertion Sort -> TimSort is faster than merge sort but still slower than quick sort . Working of Tim sort — First sort small pieces using Insertion Sort, then merges the pieces using merge of merge sort
- Radix sorting finds applications in parallel computing. It is also used in the DC3 algorithm (Kärkkäinen-Sanders-Burkhardt) while making a suffix array.
- Bucket sorting is used when input is uniformly distributed over a range. It is also used for floating-point values.
- Comb Sort eliminates small values at the end of the list by using larger gaps. It is a significant improvement over Bubble Sort.
- Insertion sort does not perform well when the close elements are far apart. Shell sort helps reduce the distance between close elements. It is also used when recursion exceeds a limit. The bzip2 compressor compresses it.
If you’re curious as to how these algorithms actually work, don’t forget to visit this link.
When to use which sorting technique?
Q: Is the occurrence of the same element important?
Yes: Insertion, Bubble, Merge, Quick
No: Heap, Quick
Q: Is the data size small?
Yes: Insertion, Bubble
No: Heap, Merge, Quick
Q: Is memory for extra space an issue?
Yes: Insertion, Bubble, Heap
No: Merge, Quick*
Q: Is the input data nearly sorted?
Yes: Insertion, Bubble
No: Heap, Merge, Quick
Q: Is speed important?
Yes: Heap, Merge, Quick
No: Insertion, Bubble
