Bubble sort solution explanaition

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 

Я имею немного трудно понять, что термин «отсортированный» делает здесь. Я знаю, что есть метод .sort, но я не смог найти какой-либо отсортированный метод, и не совсем ясно, как цикл знает, как закончить.

Может кто-нибудь объяснить немного больше, что происходит с термином «отсортировано»?

Answer 1

sorted - это логическая переменная, которая используется для указания того, завершена ли сортировка или нет.

Изначально sorted имеет значение false (при условии, что массив еще не отсортирован). Условие входа в основной (внешний) цикл проверяет, является ли значение sorted истинным или ложным, и, как вы можете видеть, цикл продолжается до тех пор, пока значение sorted не будет истинным.

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

Только в том случае, когда внутренний цикл проходит через весь массив без необходимости менять значения sorted остается верным, а внешний контур завершается.

Answer 2

Это не метод, это локальная переменная. В частности, эти типы переменных называются флагами. Он переключается между относительно небольшим количеством альтернативных значений, чтобы сохранить внутреннее состояние алгоритма. В этом случае он переключается между false и true и используется для управления ли выбегать из цикла until или нет.