Почему количество итераций неправильно с этим генератором доходности в JavaScript?

Question

Вот фрагмент кода, с которым я пытаюсь работать.

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

Это простая реализация сортировки пузырьков. Как вы знаете, пузырьковая сортировка имеет n * (n - 1) / 2 итерации, поэтому в данном случае длина массива равна 7, у нас есть 7 * (7 - 1) / 2 итерации, которая равна 21,

Но когда я запускаю этот код, я получаю только 11 итераций. Вывод как показано ниже.

{ 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 }

я использую node test.js запустить эту программу (test.js - это файл, в котором написана эта программа).

Примечание: я не хочу печатать массив после каждой итерации. Я хочу вернуть это. Если это поможет.

Answer 1

Ваша главная проблема в том, что вы звоните next дважды, но игнорируя value от любого другого звонка. Вместо этого, позвоните один раз и запомните результат:

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

... вернее, используйте for-of (что означает, что вам не нужно иметь genForLoop идентификатор):

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

Но (я не делал пузырьковую сортировку в течение многих лет), я считаю, что ваше завершение внутреннего цикла должно быть j < arr.length - 1, не просто j < arr.length - i - 1, Я смутно напоминаю, что внутренняя петля может быть короче, но не так.

Живой пример:

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

Ваше состояние внешней петли должно быть < arr.length не < arr.length - 1,