Question

Compare and Contrast Bubble Sort with Merge Sort. Discuss about the efficiency of both.

Answer 1

Bubble Sort: A Comparison Algorithm

Bubble Sort takes an iterative approach — looping through elements in a matrix-like fashion — to sorting, and is a great place to start with implementing your first sorting algorithm.

Here’s how it works: given an unsorted array, for the full length of that array, we pass over each element; comparing it with the element next to it. If the first element is larger than the second, we swap the two elements.

This creates a “bubbling” effect, where the smallest elements (in our case

numbers) migrate their way to the front of the list with every pass.

As I mentioned earlier, using helper functions to implement bubble sort makes the code more readable, so I’ll start with implementing those:

A Pair-wise comparator function . First, we’ll define a pure helper function — a function that that takes in input and gives us output without changing anything — called inAscendingOrder. This function will take two elements in a given array, compare them, and return a boolean based on the result.

code:

//let's call it inAscendingOrder
var inAscendingOrder = function(array, index) {
  //check edge case for end of array, since it won't have a neighbor to compare to
  if(index === array.length - 1) return true;
  //will return a truthy value if consecutive items are in proper ascending order
  return array[index] < array[index + 1];
};

A swapping function

Next, we’ll define a function that swaps two elements in a list. We can’t call this a pure function. Why? Because it will actually have an effect on the external scope (our bubble sort implementation) when we use it later on.

code:

var swap = function(array, index) {
  //create a variable that points to the same value as the current index
  var tmp = array[index];
  //point the current index to the value of its next index
  array[index] = array[index + 1];
  //point that next index to the value saved in our temporary storage
  array[index + 1] = tmp;
  //now the two elements in the array are swapped out!
};

The actual bubble sort implementation

And finally, we want to define the actual bubble sorting algorithm.

Before I bring in the code, I want to mention a couple of things that might be helpful to understand:

(1) I’m going to be using the concept of “state”, which basically means my function will keep metadata on itself, and let us know when it finishes sorting the input array;

(2) I’m going to pass through the array backwards. What does this mean? Well, we use nested loops to implement bubble sort. The outer loop handles the direction and length of our passes, so I’ll start my loop from the last element of the array and work my way to index 0. Why are we looping backwards? This makes it so that the inner for loop, the loop that will be handling the swapping, requires less work to do its job; avoiding the added task of passing

over elements it has already sorted. Hopefully, you’ll see what I mean below:

code:

var bubbleSort = function(arr) {
  //initialize a flag variable to help indicate whether the arr is sorted or not (state)
  var sorted = false;

  //how nested for loops work:

  //(in this case, looping backwards,) passing over our array until it's sorted,
  for(var i = arr.length; i > 0 && !sorted ; i--){

    //we'll toggle the state of our sorted flag to be true for each pass
    sorted = true;

    //with each element in the array
    for(var j = length; j > i; j++){
      //do the following:

      //check if each element is in proper descending order, if not...
      if(!inAscendingOrder(arr, j)) {
        //use helper function to swap elements
        swap(arr, j);

        //and since we had to swap, we know it's not sorted yet, so toggle state back to false...
        sorted = false;
      }
    }
  }

  //return array
  return arr;
};

Merge Sort: A Recursive Sorting Algorithm

Merge Sort, on the other hand, takes a divide-and-conquer approach to sorting; recursively breaking the input array down until we have sorted tuple-sized subarrays that we can then merge back together at the end.

I’ll also use helper functions in implementing merge sort (again, to keep the code declarative):

A split helper function

code:

function split(arr) {
  var middle = array.length / 2;
  var left = array.slice(0, middle); //won't include the end point passed
  var right = array.slice(middle);
  return [left, right]; //returns tuple of split arrays
}

A merge helper function

code:

function merge(left, right) {
  var merged = [],//setup empty storage for our merging
  leftIndex = 0,  //initialize vars to help point to current index in left && right subarrays
  rightIndex = 0;


  while(leftIndex < left.length && rightIndex < right.length) { //iterate through both subarrays
    if(left[leftIndex] < right[rightIndex]) { //if left element > than right at sameIndex
      merged.push(left[leftIndex]); //push the lesser of the two into our merge storage
      leftIndex++; //move left index pointer over one (keeps things linear)
    } else { //otherwise
      merged.push(right[rightIndex]); //if right element >, push that one to merge storage
      rightIndex++;  //move right index pointer over one
    }
  }

//in the case of inbalanced subarrays, one of these for loops will be triggered
//pushes all of the remaining values of the longer array into merge storage
//if our split function works well, we'd only be passing over a couple (if not only one) element
  for(; leftIndex < left.length; leftIndex++) merged.push(left[leftIndex]);
  for(; rightIndex < right.length; rightIndex++) merged.push(right[rightIndex]);

  return merged; //return subarrays merged

}

Note: in analyzing the code, you might be wondering: wait, why didn’t she just use javascript’s built-in shift method to implement this merge function. That’s because using shift would require more work of our algorithm, having to pass over every element and shift each over one, thereby slowing things down. To optimize efficiency of mergeSort, we’ll want to keep this as a linear operation (more on this later).

And finally, here’s our recursive merge sort solution that utilizes both helper functions…

code:

function mergeSort (arr) {
  if(arr.length < 2) return arr; //base case
  var splits = split(arr), //(1)split the array with helper function
    leftArr = splits[0], //(2)store left subarray in var
    rightArr = splits[1];//(3)store right subarray in var
  return merge(mergeSort(leftArr), mergeSort(rightArr)); //merge sorted subarrays
}

Comparing Bubble Sort and Merge Sort: Time-Complexity Analysis

So why choose one over the other?

Both have their pros and cons, but ultimately bubble sort quickly becomes less efficient when it comes to sorting larger data sets (or ‘big data’). Where as, Merge Sort becomes more efficient as data sets grow.

This makes more sense once you familiarize yourself with Big-O Notationand the concept of time complexity. What’s time complexity? Basically, we use time complexity to analyze the performance of an algorithm, or how long it takes to solve the problem for a given input. Here’s a cheat sheet to help you dig deeper into this.

At best, with smaller data sets, bubble sort has O(n), and worst case scenario, it has O(n²) time complexity (which is pretty bad).

On the other hand, merge sort performs pretty consistently, with a time complexity of O(n log(n)). The time complexity of our helper functions for merge sort make this possible.

There are many more sorting algorithms to explore, and I hope this helps others venturing into software engineering, machine learning, and other disciplines get a better understanding of the two most popular ones.

// Thank you