A sorting algorithm is used to arrange elements of an array/list in a specific order. For example,
Here, we are sorting the array in ascending order.
There are various sorting algorithms that can be used to complete this operation. And, we can use any algorithm based on the requirement.
Different Sorting Algorithms
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quicksort
- Counting Sort
- Radix Sort
- Bucket Sort
- Heap Sort
- Shell Sort
Complexity of Sorting Algorithms
The efficiency of any sorting algorithm is determined by the time complexity and space complexity of the algorithm.
1. Time Complexity: Time complexity refers to the time taken by an algorithm to complete its execution with respect to the size of the input. It can be represented in different forms:
2. Space Complexity: Space complexity refers to the total amount of memory used by the algorithm for a complete execution. It includes both the auxiliary memory and the input.
The auxiliary memory is the additional space occupied by the algorithm apart from the input data. Usually, auxiliary memory is considered for calculating the space complexity of an algorithm.
Let's see a complexity analysis of different sorting algorithms.
| 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 |
Stability of Sorting Algorithm
A sorting algorithm is considered stable if the two or more items with the same value maintain the same relative positions even after sorting.
For example, in the image below, there are two items with the same value 3. An unstable sorting algorithm allows two possibilities where the two positions of 3 may or may not be maintained.
However, after a stable sorting algorithm, there is always one possibility where the positions are maintained as in the original array.
Here's a table showing the stablilty of different sorting algorithm.
| Sorting Algorithm | Stability |
|---|---|
| Bubble Sort | Yes |
| Selection Sort | No |
| Insertion Sort | Yes |
| Merge Sort | Yes |
| Quicksort | No |
| Counting Sort | Yes |
| Radix Sort | Yes |
| Bucket Sort | Yes |
| Heap Sort | No |
| Shell Sort | No |