Bubble Sort with for loop не работает должным образом - PullRequest
Новая
       36

Bubble Sort with for loop не работает должным образом

1 голос
/ 21 июня 2019

Я только начал писать алгоритмы сортировки. В настоящее время я изучаю алгоритм Bubble Sort, я нашел в сети следующее, и он работает нормально: 

const arr = [3, 2, 6, 9, 3, 5];

const bubbleSort = array => {
  do {
    var isSorted = true;
    for (var i = 0; i < array.length; i++) {
      if (array[i] > array[i + 1]) {
        var temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        isSorted = false;
      }
    }
  } while(!isSorted)
  return array
};

Выход: 

[ 2, 3, 3, 5, 6, 9 ]

Однако, когда я пытаюсь написать его, используя оператор if вместо цикла while, как показано ниже, он не работает должным образом: 

const arr = [3, 2, 6, 9, 3, 5];

const bubbleSort = (array) => {
  let isSorted = false;
  if(!isSorted) {
    isSorted = true;
    for(var i = 0; i < array.length; i++) {
      if (array[i] > array[i + 1]) {
        var temp = array[i + 1];
        array[i + 1] = array[i];
        array[i] = temp;
        isSorted = false;
      }
    }
  }
  return array;
}

Выход: 

[ 2, 3, 6, 3, 5, 9 ]

Что я здесь не так делаю?

Ответы [ 2 ]

1 голос
/ 21 июня 2019

Нам нужен цикл while для пузырьковой сортировки.

Если мы удалим while, мы будем «пузыриться» только один раз по всему массиву. Например, если 

[3, 2, 6, 9, 3, 5];

здесь 3 (первый элемент) больше 2 (второй элемент), поэтому мы поменяли их местами, и теперь у нас есть 

[2, 3, 6, 9, 3, 5]

Когда мы продолжаем цикл for, мы приближаемся к 3 (6-й элемент), который меньше, поэтому мы заменяем его на 9 (5-й элемент). И продолжайте вперед. 

[2, 3, 6, 3, 9, 5]

отсюда мы только пойдем вверх, но мы можем проанализировать ситуацию. Мы можем видеть, что 3 (4-й элемент) меньше, чем 6 (третий элемент), но цикл for находится далеко вперед, поэтому мы не окажемся в ситуации, когда мы поменяем его с большим элементом. Таким образом, мы должны начать «пузыриться» снова с самого начала, и мы должны делать это, пока все не будет отсортировано. Это произойдет, когда нечего поменять, потому что мы устанавливаем isSorted=false всякий раз, когда мы меняемся. После сортировки массива мы сделаем последний проход, где проверим каждую соседнюю пару, и если все они отсортированы, обмен не произойдет, и isSorted будет true

TLDR; нам нужен while, потому что для «всплытия» может потребоваться несколько проходов через массив.

0 голосов
/ 21 июня 2019

цикл while - это простой способ реализовать Bubble Sort, в противном случае вам потребуется алгоритм O (n²) с вложенными циклами for, операторы if else не будут работать: 

const arr = [3, 2, 6, 9, 3, 5];
const bubbleSort = array => {
    var length = array.length;
    //Number of passes
    for (var i = 0; i < length; i++) { 
        //Notice that j < (length - i)
        for (var j = 0; j < (length - i - 1); j++) { 
            //Compare the adjacent positions
            if(array[j] > array[j+1]) {
                //Swap the numbers
                var tmp = array[j];  //Temporary variable to hold the current number
                array[j] = array[j+1]; //Replace current number with adjacent number
                array[j+1] = tmp; //Replace adjacent number with current number
            }
        }        
    }
    return array
}
bubbleSort(arr)
// expected output: [2, 3, 3, 5, 6, 9]

Вы также можете увидетьПсевдокод Bubble Sort здесь: Алгоритм Bubble Sort

...