Simple Explanation of Sorting Algorithms with JavaScript | Part 2

This is the second part of the Sorting Algorithms with Javascript from the “Understanding Data Structure and Algorithms with JavaScript ” series. In this blog, we will discuss two significant sorting algorithms known as Merge and Quick Sorting algorithms.

We will also discuss its Working, Implementation with Javascript, Illustration, and the time complexity of each algorithm takes.

Disadvantages of using Selection, Bubble, and Insertion Sort

• Selection, Bubble, and Insertion sort algorithms may be simple and fast with arrays with fewer elements but sadly they don’t scale well with large numbers of input.
• Time complexities of Selection, Bubble, and Insertion sort algorithms are not as good as of Merge, Quick, or Radix sort, (o(n²) to O(nlogn).
• Selection, Bubble, and Insertion sort algorithms are simple and easy to understand but are not very efficient whereas Merge, Quick, or Radix sort may be long and has a big learning curve but are very reliable and super fast with a large set of data. 

Also read, Understanding Array, String, and Object Data Structure with JavaScript

Merge Sort

Merge Sort is a sorting algorithm based on the divide and conquer method. The merge sort algorithm repeatedly divides the problems until we have a single element after that arrange it back in a sub-sorted array and keep on combining until it gradually becomes a sorted array.

Steps

Merge Sort is a combination of two things – merging and sorting! In order to implement the merge sort algorithm, it is helpful if we first implement a function responsible for merging two sorted arrays. For example – Given two sorted arrays, this helper function should be able to create a new array with the elements of two input arrays that are also sorted.

• Create an empty array, take a look at the smallest values in each input array,
• While there are still values we haven’t looked at,
  • If the value in the first array is smaller than the value in the second array, push the value from the first array into our results and move on to the next value in the first array.
  • If the value in the first array is larger than the value in the second array, push the value from the second array into our results and move on to the next value in the second array.
  • Once we completed one of the two arrays, push in all the remaining values to the result.
• Write the Main function now aka breaking given arrays in half till we have a single element present.
  • Once you have smaller sorted arrays, merge those arrays with other sorted arrays until you have all the elements in the correct order.
  • Once you have final sorted arrays merged back together, return it!

Also read, A.I. Can Now Write Its Own Computer Code. That’s Good News for Humans.

Illustrations

Also read, Simple Explanation of Stack and Queue with JavaScript

Implementation with JavaScript

// helper function to merge the sort array
function merge(num1, num2) {
  let result = [];
  let i = 0;
  let j = 0;

  while (i < num1.length && j < num2.length) {
    if (num2[j] >= num1[i]) {
      result.push(num1[i]);
      i++;
    } else {
      result.push(num2[j]);
      j++;
    }
  }

  while (i < num1.length) {
    result.push(num1[i]);
    i++;
  }

  while (j < num2.length) {
    result.push(num2[j]);
    j++;
  }

  return result;
}

// main function
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

let arr = [4, 9, 7, 1, 2, 5, 6];

let res = mergeSort(arr);

console.log(res); //[1, 2, 4, 5, 6, 7, 9]

Best Time Complexity – O(n logn)
Worst Time Complexity – O(n logn)
Space Complexity – O(n)

Also read, What is Big O Notation – Space and Time Complexity

Quick Sort

The quick sort algorithm works on the same method as the merge sort but in quick sort, we work by selecting one element known as a pivot and finding the index where the pivot should end up in the sorted array. Once we have the pivot element at the correct position, quick sort is applied on either side of the pivot element.

Steps

Just as in the Merge sort first we implemented a helper function, in Quick sort also we going to create the first helper function which will be useful in arranging elements in an array on either side of the pivot element.

• Write the helper pivot function which accepts three arguments: an array, start index and end index (these can have default value 0 and arr.length – 1, respectively).
• Initialize the first element of the array as a pivot point, and store the pivot index in a variable to track where the pivot should end up.
• Loop the array from start to end
  • if the pivot element is greater than the current element, increase the pivot index variable and swap the current element with the element at the pivot index.
• Swap the pivot element with the element at the current pivot index.
• Return the current pivot index.

Note:- 

1. The runtime of quick sort totally depends on the process of pivot selection.
2. Ideally, we should always try to choose the median element as a pivot in the given data set you want to sort.

• Write the Main function now, the helper function will return us an updated pivot Index each time and then we recursively call the helper function for the left subarray and another for the right subarray across the pivot index.

Also read, Simple Explanation on Searching Algorithms with JavaScript

Illustrations

Implementation with JavaScript

// helper function to swap two digits
function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

// pivot helper function
function pivot(arr, start = 0, end = arr.length - 1) {
  let pivotElement = arr[start];
  let pivotIndex = start;

  for (let i = start + 1; i < arr.length; i++) {
    if (pivotElement > arr[i]) {
      pivotIndex++;
      swap(arr, pivotIndex, i);
    }
  }
  swap(arr, start, pivotIndex);

  return pivotIndex;
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right);

    //for left
    quickSort(arr, left, pivotIndex - 1);

    //for right
    quickSort(arr, pivotIndex + 1, right);
  }

  return arr;
}

let res = quickSort([4, 9, 7, 1, 2, 5, 6]);

console.log(res); //[1, 2, 4, 5, 6, 7, 9]

Best Time Complexity – O(nlogn )
Worst Time Complexity – O(n²)
Space Complexity – O(log n)

Also read, Simple Explanation on Sorting Algorithms with JavaScript | Part 1

Final Words

I really hope you like the article and if you do then please share it more with your friends and colleagues, also bookmark this website to get awesome articles like these also on exciting tutorials, working on Javascript fundamentals, and React.