Bubble Sort – O(n2)

  • Go through the entire array for n-1 times and swap smallest numbers towards the left
void bubbleSort(int arr[]) { 
    int n = arr.length; 
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++){ 
            
            if (arr[j] > arr[j+1]) { 
                // swap temp and arr[i] 
                int temp = arr[j]; 
                arr[j] = arr[j+1]; 
                arr[j+1] = temp; 
            } 
        }
    }
} 

Improved Bubble Sort – O(n)

  • We insert a flag termed as “sorted” as true, if a swap happens then we turn the flag to false. Keep in mind, this is an edge case and the complexity is O(n). It is only possible if all the elements are sorted.
  • If the array is sorted, there are no swaps and the loop is broken in the first iteration itself and the complexity becomes O(n).
void ImprovedBubbleSort(int arr[]) {
bool sorted = true; 
    int n = arr.length; 
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++){ 
            if (arr[j] > arr[j+1]) { 
                int temp = arr[j]; 
                arr[j] = arr[j+1]; 
                arr[j+1] = temp;
                sorted = false;
            } 
        }
    if(sorted) {
         return;
       }
    }
} 

Selection Sort – O(n^2)

  • Go through the array n-1 times and search for the smallest number
  • Move it to the leftmost part of the array using a temp variable.
  • It is called selection sort because we “select” the smallest number
  • And swap the number in the relevant position
void SelectionSort(int arr[]){ 
    int n = arr.length; 
    for (int i = 0; i < n-1; i++) { 
    // Find the minimum element in unsorted array 
        int min_idx = i; 
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j; 
            }
        }
        // We use min_idx to keep track of the item to be replaced
        // So we swap the min element with the first element 
        arr[min_idx] = swapFunction(arr[i],arr[i]=arr[min_idx]);
    } 
}
 
public static int swapFunction(int first, int second){
        return first;
}

Insertion Sort – O(n2)

  • Take the array and mark the first element as sorted.
  • Iterate through the entire array and keep inserting elements to the sorted array.
  • We move rest of the elements to the right
void InsertionSort(int arr[]) {
    int n = arr.length; 
    for (int i = 1; i < n; ++i) { 
        // Sets the first sorted element &amp; sets it to current
        int current = arr[i]; 
        int j = i-1; 
            
       // Shifts all elements to the right
       // to create space for the leftmost element 
        while (j>=0 &amp;&amp; arr[j] > current) { 
            arr[j+1] = arr[j];         
            j = j-1; 
        } 
        arr[j+1] = current; 
    } 
} 

Difference Between Selection Sort and Insertion Sort

  • In selection sort, the inner loop is over the unsorted elements. Each pass selects one element, and moves it to its final location (at the current end of the sorted region).
  • In insertion sort, each pass of the inner loop iterates over the sorted elements. Sorted elements are displaced until the loop finds the correct place to insert the next unsorted element.
  • In a selection sort, sorted elements are found in output order, and stay put once they are found. Conversely, in an insertion sort, the unsorted elements stay put until consumed in input order, while elements of the sorted region keep getting moved around.
  • Selection sort does one swap per pass of the inner loop. Insertion sort typically saves the element to be inserted as temp before the inner loop, leaving room for the inner loop to shift sorted elements up by one, then copies temp to the insertion point afterwards.

ShellSort – O( n (log2(n)) )

  • Shell sort is similar to insertion sort.
  • In insertion sort, we move all elements to the right by 1 index.
  • In Shell sort, we select a term called “GAP” (Usually n/2) for every iteration.
  • We sort the array until n becomes 1.
  • For each iteration we compare the elements on the gap index and sort them. (0,0+gap,0+gap+gap,…)
  • The concept is to allow exchange of far items.
  • We then run insertion sort after the gap becomes 1.
int ShellSort(int arr[]) { 
    int n = arr.length; 
    for (int gap = n/2; gap > 0; gap = gap/2) { 
        for (int i = gap; i < n; i++) { 
// add a[i] to the elements that have been gap 
// sorted save arr[i] in temp and make a hole at 
// position i 
            int temp = arr[i]; 
// shift earlier gap-sorted elements up until 
// the correct location for arr[i] is found 
            int j; 
            for (j = i; j >= gap &amp;&amp; arr[j - gap] > temp; j=j-gap) {
                arr[j] = arr[j - gap]; 
            }
// put temp in its correct location
            arr[j] = temp; 
        } 
    } return 0; 
} 

QuickSort – O(n2)

  • We choose a pivot and iterate through the entire array.
  • We select a left & right and check if left < pivot & right > pivot.
  • If not, we swap both of the elements. (And keep doing this recursively)
  • It picks an element as pivot and partitions the given array around the picked pivot.
public static void quicksort(int[] array){
    quicksort(array,0,array.length-1);
}
 
public static void quicksort(int[] array, int left, int right){
    if(left>=right){
        return;
    }
    int pivot = array[(left+right) / 2];
    int index = partition(array,left,right,pivot);
    quicksort(array,left,index-1);
    quicksort(array,index,right);
}
 
public static int partition(int[] array, int left, int right, int pivot){
    while(left<=right){
        while(array[left] < pivot){
            left++;
        }
 
        while(array[right] > pivot){
            right--;
        }
 
        if (left <= right){
            //swap
            array[left] = swapFunction(array[right],array[right]=array[left]);
            left++;
            right--;
        }
    }
    return left;
}

public static int swapFunction(int first, int second){
        return first;
}

MergeSort – O(n log (n))

  • MergeSort works on divide and conquer as it divides the array in two parts.
  • It keeps on splitting the array into two and sorts them recursively.
  • A middle is selected and array is broken down into two parts over and over again.
  • Both arrays are compared and a new array is created while inserting the items while comparing from the first two arrays.
