5 Sorting Algorithms - Concise
Selection, Bubble, Insertion, Merge, and Quick Sort
I share my learnings here. Thanks for reading.
Selection Sort
Select the minimums and swap it
Minimum at the front
Algorithm
Step 1 - Swap index 0 and minimum index in the range [0,n-1]
Step 2 - Swap index 1 and minimum index in the range [1,n-1]
Step 3 - Swap index 2 and minimum index in the range [2,n-1]
....
Step n-1 - Swap index n-2 and minimum index in the range [n-2,n-1]
Time Complexity - O(n^2)
Code
public class SelectionSort {
public static void main(String[] args) {
int a[] = new int[]{13,46,24,52,20,9};
for (int i=0; i<a.length-1; i++){
int minIndex = i;
for (int j=i; j<a.length;j++){
if (a[j]<a[minIndex]) minIndex = j;
}
swap(a,i,minIndex);
}
}
public static void swap(int a[], int i, int j){
int temp = a[i];
a[i]=a[j];
a[j]=temp;
}
}
Bubble Sort
Pushes the maximum to the last by adjacent swaps
Algorithm
Adjacent Swaps - Traverse the array and swap the current element with the previous one if it is greater than the current.
Step 1 - Adjacent swaps in the range [0,n-1]
Step 2 - Adjacent swaps in the range [0,n-2]
Step 3 - Adjacent swaps in the range [0, n-3]
...
Step n-2 - Adjacent swaps in the range [0,1]
Time Complexity
Worst Case - O(n^2)
Best Case - O(n)
public class BubbleSort{
public static void main(String[] args) {
int a[] = new int[]{13,46,24,52,20,9};
int n = a.length;
for(int i=n-1; i>0; i--){
for(int j=0; j<i; j++){
if(a[j]>a[j+1]){
int temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
}
Optimized bubble sort
If no adjacent swaps happened it means the array is sorted. Hence we can stop the process.
Time Complexity (Best case): O(n)
public class BubbleSort{
public static void main(String[] args) {
int a[] = new int[]{13,46,24,52,20,9};
int n = a.length;
for(int i=n-1; i>0; i--){
boolean swapHappened = false;
for(int j=0; j<i; j++){
if(a[j]>a[j+1]){
int temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
swapHappened = true;
}
}
if (!swapHappened) {
break;
}
}
}
}
Insertion Sort
Take an element and place it in its correct position
Algorithm
Push the lower number to the left through adjacent swaps
Step 1 - Adjacent swaps in the range [0,1]
Step 2 - Adjacent swaps in the range [0,2]
Step 3 - Adjacent swaps in the range [0,3]
...
Step n-1 - Adjacent swaps in the range [0,n-1]
Time Complexity - O(n^2)
public class InsertionSort {
public static void main(String[] args) {
int a[] = new int[]{13,46,24,52,20,9};
int n = a.length;
for(int i=1; i<n; i++){
int j=i;
while (j>0 && a[j-1]>a[j]) {
swap(a,j-1,j);
j--;
}
}
}
}
Merge Sort
Divide and merge
Algorithm
Divide the array into two halves, sort each half, and then merge them.
Time Complexity - O(nlogn)
Code
package Sorting;
public class MergeSort {
public static void main(String[] args) {
int arr[] = new int[]{8,4,5,2,7,9,-1,100};
mergeSort(arr, 0, arr.length-1);
}
private static void mergeSort(int[] arr, int low, int high) {
if (low==high) return;
int mid = (low+high)/2;
mergeSort(arr, low,mid);
mergeSort(arr,mid+1, high);
merge(arr, low, mid, high);
}
private static void merge(int[] arr, int low, int mid, int high) {
int length = high-low+1;
int dummy[] = new int[length];
int ptr1 = low;
int ptr2 = mid+1;
int curr = 0;
while (ptr1<=mid && ptr2<=high){
if (arr[ptr1]<arr[ptr2]){
dummy[curr] = arr[ptr1];
ptr1+=1;
} else {
dummy[curr] = arr[ptr2];
ptr2+=1;
}
curr+=1;
}
while (ptr1<=mid){
dummy[curr] = arr[ptr1];
ptr1+=1;
curr+=1;
}
while (ptr2<=high){
dummy[curr] = arr[ptr2];
ptr2+=1;
curr+=1;
}
for (int i=0; i<dummy.length; i++){
arr[low+i] = dummy[i];
}
}
}
Quick Sort
Pick a pivot and place it in its correct place in the sorted array
An element is in its sorted position if all elements on the left-hand side are smaller and all elements on the right-hand side are larger. This means the element is correctly placed, even if the rest of the elements may or may not be in their sorted positions. This is the fundamental idea behind quicksort.
Pivot can be any element of the array
It can be 1st Element of the array
It can be the last Element of the array
It can be the median of the array
It can be a random element of the array
Algorithm
Pick a pivot and find its correct position; this is called the partition index.
Now, sort the left array and right arrays concerning the pivot using the same quick sort.
Partition Index
The Partition Index in quicksort involves using two-pointers. One pointer starts at the beginning, and the other is positioned at the end. These pointers represent the left and right pointers, respectively. The left pointer halts at the index where the element value is greater than the pivot, while the right pointer stops at the index where the element is lesser than the pivot. Therefore, we swap these elements to segregate smaller elements to the left and greater elements to the right. Eventually, when both pointers intersect, we swap the pivot with the right pointer, as it holds the last element among the smaller values relative to the pivot element. Thus, the right pointer denotes the partition index.
There are 2 scenarios we swap the elements.
Scenario Swap 1
We swap elements when the left pointer encounters an element greater than the pivot and the right pointer encounters an element smaller than the pivot.
Scenario Swap 2
The right pointer stops at the index of an element smaller than the pivot, effectively separating the array into two groups: one with elements less than the pivot and the other with elements greater than the pivot.
Time Complexity - O(nlogn)
Code
package Sorting;
public class QuickSort {
public static void main(String[] args) {
int arr[] = new int[]{8,4,5,2,7,9,-1};
quickSort(arr, 0, arr.length-1);
}
private static void quickSort(int[] arr, int low, int high) {
if (low<high){
int partitionIndex = partition(arr, low,high);
quickSort(arr, low, partitionIndex-1);
quickSort(arr, partitionIndex+1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = low;
int leftPtr = low;
int rightPtr = high;
while (leftPtr<rightPtr){
// leftPtr also starts at pivot so equals to mandatory
while (leftPtr<=high && arr[leftPtr]<=arr[pivot] ) leftPtr+=1;
while (rightPtr>=low && arr[rightPtr]>arr[pivot]) rightPtr-=1;
if (leftPtr<rightPtr) swap(arr, leftPtr, rightPtr);
}
swap(arr,pivot,rightPtr);
return rightPtr;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Time Complexity
Best Case Scenario:
If the partition index is the middle element, the maximum depth of the recursion tree is log n. Finding the partition index takes O(n) at each level. Therefore, the total time complexity is O(nlog n).
Worst Case Scenario:
If the array is already sorted, the partition index will always be the first element. This results in a maximum recursion depth of n. Finding the partition index takes O(n) at each level. Thus, the total time complexity is O(n^2).