4
\$\begingroup\$

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 :(

\$\endgroup\$
4
\$\begingroup\$

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 ;)

\$\endgroup\$
  • 1
    \$\begingroup\$ So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks! \$\endgroup\$ – Ademola Adegbuyi Apr 7 at 16:36
  • 1
    \$\begingroup\$ No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code. \$\endgroup\$ – 200_success Apr 7 at 16:53
  • \$\begingroup\$ @200_success you are absolutely right - about to edit my answer :) \$\endgroup\$ – jvb Apr 7 at 17:58
  • \$\begingroup\$ @200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in. \$\endgroup\$ – Ilmari Karonen Apr 7 at 23:32
2
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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