Sorting Algorithm is the process of arranging the elements of an array so that they can be placed either in ascending or descending order.
Heap Sort
Heap sort is a comparison-based sorting technique based on the binary heap data structure. It is similar to the selection sort where we first find the minimum element and place the minimum element ad the beginning and repeat the same process for the remaining elements.
Quick Sort
Quick sort is also and divides and conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. This algorithm is used to quickly sort items within an array matter how big the array is.
Bubble Sort
Bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and word-case time complexities is quite high.
Selection sort
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning.
Merge sort
Merge sort is an algorithm that is considered an example of the divide and conquers strategy. So, the array is initially divided into two equal halves and then they are combined in a sorted manner.
Insertion sort
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Shell sort
Shell sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of ShellSort is to allow the exchange of far items. In Shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.
Time Complexities of all Sorting Algorithms
The time complexity of an algorithm describes the amount of time an algorithm takes to run in terms of the characteristics of the input.
| Sorting Algorithm | Time Complexity – Best | Time Complexity – Worst | Time Complexity – Average | Space Complexity |
|---|---|---|---|---|
| Bubble Sort | n | n2 | n2 | 1 |
| Selection Sort | n2 | n2 | n2 | 1 |
| Insertion Sort | n | n2 | n2 | 1 |
| Merge Sort | nlog n | nlog n | nlog n | n |
| Quicksort | nlog n | n2 | nlog n | log n |
| Counting Sort | n+k | n+k | n+k | max |
| Radix Sort | n+k | n+k | n+k | max |
| Bucket Sort | n+k | n2 | n | n+k |
| Heap Sort | nlog n | nlog n | nlog n | 1 |
| Shell Sort | nlog n | n2 | nlog n | 1 |
Big-O Complexity Chart