Sorting

Comparisons : No of comparisons made to sort an array.

Inversions : i,j forms an inversion if a[i] > a[j]. ie. i&j are out of order. .Best Case : 0 for already sorted array, Worst Case : for reverse sorted array.

Stable Sort : A sorting is stable if, the relative order of the elements with same value is maintained in sorted array.

Bubble Sort

1. Works by repeatedly swapping the adjacent nodes if they are not in order. 
2. After each iteration , highest element is moved to the end. 
3. Requires n-1 passes.

Bubble Sort


public void bubbleSort(int[] arr){
   int n = arr.length;
   for(int i=1;i<n;i++){
      for(int j=0;j<n-i;j++){
         if(arr[j]>arr[j+1]){
            // found inversion. swap elements
            arr[j] = arr[j] + arr[j+1];
            arr[j+1] = arr[j] - arr[j+1];
            arr[j] = arr[j] - arr[j+1];
         }
      }
   }
}

Time Complexity : O(n²)

Space Complexity : O(1)

Stable Sort
O(n) for already sorted array.
No of comparisons : O(n²) – For each iterations i we will do n-i comparisons.
No of Inversions : O(n²) – In worst case scenario, for each iteration i, no of inversions will be n-i;

Selection Sort

1. Works by finding the minimum element in each iteration and swapping it with the beginning. 
2. After each iteration, smallest element is moved to the front. 
3. Requires n-1 pass.

Selection Sort

   
public void selectionSort(int[] arr){
   int n = arr.length;
   for(int i=1;i<n;i++){
      int minIndex = i;
      for(int j=i;j<n;j++){
         if(arr[j]<arr[minIndex]){
            minIndex  = j;
         }
      }
      // swap minIndex to i
      swap(arr, i, minIndex);
   }
}

Time Complexity : O(n²) always.

Space Complexity : O(1)

Unstable Sort
No of comparisons : O(n²)
No of Inversions : O(n²) – In worst case scenario, for each iteration i, no of inversions will be n-i;
No of swaps : O(n)

Insertion Sort

1. Simple sorting algorithm which sorts the array by shifting elements one at a time. 
2. At any given iteration i, arr[i-1] will be sorted and arr[i] will be inserted into the sorted array. 
3. It is adaptive as it reduces the steps if array is nearly sorted. 
4. Requires n-1 pass.

Insertion Sort

public void insertionSort(int[] arr){
   int n = arr.length;
   
   for(int i=1;i<n;i++){
      int temp = arr[i];
      int j = i-1;
      while(arr[j] > temp && j >=0 ){
         arr[j+1] = arr[j];
         j--;
      }
      arr[j+1] = temp;
   }
   
}

Time Complexity : O(n²).

Space Complexity : O(1)

Stable Sort.
Efficient for smaller data-sets.
No of comparisons : O(n²)
No of Inversions : O(n + d).
No of swaps : O(n²)

Merge Sort

Merge Sort is based on Divide & Conquer Strategy. It divides the array in two halves and call itself on each half. Then it Merges the sorted halves.

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

Merge Sort - g4g

public static void mergeSort(int[] arr, int l, int r){
   if(l<r){
      int m = l + (r-l)/2;
      mergeSort(arr, l, m);
      mergeSort(arr, m+1, r);
      merge(arr, l, m, r);
   }
}

private static void merge(int[] arr, int l, int m, int r) {
   int p = m-l+1;
   int q = r-m;
   int[] a1 = new int[p];
   int[] a2  = new int[q];
   for(int i=0;i<p;i++){
      a1[i] = arr[l+i];
   }
   for(int j=0;j<q;j++){
      a2[j] = arr[j+m+1];
   }
   int i=0,k=l,j=0;
   while(i<p && j <q){
      if(a1[i] < a2[j]){
         arr[k++] = a1[i++];
      }
      else if(a1[i] > a2[j]){
         arr[k++] = a2[j++];
      }
   }
   while(i<p){
      arr[k++] = a1[i++];
   }
   while(j<q){
      arr[k++] = a2[j++];
   }
}

Time Complexity : O(nlog(n)).

Space Complexity : O(n)

Stable Sort
It can be used to count the number of inversions in an array.

Quick Sort

Quick Sort also works on Divide and Conquer strategy. We pick a pivot element and divide the array into two partitions, A1 - Containing elements less than pivot element and A2 - Containing elements greater than pivot element.

After each call of partition method, the position of pivot element gets finalized.

Algo :
1. Select a pivot element. 
2. Divide the array around pivot elements. 
3. For each array call the quick-sort method.

public static void quickSort(int[] arr, int l, int r){
   if(l < r){
      int p = partition(arr, l, r);
      quickSort(arr, l, p-1);
      quickSort(arr, p+1, r);
   }
}

private static int partition(int[] arr, int l, int r) {
   int pivot = l;
   int i=l+1, j = r;
   while(true){
      while( i < r && arr[i]<arr[pivot]){i++;}
      while(j>=l && arr[j]>arr[pivot]){j--;}
      if(i<j){
         swap(arr, i, j);
      } else{
         break;
      }
   }
   swap(arr, pivot, j);
   return j;
}

Time Complexity = T(n) = [T(k) + T(n-k-1) + Θ(n)] ~ O(nlog(n)) (Average case), where k is no of elements smaller than pivot.

Worst Case : when pivot element is always greatest or smallest element. Complexity O(n²).

Best Case : when pivot element is always the middle element. Complexity O(nlog(n))

Inplace sort
Stable Sort