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

— Bubble sort, Insertion sort and Selection sort

Comparison between 5 types of sort algorithms and their performance

As a developer, doing real life projects is crucial but having strong foundation in algorithms is definitely a plus. Algorithm is a set of instructions for the system to perform a computation. To have strong foundation in algorithms, one can write code to solve various problems in a more effective and mainly, maintainable way without creating spaghetti code.

In this article, using JavaScript, I will focus on sorting algorithms, in particular quick sort, selection sort, insertion sort, quick sort and merge sort. These few types are listed in FreeCodeCamp as most frequently used in job interviews, compared with other types.

BUBBLE SORT

Bubble sort is one of the simplest sorts, yet rarely practiced in real world for its poor performance. It iterates the list from the first element, comparing the current one with the next one and swap them if needed. Then, it will iterate the list over and over again in the same manner until no more swap is needed. The name “bubble” is used for this sort because the largest element is eventually bubbled up to the end of the list.

Summary of steps:

1. Loop through the list, compare one element with its adjacent element.
2. Swap when needed.
3. Repeat 1 until no swap is needed.

Bubble sort

Example I

This example is literally reflecting the aforesaid summary.

First, we declare a variable (“swapped”) potentially for boolean value, to check if any swaps are needed in the loop we are going to perform.

Second, we create a do/while loop for a single purpose, to reset “swapped” as false (if it was assigned true from previous iteration), so the execution of the inner code block can be stopped when no swap is needed (i.e. as the argument for while loop will be falsy).

Third, inside the do/while loop, we start iterate the whole array (we used for loop here, but it can be another while loop). Then, we put a logic to check if swap is needed for the element concerned, and do it when needed. If swapped is performed, “swapped” will switch to true —indicating the need for another round of for loop.

function bubbleSort(array) {
  let swapped; //setup an indicator as an argument for while loop
  do {
    swapped=false; //reset the indicator to be false
    for (let i=0;i<array.length;i++) {
      if (array[i] > array[i+1]) {
        [array[i], array[i+1]] = [array[i+1], array[i]] //destructuring in ES6
        swapped = true; //switch the indicator to true to signal another loop
      } 
    }
  } while (swapped); //gatekeeper to prevent infinite loop
  return array;
}

Example II

In this example, we created a nested loop to treat each element of array as a sub-array. It is possibly less effective as it, without using any indicator, takes n2 to complete the whole checking even though the sort may have done before the end.

// Optional:
// Either create this function or using destructuring as example I
function swapping(a,b,array) {
  let temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}

function bubbleSort(array) {
  for (let i=0;i<array.length; i++) {
    for (let j=0;j<array.length; j++) {
      if (array[j]>array[j+1]) {
        swapping(j,j+1,array)
      }
    }
  }
  return array;
}

SELECTION SORT

Selection sort divides into 2 arrays: unsorted (input) and sorted ones. It first takes the minimum value of the unsorted one and assigns it to be the first place of the sorted one, and then second minimum the second place, and so on, until the unsorted array is empty.

For time complexity, selection sort is O(n2) for both best and worst cases, and in general perform worse than insertion sort (next case to look into), which is similar in operation.

Summary of steps:

1. Create an empty array for storing sorted array
2. Iterate the original unsorted array
3. Take the minimum value of element from the unsorted, and move it to the right side of the sorted
4. Until there is not any elements in the unsorted array

Selection sort

In Wikipedia or many other places, the suggested solution is similar to Example I as below:

Example I — standard

We first create a for loop to iterate the array. We also declare a variable (“min”) to store the value of the current index (“i”), presuming array[i] is the minimum value of the array.

Then, we create a nested loop, solely served to check if the presumed minimum value is bigger than any elements in the unsorted array. If yes, we update “min” (index of presumed minimum value of element) to “j” (index of current element of the inner loop).

• Note that the nested loop will get shorter along time as the positions on the left side of the current element should have been sorted.

