bubble sort algorithm with nested loops performs better than with one loop JS

Question

Here are 2 bubble sort algorithms:

1:

function bubbleSort(array) {

  let i = 0;
  let startVal = array[i];
  let comparingVal = array[i + 1];
  let iterations = array.length;

  while (iterations > 0) {

    if (comparingVal === undefined) {
      i = 0;
      startVal = array[i]
      comparingVal = array[i + 1]
      iterations--;

    } else if (startVal > comparingVal) {
      array[i] = comparingVal;
      array[i + 1] = startVal;
      startVal = array[i + 1];
      comparingVal = array[i + 2];
      i++;

    } else {
      startVal = array[i + 1];
      comparingVal = array[i + 2];
      i++;
    }
  }
  return array;
}

2:

function bubbleSortTwo(array) {
  const length = array.length;
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length; j++) {
      if (array[j] > array[j + 1]) {
        //swap
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
}

when tested in the browser using performance.now() Web API bubbleSortTwo yielded faster performance time even though there is a nested loop O(n^2) whereas bubbleSort only has one loop for which I would assume a time complexity of O(n). Why is this? Or am I missing something somewhere? (I am new to ds and algs so excuse my ignorance I am trying to learn)

The two functions presented have the same time complexity n^2 as you compare each of n items against all n items. The performance difference is due to the code path of the second being simpler than the other. — Blindman67
– Blindman67, Commented May 27, 2022 at 20:07
(@Blindman67 you compare each of n items against all n items um - only if the input is in reverse order. In an ordered array every item is compared to its neighbours, only. Time and again…) — greybeard
– greybeard, Commented May 28, 2022 at 8:58
@greybeard Add a counter to the inner while loop. For 100 items it counts 100 * 100 iterations. — Blindman67
– Blindman67, Commented May 28, 2022 at 21:24

3 revs · Accepted Answer · 2022-05-28 08:59:51Z

There are four instances of

    startVal = array[i + c]
    comparingVal = array[i + 1 + c]

in 1 (for c 0 or 1).
Don't Repeat Yourself:

/**
 * Sort array in-place.
 * @return array
 */
function bubbleSort(array) {

  let iterations = array.length, i = 0;
  let startVal, comparingVal;

  while (iterations > 0) {
    startVal = array[i];
    comparingVal = array[i + 1];
    if (comparingVal === undefined) {
      i = 0;
      iterations--;
    } else {
      if (startVal > comparingVal) {
        array[i] = comparingVal;
        array[i + 1] = startVal;
      }
      i++;
    }
  }
  return array;
}

Generally, the assumption that every loop nesting level adds a factor of n is not valid.
There is reason to it where each loop is iterated cn times for some constant c… which is not the case in 1: i gets reset to 0 iterations times.

(dropping the redundant assignment to startVal from

      array[i + 1] = startVal;
      startVal = array[i + 1];

leads to another interpretation of bubblesort:
Where the next value is smaller, "take out" the bigger one.
Keep moving values down while smaller.
Put the value once bigger back in.
)

Stack Exchange Network

bubble sort algorithm with nested loops performs better than with one loop JS

1 Answer 1

You must log in to answer this question.

Hot Network Questions

bubble sort algorithm with nested loops performs better than with one loop JS

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions