Insertion Sort and Bubble Sort

Bubblesort is a sorting algorithm which compares adjacent elements and swaps them if they are in the wrong order.¹ In this example, let’s iterate on the input list until it completes one pass without any swaps:

const sort = function(items) {
     let isSorted = false;
     while (!isSorted) {
         isSorted = true;
         for (let i = 0; i < items.length - 1; i++) {
             if (items[i] > items[i+1]) {
                 let itemsITemp = items[i];
                 items[i] = items[i+1];
                 items[i+1] = itemsITemp;
                 isSorted = false;
             }
         }
     }     
     return items; 
}

Insertion sort is a sorting algorithm which can be instantiated with two nested loops and for which we can break out of the inner loop but not the outer loop when we know a portion of the array is already sorted and we don’t need to iterate through the rest of it.

In terms of its behavior on the input list, insertion sort starts counting on a narrow range of values: the subarray which begins as a single array element with bounds called i and j to indicate the current range of array elements, and within which insertion sort places the next value at i + 1 in its proper location. The pointer at j has maximum bound i.²

function sort(items) {
     let length = items.length;
     for (let i = length - 1; i >= 0; i--) {
         //Number of passes
         for (let j = length - i; j > 0; j--) {
             //Compare the adjacent positions
             if (items[j] < items[j - 1]) {
                 //Swap the numbers
                 let tmp = items[j];
                 items[j] = items[j - 1];
                 items[j - 1] = tmp;
             } else {
               break;
             }
         }
     }
     return items;
}

This function responds to the original task of sorting an array of integers by looping j through an ever-increasing set of elements. Through continual swapping with the adjacent element and until it can no longer be swapped, each element follows j’s current range of indices. At this point because the rest of the array is already sorted, the element has reached its proper location which is not checked for in the original function. Because of this structure, if swapping doesn’t occur it means that the element has already reached its brilliant destination, so then we should break if no more swaps are to be made. And if we want to sort it in decreasing order instead of increasing order then we should flip the comparison.

[1]: InterviewBit. Bubble Sort
https://www.interviewbit.com/tutorial/bubble-sort/

[2]: Toptal. Sorting Algorithms Animations
https://www.toptal.com/developers/sorting-algorithms