Now, after the completion of nested loop, we finally perform swap — if “min ”is still “i”, there will not be any changes; if “min ”is updated, the position of current element of the outer loop will get swapped with the minimum value of the unsorted array.

function swapping(a, b, arr) {
  let tmp = arr[a];
  arr[a] = arr[b];
  arr[b] = tmp;
}

function selectionSort(array) {
  for (let i=0; i<array.length; i++) {
    let min=i;
    for (let j=i; j<array.length; j++) {
    //note that j=i instead 0, to exclude the left side of array
    //which should have been sorted
      if (array[min] > array[j]) min = j
    }
    swapping(i, min, array) //swap between array[i] and array[min]
}
  return array
}

Example II — with higher order functions

This example is less effective even compared with the standard solution, containing a loop with a higher order function, also mutating the original array (although the last concern can be avoided by creating a clone) but I consider it literally follows the summary of steps and therefore good as demonstration to grasp the concept.

First, we create 2 variables, one is the new empty array for storing sorted data, and the other one is to store the length of the unsorted array in its initial status.

Then, we create a while loop to check if the sorted array has the same length as the initial unsorted array. If yes, it means the sort is completed and it can return the sorted array.

Inside the while loop, we combine Math.min() and array.findIndex() to get the index of the minimum value of the unsorted array. Then, we push the value to the sorted array and use array.splice() to delete the value from the unsorted one (as it is an array instead of a set, index is needed for deletion).

As with array.splice(), the unsorted array will get shorted, meaning each round Math.min(…array) will return the next minimum value. Loop will stop once the sorted array collected all elements, having same length as the unsorted one in the beginning. The unsorted one, at this stage, should be empty.

function selectionSort(array) {
  const newArray = []
  const length = array.length;

  while (newArray.length < length) { //check if the sort is completed fully
    let min = array.findIndex(e=>e==Math.min(...array))
    newArray.push(array[min]) //push the min to the new array
    array.splice(min,1) //** mutation, delete the min from original array
  }
  return newArray;
}

INSERTION SORT

Insertion sort may not be as efficient as more advanced sort algorithms but it is simple, stable and still more efficient than Bubble sort or Selection sort, stable and can perform simultaneously when it is still receiving data. In fact we are mostly practicing it when playing poker cards.

Summary of steps:

1. Iterate the array, and suppose the left side of the current element is sorted
2. Compare the current element with the next one
3. If current element is less than the next one, skip the current element to the next.
4. If current element is greater, start loop through the left side of current element, from right to left
5. Insert the concerned element when it encounter an element smaller than it.

Insertion sort

Example

To implement insertion sort, a very important step is to create a variable (“curr”) to store the value of current index concerned, just like temp in function swapping(a,b,array). This is because the elements on the left side will shift to the right and as consequence, the value at the concerned index will be updated.

After then, we compare if the value of curr (again, not array[i]) is greater than its previous element. Keep moving it towards the start of array until it encounters an element less than it. Insert it on the spot.

function insertionSort(array) {
  for (let i=1; i<array.length;i++) {
    let curr = array[i]; //!IMPORTANT: store the value aside
    let j=i-1;

    while (j>=0 && array[j]>curr) { //if previous element is smaller than current, skip the while loop
      array[j+1]=array[j] //shift the elements toward the rightside
      j--;
    }
    array[j+1]=curr //insertion, if iteration is skipped, should be the same position
  }
  return array;
}

TLDR;

Bubble sort, selection sort and insertion sort are inside the box of simple sorting and considered less efficient in general cases (there are exceptional scenarios which, for example insertion sort may have better performance).

Bubble sort concerns the one next to it for comparison each time and therefore requires multiple loops (n2) to complete the sorting in the worst case. Selection sort always compares all elements of unsorted side to get the minimum value which will be selected. Insertion sort compares the current value with the left side of array, starting with the most adjacent one, and stop the shifting whenever the condition is fulfilled and insert into the right place.

NEXT PART

In the next article I will compare the more advanced sort algorithms — quick sort and merge sort.

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

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

Sorting algorithm - Wikipedia

freeCodeCamp.org