Sorting Algos

 Bubble Sort

This is the most simple sorting algorithm. Just swap adjacent elements until the array is sorted. Like we have to traverse whole array n-2 times and in each traversal we have just this condition: check if the the left node is greater than right. If yes, just swap them. Time Complexity(Average, worst, best)= O(n^2)

code(in C++):

for (i = 0; i < n-1; i++)      
      
    // Last i elements are already in place  
    for (j = 0; j < n-i-1; j++)  
        if (arr[j] > arr[j+1])  
            swap(&arr[j], &arr[j+1]);  

Insertion Sort

Another Simple and intuitive algorithm, yet an efficient one. Its just the way we normally sort as "normal" humans. Suppose we are at some position of array, i, what we do is to take the element at the ith card and then swap it with the element it should be to make the array before i position ,sorted. 

Time Complexity: 

O(n^2)(Average and worst) 

O(n)(Best case)(When array is already sorted)

int i, key, j;  
    for (i = 1; i < n; i++) 
    {  
        key = arr[i];  
        j = i - 1;  
  
        /* Move elements of arr[0..i-1], that are  
        greater than key, to one position ahead  
        of their current position */
        while (j >= 0 && arr[j] > key) 
        {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = key;  
    }  

Selection Sort

Selection sort is simple: find minimum element in the array and swap it with the current pointer. Quite intuitive! 

Time Complexity: O(n^2) (Best ,worst and average)

int i, j, min_idx;  
  
    // One by one move boundary of unsorted subarray  
    for (i = 0; i < n-1; i++)  
    {  
        // Find the minimum element in unsorted array  
        min_idx = i;  
        for (j = i+1; j < n; j++)  
        if (arr[j] < arr[min_idx])  
            min_idx = j;  
  
        // Swap the found minimum element with the first element  
        swap(&arr[min_idx], &arr[i]);  
    }  

Merge Sort

It is a recursive sorting algorithm and its principle is based on DIVIDE AND CONQUER. Just divide the array into two parts and make both arrays sorted(by the same technique of dividing elements) and then merge them. w till dividing everything is fine but what happens on merging?  Simple, we merge them comparing the corresponding elements one by one. Time complexity: dividing takes log n time and merging them takes n. So total=O(nlogn) in all three cases(best,worst,average)

void merge(int arr[], int l, int m, int r)
{
    int n1 = m - l + 1;
    int n2 = r - m;
 
    // Create temp arrays
    int L[n1], R[n2];
 
    // Copy data to temp arrays L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
 
    // Merge the temp arrays back into arr[l..r]
 
    // Initial index of first subarray
    int i = 0;
 
    // Initial index of second subarray
    int j = 0;
 
    // Initial index of merged subarray
    int k = l;
 
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    // Copy the remaining elements of
    // L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    // Copy the remaining elements of
    // R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
 
// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
 
        // Same as (l+r)/2, but avoids
        // overflow for large l and h
        int m = (l + r - l) / 2;
 
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
 
        merge(arr, l, m, r);
    }
}
  

Quick Sort

Another sorting algo based on DIVIDE AND CONQUEUER which is quite confusing at first. The crux is that fix a pivot, and swapping elements based on comparison with pivot. Now the algoritm actually is not that straight forward and you would simply get lost in visualization but if you see the code you may understand more easily.

The 

int partition (int arr[], int low, int high)  
  {  
      int pivot = arr[high]; // pivot  
      int i = (low - 1); // Index of smaller element  

      for (int j = low; j <= high - 1; j++)  
      {  
          // If current element is smaller than the pivot  
          if (arr[j] < pivot)  
          {  
              i++; // increment index of smaller element  
              swap(&arr[i], &arr[j]);  
          }  
      }  
      swap(&arr[i + 1], &arr[high]);  
      return (i + 1);  
  }  

  /* The main function that implements QuickSort  
  arr[] --> Array to be sorted,  
  low --> Starting index,  
  high --> Ending index */
  void quickSort(int arr[], int low, int high)  
  {  
      if (low < high)  
      {  
          /* pi is partitioning index, arr[p] is now  
          at right place */
          int pi = partition(arr, low, high);  

          // Separately sort elements before  
          // partition and after partition  
          quickSort(arr, low, pi - 1);  
          quickSort(arr, pi + 1, high);  
      }  
  }