Possibly bubble sort algorithm

Question

I'm trying to figure out what to call this sorting algorithm:

function sort(array) {
  array = array.slice();

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

  return array;
}

console.log(sort([8, 4, 5, 2, 3, 7]));

I wrote it while trying to figure out bubble sort which is a lot different. Tho will have slightly the same running time as the actual bubble sort. I might be wrong :(

Answer 1

To me, that's exactly Bubblesort: it takes care the largest element moves to the end of the array, and then operates on length-1 elements.

Edit: this does look quite similar to Bubblesort, but - as a diligent reader noticed - is not quite Bubblesort, as the algorithm does not compare (and swap) adjacent elements (which indeed is the main characteristic of Bubblesort). If you replace array[j] > array[i] with array[j] > array[j+1], you will get Bubblesort.

This implementation will fail if less than two input elements are given (0 or 1) - hint: the array is already sorted in these cases (just add an if).

A small improvement would be to add a flag in the i loop which records if any swapping happened at all - the outer for loop may terminate if the inner loop didn't perform any swaps. (Time) performance of Bubblesort is considered to be awful in comparison to other algorithms, but it must be noted it's the fastest algorithm on an already sorted array - if you add that flag ;)

Answer 2

It's not even obvious at a glance that your algorithm really sorts all inputs correctly. In fact, it does, but proving that takes a bit of thought.

The key insight is that, at the end of each iteration of the outer loop, the elements at positions from 0 to i will be sorted correctly:

for (let i = 0; i < array.length; i++) {
  for (let j = 0; j < array.length - 1; j++) {
    if (array[j] > array[i]) {
      [array[i], array[j]] = [array[j], array[i]]
    }
  }
  // Invariant: here array[0] to array[i] will be correctly sorted!
}

In particular, this invariant will obviously be true at the end of the first iteration, when i == 0. It is then not hard to inductively show that, if this was true at the end of the previous iteration, then it will remain true (with i now one greater than before) after the next one as well. Thus, at the end of the last iteration, with i == array.length - 1, the whole array will be correctly sorted.

---

Actually, to achieve this, we only need to iterate the inner loop up to j == i - 1; the iteration with i == j obviously does nothing useful, and any later iterations of the inner loop have no effect on the invariant. (Those iterations can only swap the element currently at index i with a larger one from the tail end of the array, which will still leave array[i] greater than or equal to all its predecessors.) So we can speed up your algorithm by only iterating the inner loop until j == i:

for (let i = 0; i < array.length; i++) {
  for (let j = 0; j < i; j++) {
    if (array[j] > array[i]) {
      [array[i], array[j]] = [array[j], array[i]]
    }
  }
  // Invariant: here array[0] to array[i] will be correctly sorted!
}

With this optimization, your algorithm can be recognized as a form of insertion sort.

---

It's generally not the most efficient form of that algorithm, though, since the inner loop does the insertion of array[i] into its correct position somewhat inefficiently. A somewhat more efficient implementation would be something like this:

for (let i = 1; i < array.length; i++) {
  let j = i, temp = array[i];
  while (j > 0 && array[j - 1] > temp) {
      array[j] = array[j - 1];
      j--;
  }
  if (j < i) array[j] = temp;
  // Invariant: here array[0] to array[i] will be correctly sorted!
}

By running the inner loop "backwards" we can stop it as soon as we find an element that's ranked lower than the one we're inserting (thus avoiding lots of needless comparisons, especially if the input array is already mostly sorted), and by saving the element to be inserted in a temporary variable, we can replace the swaps with simple assignments.

The if (j < i) part of the code above is not really necessary, since if j == i, assigning temp back to array[i] would have no effect. That said, it's generally a useful optimization if integer comparisons are cheaper than array assignments, which is usually the case. The same goes for starting the outer loop from let i = 1 instead of let i = 0; the iteration with i == 0 does nothing anyway, so we can safely skip it!