Algorithm sorting

This is a continuation of Algorithms Sorting, in this write up we will introduce our last basic sorting algorithm which is the insertion sort.
Insertion Sort
The insertion sort builds up the sort by gradually creating a larger left portion which is always sorted.
Take the array for example
[ 5, 3, 4, 1, 2 ]
[ 3, 5, 4, 1, 2 ]
[ 3, 4, 5, 1, 2 ]
[ 1, 3, 4, 5, 2 ]
[ 1, 2, 3, 4, 5 ] //sorted array
Taking a look at the first array, insertion sort looks at the left or sorted portion of the array which is starting from 5, it compares 5 and 3 since 3 is less than 5 it inserts it before 5, now the sorted portion of the array is [3,5] It compares that to the next element which is 4 and places it where it belongs in the sorted portion of the array, this sorted portion then becomes [3,4,5]. The algorithm does this until it has come to the end of the array.
Pseudocode

• Start by picking the second element in the array
• Now compare the second element with the one before it and swap if necessary.
• Continue to the next element and if it is in the incorrect order, iterate through the sorted portion (i.e. the left side) to place the element in the correct place.
• Repeat until the array is sorted.

 
Code For Insertion Sort
function insertionSort(arr){
var currentVal;
    for(var i = 1; i < arr.length; i++){
        currentVal = arr[i];
        for(var j = i – 1; j >= 0 && arr[j] > currentVal; j–) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal;
    }
    return arr;
}
Intermediate Sorting algorithms
The algorithms in this category are a little more complex than the basic ones. They are also quite faster and can greatly improve performance depending on the situation. There are certain situations where a simple sorting algorithm will work better than an intermediate algorithm.
We will be looking at two sorting algorithms which are 

• Merge Sort
• Quick Sort

Why do we need these sorting algorithms

• The sorting algorithms we’ve learned so far don’t scale well
• Try out bubble sort on an array of 100000 elements, it will take quite some time!
• We need to be able to sort large arrays more quickly

Faster Sorts

• They can  improve time complexity from O(n  ) to O(n log n)
• There’s a tradeoff between efficiency and simplicity
• The more efficient algorithms are much less simple, and generally take longer to understand

Merge Sort

• It’s a combination of two things – merging and sorting!
• Exploits the fact that arrays of 0 or 1 element are always sorted
• Works by decomposing an array into smaller arrays of 0 or 1 elements, then building up a new sorted array

How does it work
Let us visualize it 
[ 8, 3, 5, 4, 7, 6, 1, 2 ]
[ 8, 3, 5, 4 ] [ 7, 6, 1, 2 ]
[ 8, 3 ] [ 5, 4 ] [ 7, 6 ]       [ 1, 2 ]
   [ 8 ] [ 3 ] [ 5 ] [ 4 ] [ 7 ]   [ 6 ]   [ 1 ]       [ 2 ]
       [ 3, 8 ] [ 4, 5 ]   [ 6, 7 ]         [ 1, 2 ]
[ 3, 4, 5, 8 ] [ 1, 2, 6, 7 ]
[ 1, 2, 3, 4, 5, 6, 7, 8 ]
From the above layout, we see that the entire array was split until it had split all the elements into their individual array, then it began sorting them.
Pseudocode

• Break up the array into halves until you have arrays that are empty or have one element
• Once you have smaller sorted arrays, merge those arrays with other sorted arrays until you are back at the full length of the array
• Once the array has been merged back together, return the merged (and sorted!) array

Quick Sort

• Like merge sort, exploits the fact that arrays of 0 or 1 element are always sorted
• Works by selecting one element (called the “pivot”) and finding the index where the pivot should end up in the sorted array
• Once the pivot is positioned appropriately, quicksort can be applied on either side of the pivot

How does it work
[ 5, 2, 1, 8, 4, 7, 6, 3 ]
Let us pick a pivot 5, the algorithm takes all the elements less than 5 and puts them on the left side of 5 and all the elements that are greater than 5 and puts them on the right side of 5. Then we look at the left side of the array, pick a pivot point and do the same thing to it. We move the elements greater than it to the right and the elements greater than it to the left. We do this till we have single or 1 element arrays before we repeat the process on the right side.
5 → pivot
   Pivot <–3              7→ pivot
1      4     6    8
        2
Pivot Helper

• In order to implement merge sort, it’s useful to first implement a function responsible for arranging elements in an array on either side of a pivot
• Given an array, this helper function should designate an element as the pivot
• It should then rearrange elements in the array so that all values less than the pivot are moved to the left of the pivot, and all values greater than the pivot are moved to the right of the pivot
• The order of elements on either side of the pivot doesn’t matter!
• The helper should do this in place, that is, it should not create a new array
• When complete, the helper should return the index of the pivot

Picking a Pivot

• The runtime of quicksort depends in part on how one selects the pivot
• Ideally, the pivot should be chosen so that it’s roughly the median value in the data set you’re sorting
• For simplicity, we’ll always choose the pivot to be the first element (we’ll talk about consequences of this later)

Pivot Pseudocode

• It will help to accept three arguments: an array, a start index, and an end index (these can default to 0 and the array length minus 1, respectively)
• Grab the pivot from the start of the array 
• Store the current pivot index in a variable (this will keep track of where the pivot should end up)
• Loop through the array from the start until the end

• If the pivot is greater than the current element, increment the pivot index variable and then swap the current element with the element at the pivot index
• Swap the starting element (i.e. the pivot) with the pivot index
• Return the pivot index

QuickSort PseudoCode

• Call the pivot helper on the array
• When the helper returns to you the updated pivot index, recursively call the pivot helper on the subarray to the left of that index, and the subarray to the right of that index
• Your base case occurs when you consider a subarray with less than 2 elements

QuickSort Code
function pivot(arr, start = 0, end = arr.length – 1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };
  // We are assuming the pivot is always the first element
  let pivot = arr[start];
  let swapIdx = start;
  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }
  // Swap the pivot from the start the swap point
  swap(arr, start, swapIdx);
  return swapIdx;
}
function quickSort(arr, left = 0, right = arr.length -1){
    if(left < right){
        let pivot index = pivot(arr, left, right) //3
        //left
        quickSort(arr,left,pivot index-1);
        //right
        quickSort(arr,pivotIndex+1,right);
      }
     return arr;
} 
BigO complexity

Algorithm	Time Complexity(Best)	Time Complexity(Average)	Time Complexity(Worst)
Insertion Sort	O(n)	O(n^2 )	O(n ^2)
Merge Sort	O(n log n)	O(n log n)	O(n ^2)
Quick Sort	O(n log n)	O(n log n)	O(n log n)

 
 

Author:  Okocha Ebube Emmanuel