public static void mergesort(int[] array){
	mergesort(array,new int[array.length], 0,array.length-1);
}

public static void mergesort(int[] array, int[] temp, int leftStart, int rightEnd){
	if (leftStart >= rightEnd){
		return;
	}
	int middle = (leftStart+rightEnd) / 2;
	mergesort(array,temp,leftStart,middle);
	mergesort(array,temp,middle+1,rightEnd);
	mergeHalves(array, temp, leftStart, rightEnd);
}

public static void mergeHalves(int[] array, int[] temp, int leftStart,int rightEnd){
	int leftEnd = (rightEnd+leftStart)/2;
	int rightStart = leftEnd+1;
	int size = rightEnd - leftStart + 1;

	int left = leftStart;
	int right = rightStart;
	int index = leftStart;

	while (left <= leftEnd &amp;&amp; right <= rightEnd){
		if(array[left] <= array[right]){
			temp[index] = array[left];
			left++;
		} else{
			temp[index] = array[right];
			right++;
		}
		index++;
	}
// Copying all remaining elements into the temp array.
	System.arraycopy(array,left,temp,index,leftEnd - left + 1);
	System.arraycopy(array,right,temp,index,rightEnd - right + 1);
	System.arraycopy(temp,leftStart,array,leftStart,size);
}

Tree Sort  – O(n2)

In Tree Sort, We get the list of items in an array and we make a BST (Binary Search Tree)

  • The left of a root has a value less than it.
  • The right of a root has a value greater than it.
  • The left and right subtree each must also be a binary search tree.

We then perform an In-Order Traversal on this tree i.e. (Left>Parent>Right)

  1. Traverse the left subtree, i.e., call Inorder(left-subtree)
  2. Visit the root.
  3. Traverse the right subtree, i.e., call Inorder(right-subtree)
import java.util.Arrays;
class TreeSort  { 
	class Node { 
		int key; 
		Node left, right; 
   
		public Node(int item) { 
			key = item; 
			left = right = null; 
		} 
	} 
	 
	Node root; 
	TreeSort() {  
		root = null;  
	} 
 
	// First
	void treeInsert(int arr[]) { 
		for(int i = 0; i < arr.length; i++) { 
			insert(arr[i]); 
		} 
	} 
	// Call to Insert
	void insert(int key) { 
		root = insertRec(root, key); 
	} 
	// Call to insertRec
	Node insertRec(Node root, int key) { 
		if (root == null) { 
			root = new Node(key); 
			return root; 
		} 
   
		if (key < root.key) {
			root.left = insertRec(root.left, key); 
		} else if (key > root.key) {
			root.right = insertRec(root.right, key); 
		}
		return root; 
	}
	 
	// For inorder traversal of BST 
	void inorderTraversal(Node root) { 
		if (root != null) { 
			inorderTraversal(root.left); 
			System.out.print(root.key + " "); 
			inorderTraversal(root.right); 
		} 
	} 
 
	public static void main(String[] args) { 
		TreeSort tree = new TreeSort(); 
		int arr[] = {5, 4, 7, 2, 11}; 
		System.out.println("Before Sorting = "+Arrays.toString(arr));
		tree.treeInsert(arr); 
		System.out.print("After Sorting = ");
		tree.inorderTraversal(tree.root); 
	} 
}

Heap Sort – O(n log n)

  • From the unsorted array, we create a binary heap.
  • A Binary Heap is a complete binary tree, i.e. a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible and items are stored in a manner such that value in a parent node is greater than the values in its two children nodes.
  • Build a Max-Heap
  • Now replace the largest element with the last element in the tree and remove the largest element (Which is now the last one).
  • Build the max heap and repeat the earlier two processes.
import java.util.Arrays;
class HeapSort { 
	public void HeapSort(int arr[]) { 
		int n = arr.length; 
  
		// Build heap (rearrange array) 
		for (int i = n / 2 - 1; i >= 0; i--) {
			heapify(arr, n, i); 
		}
  
		// One by one extract an element from heap 
		for (int i = n-1; i >= 0; i--) { 
			// Move current root to end 
			arr[0] = swapFunction(arr[i], arr[i] = arr[0]);
  
			// call max heapify on the reduced heap 
			heapify(arr, i, 0); 
		} 
	} 
  
	// To heapify a subtree rooted with node i which is 
	// an index in arr[]. n is size of heap 
	void heapify(int arr[], int n, int i) { 
		int largest = i; // Initialize largest as root 
		int left = 2*i + 1; // left = 2*i + 1 
		int right = 2*i + 2; // right = 2*i + 2 
  
		// If left child is larger than root 
		if (left < n &amp;&amp; arr[left] > arr[largest]) {
			largest = left; 
		}
  
		// If right child is larger than largest so far 
		if (right < n &amp;&amp; arr[right] > arr[largest]) {
			largest = right; 
		}
  
		// If largest is not root 
		if (largest != i) { 
			//swap
			arr[i] = swapFunction(arr[largest], arr[largest] = arr[i]);
			// Recursively heapify the affected sub-tree 
			heapify(arr, n, largest); 
		} 
	} 
  
	static void printArray(int arr[]) { 
		System.out.println("After Sorting ="+Arrays.toString(arr));
	} 
	
	public static int swapFunction(int first, int second){
			return first;
	}
  
	// Driver program 
	public static void main(String args[]) { 
		int arr[] = {12, 11, 13, 5, 6, 7}; 
		System.out.println("Before Sorting ="+Arrays.toString(arr));
		int n = arr.length; 
		HeapSort hp = new HeapSort(); 
		hp.HeapSort(arr); 
		printArray(arr); 
	} 
}