Как узнать, когда алгоритм сортировки закончился?

Question

Я разработал очень простую реализацию алгоритма сортировки в Rust, и он работает так, как я хочу, за исключением одной вещи.Он может принимать набор входных данных (взять [3, 6, 2, 1, 9, 4]) и сортировать их.У меня есть программа, печатающая новый набор выходных данных после каждого обмена.Что мне интересно, так это то, как я могу узнать, когда мой сорт закончился?После того, как он решит его, он отобразит завершенную сортировку и просто бесконечно висит там.

Что я мог сделать, это жестко запрограммировать ожидаемый результат, а затем проверить, соответствует ли сортировка этому, но это ужасно по двум причинам: Это наносит ущерб всей цели сортировки, и это ужасно неэффективно и требует жестко закодированных значений, тогда никакие динамические значения не могут пройти через алгоритм.Вот простой алгоритм:

loop {
    for num in 0..(nums.len() - 1) {
        if nums[num] > nums[num + 1] {
            let i = nums[num + 1];

            nums[num + 1] = nums[num];

            nums[num] = i;
        }
    }
}

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

Любая помощь приветствуется!

Answer 1

Каждую итерацию, отслеживайте, отсортирован ли массив, затем разбивайте, если он есть.

let mut sorted = false;
while !sorted {
    sorted = true;
    for num in 0..(nums.len() - 1) {
        if nums[num] > nums[num + 1] {
            let i = nums[num + 1];
            nums[num + 1] = nums[num];
            nums[num] = i;
            sorted = false;
        }
    }
}

Имейте в виду, что это сортировка O (n ^ 2), так что я бы не сталиспользуйте это для чего-либо.