Summary of 5 types of sorting in programming (Part 2)

— Quick sort and Merge sort

Comparison between 5 types of sort algorithms and their performance

In Part 1, we have explored bubble sort, insertion sort and selection sort. In this part, we will look into quick sort and merge sort. Both of them adopted divide and conquer technique, and are faster and more widely used than bubble sort, insertion sort selection sort while the implementation is also simple.

If you want to review Part 1, here is the link:

Summary of 5 types of sorting in programming (Part 1)

QUICK SORT

The feature of quick sort is to have a pivot value as the reference point, then recursively divide 2 sub-arrays by comparing the elements with the pivot value. It achieves O(n log n) both best and average cases. In particular, its performance can be slightly faster than merge sort for randomized data on large distribution. (From Wikipedia — Quick Sort)

P.S.:
There are many variations revolving the choice of pivot value and other details. They will greatly affect the efficiency. For this reason, I will only list out the shared features to be considered as quick sort, while the illustration will be put inside the examples respectively.

Main features:

1. Pivot value is selected using one of the elements inside the array.
2. Compare the rest of elements with the pivot value, to divide into partitions.
3. Recursive method.

Example 1

In the beginning of the function, you will set a indicator to terminate the recursion or the recursion will not know when to stop. You use if/else to return [] in case the array is empty.

By this, it can also handle the edge case if the argument array is empty.

In the top part of the else scope, declare a pivot number to store a value, in this example we use index[0] (in the classic model, it is the last element of the array, you can do the same as well). Also, there are 3 array variables to store the elements which are less than pivot number, equal to pivot number, and greater than pivot number.

After then, you use for loop / for of to iterate through the array and divide all elements into those 3 arrays.

Lastly, return a new array using destructuring with recursion, calling the function to the lower and the greater sub arrays.

function quickSort(array) {
  if (array.length < 1) {
    return [];
  } else {
    let pivotNum = array[0];
    let lower = [];
    let higher = [];
    let equal = [];

    for (let elem of array) {
      if (elem < pivotNum) { lower.push(elem)} 
      else if (elem > pivotNum) { higher.push(elem)}
      else { equal.push(elem)};
    }
    return [...quickSort(lower), ...equal, ...quickSort(higher)];
  }
}

Here is the illustration for ease of understanding:

Illustration for example 1

Example 2 (using Hoare’s partition scheme)

In this approach, other than the main function, we have 2 utility functions: swap(), and pivot(). Swap() is to swap the position of 2 elements, pivot() is to dynamically determine the position of pivot number during the recursion.

Inside pivot(), you set the initial pivot to be the first element of the array, and start looping from the one right to the pivot. If there isn’t any elements greater than the pivot, there will not be any change on that round. If there is any elements greater, set it as the temp pivot, swap its position with the element on the right side of the initial / previous pivot. (see illustration)

The main function quickSort() has 3 parameters:

• the array
• the begin index
• the end index

You will use logic to check if the begin index == the end index, if yes, it means the array is completely sorted, return the array.

If not, inside the if scope, you use recursion to call quickSort() with same arguments except the start index which is the previous start index + 1. (Be aware if you forgot to do so will result infinite loop)

function swap(arr, x, y) {
  [arr[x], arr[y]] = [arr[y], arr[x]];
}

function pivot(arr, left = 0, right = arr.length - 1) {
  let shift = left;
  for (let i = left + 1; i <= right; i++) {
    if (arr[i] < arr[left]) swap(arr, i, ++left);
  }
  swap(arr, left, shift);
  return shift;
}

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

It may be easier to look at the illustration to understand:

Illustration for example 2

MERGE SORT

Merge sort takes divide and conquer technique same as quick sort. In most implementations it performs stably.

Summary of steps:

1. Use recursion to divide the array into n sub arrays, each containing one element.
2. Signal recursion to stop when the division starts creating empty sub arrays.
3. Each sub array with 1 element is considered sorted.
4. Repeatedly merge sorted sub arrays to form new sorted sub arrays until there is only one sub array.

EXAMPLE

First of all, you create the main function mergeSort(). Inside its scope, you use if to branch out 2 possibilities: (1) array containing 1 or 0 elements, and (2) array containing more elements than 1.

This is to set a condition (when the sub arrays contains only 0/1 element) to terminate the recursion and return the array.

In else scope, you divide the array into 2 parts by creating 3 variables:

1. midpoint for spliting array into 2 sub arrays
2. use slice() to get the first half till the midpoint
3. use slice() to get the second half from the midpoint to the end

After that, you call merge() to take the invocation of mergeSort() to those 2 sub arrays created above respectively.

Let’s take a closer look into merge().

First you will declare an empty array for storing sorted elements, here I called it mergedArr.

You need to loop through these 2 arrays, here I used while loop. If whichever array got empty during the iteration, the loop will be terminated and jump out of the meeting. Then, you will use destructuring to combine the mergedArr, the leftover of arrA and the leftover of arrB.

Inside the while loop, you need to do the reordering. If arrA[0] > arrB[0], the smaller one — arrB[0] will be pushed to mergedArr while being deleted from arrB. If arrA[0] < arrB[0], vice versa.

If arrA[0] and arrB[0] have the same value, push both of them to mergedArr and delete from arrA and arrB.

function mergeSort(array) {
  if (array.length <= 1) {
    return array;
  } else {
    const midpoint = Math.floor(array.length / 2);
    const firstHalf = array.slice(0,midpoint);
    const secondHalf = array.slice(midpoint);

    return merge(mergeSort(firstHalf),mergeSort(secondHalf));
  }
}

function merge(arrA, arrB) {
  let mergedArr = [];

  while (arrA.length && arrB.length) {
    if (arrA[0] > arrB[0]) {
      mergedArr.push(arrB.shift());
    } else if (arrA[0] < arrB[0]) {
      mergedArr.push(arrA.shift());
    } else {
      mergedArr.push(arrA.shift(), arrB.shift());
    }
  }
  return [...mergedArr, ...arrA, ...arrB];
}

As always, the illustration is under the code block, for ease of reference :D

Illustration for merge sort

CONCLUSION

Both quick sort and merge sort are more efficient than the prevoius 3 basic sort algorithms: bubble sort, insertion sort and selection sort. Quick sort and merge sort adopt the concept of divide and conquer, using recursion to achieve better performance.

If you found this article not accurate or encountered some other issues, please feel free to drop me a line or email me Kami Ka-kei Lam

EXTERNAL RESOURCES

Merge sort - Wikipedia

Quicksort - Wikipedia