0

I found this implementation of insertion sort that avoids using the typical while loop that I've seen across most video explanations. I'm not exactly sure if this is valid though. Wouldn't this be nearly identical to bubble sort? Would there really be any specific benefit of using this? Here are my implementations of insertion sort and bubble sort:

let arr = [1, 4, 6, 7, 8, 6, 3, 4, 5, 6, 6, 7];

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

const insertSort = (array) => {
  for (let i = 1; i < array.length; i++) {
    for (let j = i; j > 0; j--) {
      if (array[j] < array[j - 1])
        [array[j - 1], array[j]] = [array[j], array[j - 1]];
    }
  }
};


1 Answer 1

2

Your bubble sort implementation is not really bubble sort - rather, it is, as you noticed, essentially the same as your insertion sort implementation.

With bubble sort, you iterate through the list and swap adjacent elements, changing the indicies being compared each time - and when you get to the end, you start over from the beginning of the array and do it again, and so on, until it's sorted. (Nice visualization.) That's not what you're doing.

With insertion sort, you have a completely sorted portion of the array, and an untouched portion of the array, taking elements from the untouched portion and putting them in the right position in the sorted portion before proceeding with the next unsorted item. (Nice visualization.) That's what you're doing in both implementations here.

Would there really be any specific benefit of using this?

No. Both sorting algorithms are far inferior to merge sort (and its variants). If you need to sort an array, the best way by far would be to use the built-in .sort function, which implements merge sort under the hood, and is much faster than any sorting algorithm you could write on your own in JavaScript.

1
  • Thank you for the great answer! I didn't know that's how .sort worked under the hood. Jan 28, 2022 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.