CODEWITHSUNDEEP
javascriptsortingbubble-sort
pi2018
pi2018

Reputation: 357

Is this implementation of bubble sort wrong?

Instead of using the usual do-while loops for sorting, if we use 2 for loops, would that be okay?

let bubbleSort = (arr) => {
    console.log(arr);
    for(let i=0; i<arr.length; i++) {
        for (j=0; j<arr.length; j++) {
            if (arr[j] > arr[j+1]){
                console.log("swapped (i,j)->", arr[j],arr[j+1])   
                let temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;

            }
        }
    }

    return arr

}

This returns the correct sorted array but is it any better than the do-while loop. Both are O(n^2) time-complexity.

Upvotes: 3

Views: 201

Answers (1)

ggorlen
ggorlen

Reputation: 57096

All loop types do, while and for are equivalent. They're just syntactic sugar for the programmer and ultimately boil down to the same thing at runtime.

What you've posted here is a mostly correct implementation of bubble sort, but there are a few points of improvement available:

  • Bug: the code is accessing an out of bounds index in the inner loop: iterate to j < arr.length - 1 instead of j < arr.length because of the arr[j+1] statement. Most languages will crash or exhibit undefined behavior for an out of bounds array access, but JS just compares the value against undefined and carries on.

  • Potential bug: the inner loop creates a global j variable in the inner loop (thanks to Kaiido for pointing this out). This variable's value will persist beyond this function and might cause unexpected behavior elsewhere in the program. Declare variables with let (or const if the variable shouldn't be reassigned) to ensure that they are scoped locally to the block.

  • After the first iteration of the outer loop, the rightmost element in the array is in its final and sorted location (because it's the largest element in the array). After the second iteration of the outer loop, the last two elements of the array are in their final sorted positions. And so on. Therefore, we can shorten the number of iterations of the inner loop as follows: j < arr.length - 1 - i.

  • If on any iteration no swaps were performed, we can break--the array is already sorted.

These optimizations don't improve the time complexity, which is O(n2) as you say, but they're worth thinking about, as similar optimization approaches can help speed up real-world sort routines.

A few style points to consider:

  • Use spacing between operators (unless they're in []s).
  • Consider using a destructuring assignment to avoid the temp variable when swapping values. As pointed out in the comments, this has a performance penalty due to the overhead of array object creation per swap, so it should be compiled out in a production build (although bubble sort wouldn't be appropriate in production anyway).
  • Be consistent with semicolons and vertical spaces.

Here's a possible re-write:

const bubbleSort = arr => {
  for (let i = 0; i < arr.length; i++) {
    let swapped = false;
    
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
        swapped = true;
      }
    }
    
    if (!swapped) { break; }
  }

  return arr;
};

for (let i = 0; i < 10000; i++) {
  const arr = Array(100).fill().map(e => ~~(Math.random() * 30));
  const expected = JSON.stringify(arr.slice().sort((a, b) => a - b));
  const actual = JSON.stringify(bubbleSort(arr.slice()));
  
  if (actual !== expected) {
    throw new Error(`test failed: expected ${expected} but got ${actual}`);
  }
}

console.log("10000 tests passed");

Fun follow-up exercises:

  • Write it without loops, using recursion.
  • Allow the user to pass a custom comparator function, similar to the builtin Array#sort. This way, you can sort arrays of objects or specify the order of the sort.
  • Benchmark it against other sort routines using console.time (thanks to Medet for the idea). How much do the optimizations help? Look into using seeded random numbers for your tests.

Upvotes: 4

Related Questions