javascriptiterationgeneratorbubble-sortyield-keyword

Why are the number of iterations wrong with this yield generator in javascript?


So here is a code snippet that I am trying to work with.

function* genBubble(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      yield arr; // returning arr after every iteration
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1); // removed swap for brevity
      }
    }
  }
}
const tempArray = [3, 5, 8, 4, 1, 9, -2];
const genForLoop = genBubble(tempArray);

do {
  console.log(genForLoop.next());
} while (!genForLoop.next().done);

This is a simple bubble sort implementation. As you know bubble sort has n * (n - 1) / 2 iterations, so in this case with array's length being 7, we have 7 * (7 - 1) / 2 iterations which is equal to 21.

But when I run this code, I am only getting 11 iterations. The output is as shown below.

{ value: [ 3, 5, 8, 4, 1, 9, -2 ], done: false }
{ value: [ 3, 5, 8, 4, 1, 9, -2 ], done: false }
{ value: [ 3, 5, 4, 1, 8, 9, -2 ], done: false }
{ value: [ 3, 5, 4, 1, 8, -2, 9 ], done: false }
{ value: [ 3, 4, 5, 1, 8, -2, 9 ], done: false }
{ value: [ 3, 4, 1, 5, 8, -2, 9 ], done: false }
{ value: [ 3, 4, 1, 5, -2, 8, 9 ], done: false }
{ value: [ 3, 1, 4, 5, -2, 8, 9 ], done: false }
{ value: [ 1, 3, 4, -2, 5, 8, 9 ], done: false }
{ value: [ 1, 3, -2, 4, 5, 8, 9 ], done: false }
{ value: [ 1, -2, 3, 4, 5, 8, 9 ], done: false }

I am using node test.js to run this program(test.js is the file where this program is written in).

Note: I do not want to print the array after each iteration. I want to return it. If that helps.


Solution

  • Your main problem is that you're calling next twice, but ignoring the value from every other call. Instead, call it once and remember the result:

    let result;
    while (!(result = genForLoop.next()).done) {
      console.log(result.value.join(","));
    }
    

    ...or rather more simply, use for-of (which means you don't have to have the genForLoop identifier):

    for (const value of genBubble(tempArray)) {
      console.log(value.join(","));
    }
    

    But (I haven't done a bubble sort in years) I believe your inner loop termination needs to be j < arr.length - 1, not just j < arr.length - i - 1. I do vaguely recall that the inner loop can be shorter, but not apparently in that way.

    Live Example:

    function swap(arr, i1, i2) {
      const t = arr[i1];
      arr[i1] = arr[i2];
      arr[i2] = t;
    }
    function* genBubble(arr) {
      for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1; j++) {
          yield arr; // returning arr after every iteration
          if (arr[j] > arr[j + 1]) {
            swap(arr, j, j + 1); // removed swap for brevity
          }
        }
      }
    }
    const tempArray = [3, 5, 8, 4, 1, 9, -2];
    
    for (const value of genBubble(tempArray)) {
      console.log(value.join(","));
    }
    .as-console-wrapper {
      max-height: 100% !important;
    }

    Your outer loop condition should be < arr.length, not < arr.length - 1.