Index
- Time Complexities
- Selection sort
- Bubble sort
- Insertion sort
- Quick Sort sort
- Merge Sort sort
- Heap sort
Time-Complexity of Sorting-Algorithms
| ALGORITHM | WORST-case Time Complexity(Big O Notation) | AVERAGE-case time complexity (Theta Notation) | BEST-case time-complexity (Omega Notation) |
|---|---|---|---|
| Selection sorting | O(n^2) | θ(n^2) | Ω(n^2) |
| Bubble sorting | O(n^2) | θ(n^2) | Ω(n) |
| Insertion sorting | O(n^2) | θ(n^2) | Ω(n) |
| Heap sorting | O(nlog(n)) | θ | Ω |
| Quick sorting | O(n^2) | θ | Ω |
| Merge sorting | O(nlog(n)) | θ | Ω |
| Bucket sorting | O(n^2) | θ | Ω |
| Radix sorting | O(nk) | θ | Ω |
| Tree-sort | O(nlog(n)) |
Working of Sorting Algorithms
Usage : Selection vs Insertion vs Bubble sort
- Selection Sort is best when memory write operations are costly since it makes the minimum possible number of swaps compared to other two.
- Insertion Sort is preferable for small or nearly sorted data.
- Bubble Sort is typically used for educational purposes to demonstrate sorting techniques but is rarely used in practical applications due to its inefficiency.
Selection Sorting
Algorithm :
- Iterate through the array to find the smallest (or largest) element.
- Swap the found minimum (or maximum) element with the first element.
- Move the boundary of the unsorted subarray by one element.
- Repeat the process for the remaining unsorted portion of the array.
private static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
//optimisation used : outer loop used for swapping - internal for index tracking
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
- Time Complexity: O(n²)
- Space Complexity: O(1) (In-place sorting)
Bubble Sort
Algorithm :
- Compare adjacent elements in the array.
- Swap them if they are in the wrong order.
- Continue doing this for each pair of adjacent elements until the array is fully sorted
- .After each pass, the next largest element is in its correct position.
- Repeat the process until no swaps are needed (the array is sorted).
private static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1; j++) {
if(arr[j]>arr[j+1]){
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
- Time Complexity: O(n²)
- Space Complexity: O(1) (In-place sorting)
Insertion Sort
Algorithm :
- Start from the second element, assume that the first element is already sorted.
- Pick the next element and compare it with the elements in the sorted part.
- Shift all elements in the sorted part that are greater than the current element to the right.
- Insert the current element into its correct position.
- Repeat the process until the entire array is sorted.
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1] that are greater than key to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
- Time Complexity: O(n²)
- Space Complexity: O(1) (In-place sorting)
Quick Sort
Algorithm :
- Choose a “pivot” element from the array.
- Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
- Recursively apply the same steps to the sub-arrays.
- Combine the sub-arrays to get the sorted array.
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Recursively sort elements before partition
quickSort(arr, pi + 1, high); // Recursively sort elements after partition
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1); // Index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
- Time Complexity:
- Best Case: O(n log n)
- Worst Case: O(n²) (occurs when the smallest or largest element is always chosen as the pivot)
- Space Complexity: O(log n) (in-place sorting, though recursion stack takes
Merge Sort
Algorithm :
- Divide the array into two halves.
- Recursively sort each half.
- Merge the two halves to create a sorted array.
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
// Sort first and second halves
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
// Merge the sorted halves
merge(arr, left, middle, right);
}
}
private static void merge(int[] arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
// Temporary arrays
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data to temp arrays
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[middle + 1 + j];
// Merge the temp arrays
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements of L[]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[]
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
// Call mergeSort with the full range of the array
mergeSort(arr, 0, arr.length - 1);
// Print the sorted array
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
Heap sort
Algorithm :
Techglot 