let swapFun = (arrToSwap, indexFir, indexSec) => {
let temp = arrToSwap[indexFir]
arrToSwap[indexFir] = arrToSwap[indexSec]
arrToSwap[indexSec] = temp
}
let insertionSort = (arr, n = 0) => {
if (n === arr.length) {
return arr
}
for (let i = 1; i < arr.length; i++) {
while (arr[i - 1] > arr[i]) {
swapFun(arr, i - 1, i)
}
}
insertionSort(arr, n + 1)
return arr
}
console.log(insertionSort([5, 4, 33, 2, 8]))It is actually Bubble Sort, but it is a bad implementation of Bubble Sort.
If you notice the for loop:
for (let i = 1; i < arr.length; i++) {
while (arr[i - 1] > arr[i]) {
swapFun(arr, i - 1, i)
}
}
it basically iterates the array, starting from index 1, to the end of the array, and for each item, it compares the item with the previous item. The comparison is made in the while loop, but it actually is not a loop (it just executes the body if item at index i-1 is bigger than item at index 1.) It can be replaced with a if statement:
for (let i = 1; i < arr.length; i++) {
if (arr[i - 1] > arr[i]) {
swapFun(arr, i - 1, i)
}
}
The for loop is executed in total n-1 times, because n=0 at the start and gets incremented each time the function gets called recursively, until it reached n=array length (this time the for loop will not be executed.) The body of the for-loop gets executed array.length-1 times (4 times in your example).
The biggest problem with this implementation, is the use of Recursion, which will use more Space (because Recursion uses a Stack). It also is not optimized regarding Time. Even if the array was already sorted, the for loop would be executed N-1 times, and its body will also be executed N-1 times. Which means that even in the Best Case (array is already sorted), this Bubble sort would have O(n^2) Time complexity, when in fact it can be O(n).
The optimized version of Bubble Sort:
const sort = array => {
let isSorted;
for (let i=0; i < array.length; i++) {
isSorted = true;
for (let j=1; j < array.length - i; j++)
if ( array[j] < array[j-1]) {
swap(array, j, j-1);
isSorted = false;
}
if (isSorted)
return;
}
}
const swap = (array, index1, index2) => {
let temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
const array = [5, 4, 33, 2, 8]
sort(array);
console.log(array);
The variable "isSorted", keeps track if array is Sorted or not. If no swaps were made, it means array is sorted, and I can stop the execution of the function. Also note that in the inner loop: for (let j=1; j < array.length - i; j++) , we do not check the items at the "sorted part" (each time the inner loop if executed, one item goes to it's "final" index in the array and we do not need to make any comparisons with these items).
Hope this helped! Please ask if I did not explain something properly.