Sorting
Table of Contents
Concept Description
A sorting algorithm is used to re-order the elements of an array in either increasing or decreasing order. A comparison operator is used to determine the order between the two given elements
Any comparison based sorting algorithm has a running time complexity of $\mathsf{\Omega(nlogn)}$ .
Stablity
Stablity of a sorting algorithm determines, if the given algorithm-provided two (or more) objects with equal keys- is able to maintain the same relative sequence in the sorted output as they appear in the proided input.
Formally, Given an array A, an algorithm is stable if and only if, $\mathsf{i < j \; and \; A[i] == A[j] \; implies \; \pi(i) < \pi(j)}$ where $\mathsf{\pi(i)}$ is the sorting permutation.
Stable sorting algorithms include Bubble Sort, Insertion Sort, Merge Sort etc.
In Place Sorting
An in-place sorting algorithm uses constant extra space for sorting procedure, i.e., all the changes are made in the input array itself. For example, Insertion Sort and Selection Sort.
Time and Space Complexity for various sorting algorithms
| Algorithm | Time Complexity | Space Complexity | ||
|---|---|---|---|---|
| Best Case | Average Case | Worst Case | Worst Case | |
| Quick Sort | Ω (n log(n)) | Θ (n log(n)) | O (n2) | O (n log(n)) |
| Merge Sort | Ω (n log(n)) | Θ (n log(n)) | O (n log(n)) | O (n) |
| Timsort | Ω (n) | Θ (n log(n)) | O (n log(n)) | O (n) |
| Heapsort | Ω (n log(n)) | Θ (n log(n)) | O (n log(n)) | O (1) |
| Bubble Sort | Ω (n) | Θ (n2) | O (n2) | O (1) |
| Insertion Sort | Ω (n) | Θ (n2) | O (n2) | O (1) |
| Selection Sort | Ω (n2) | Θ (n2) | O (n2) | O (1) |
| Tree Sort | Ω (n log(n)) | Θ (n log(n)) | O (n2) | O (n) |
| Shell Sort | Ω (n log(n)) | Θ (n (log(n))2) | O ((n (log(n))2) | O (1) |
| Bucket Sort | Ω (n + k) | Θ (n + k) | O (n2) | O (n) |
| Radix Sort | Ω (n*k) | Θ (n*k) | O (n*k) | O (n + k) |
| Counting Sort | Ω (n + k) | Θ (n + k) | O (n + k) | O (k) |
| Cube Sort | Ω (n) | Θ (n log(n)) | O (n log(n)) | O (n) |
Programs
| S. No | Program Name | Implemented Languages |
|---|---|---|
| 1. | Merge Sort | Java, C++ |
| 2. | Quick Sort | Java, C++ |
| 3. | Insertion Sort | Java |
| 4. | Bubble Sort | Java |
| 5. | Selection Sort | Java |