Нужна помощь в понимании синтаксиса / логики в решении Ruby Bubble sort

Question

Мне нужна помощь в понимании некоторых синтаксиса и логики в этом программном решении.

def bubble_sort(arr)
  sorted = false
  until sorted
    sorted = true
    (arr.count - 1).times do |i|
      if arr[i] > arr[i + 1]
        arr[i], arr[i + 1] = arr[i + 1], arr[i]
        sorted = false
      end
    end
  end

  arr
end

В частности, у меня были некоторые проблемы с пониманием until петля и sorted = true а также sorted = false, Я кое-что прочитал здесь, и думаю, что получу, если в массив все еще нужно внести изменения, sorted устанавливается на false и цикл продолжается. Но я был бы признателен, если бы кто-то мог объяснить мне это просто еще раз.

Похоже, цикл times выполняется только один раз для каждого элемента массива минус один, а затем меняет позиции. Как цикл до играет в этом?

Answer 1

.times цикл делает один проход по массиву, сравнивая каждый элемент с его соседом и меняя их местами, если они находятся в неправильном порядке.

Внешний until sorted цикл повторяет этот процесс, пока ничего не изменится. На данный момент массив отсортирован.

sorted записи переменных, поменялись ли мы элементами во время нашего последнего прохода по массиву. Если мы это сделали, массив изменился, и мы еще не закончили. С другой стороны, если никакие элементы не были поменяны местами, sorted = false не выполняется, sorted остатки trueи мы можем выйти из внешнего цикла.

Answer 2

Вы правы в том, что он выполняет итерацию по массиву, проверяя значения и меняя местами, если это необходимо - если в этом процессе вообще произошла перестановка, он считает массив не отсортированным и устанавливает sorted = false. Если это так, то цикл до будет гарантировать, что в массиве произойдет новый проход, чтобы снова повторить процесс. Единственный раз, когда цикл "до" останавливается, это когда не было ни одного свопа во время прохода. В начале каждого до тех пор, пока цикл sorted не будет установлен в true, потому что он предполагает, что это будет последний проход - если не сделан обмен, который устанавливает sorted = false, тогда он будет выполнять как минимум еще один проход.

Проверьте http://visualgo.net/sorting.html если вы хотите аккуратную анимацию, чтобы визуализировать, что происходит в различных алгоритмах сортировки.