Как я могу заставить этот метод сортировки вставки запускаться по одному шагу за раз? - PullRequest
Новая
       36

Как я могу заставить этот метод сортировки вставки запускаться по одному шагу за раз?

0 голосов
/ 02 марта 2019

Я пытаюсь анимировать этот метод визуально, и я хочу использовать таймер для управления сортировкой вставок, позволяя ему проверять один индекс или менять один набор индексов очень часто (100 мс).Таким образом, я вижу, как это происходит шаг за шагом.

Вот метод: 

public static void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int j = i;
        while(j > 0 && arr[j] < arr[j-1]){
            ArrayUtility.swap(j,j-1, arr);
            j--;
        }
    }
}

Цель этого состоит в том, чтобы, если одна пара индексов проверялась друг против друга,метод не продолжает цикл, он проверяет индексы и затем останавливается, пока следующая часть метода не будет запущена через 100 мс.

1 Ответ

0 голосов
/ 02 марта 2019

Объяснение

Запомните текущие индексы i и j, тогда вы можете легко приостановить и возобновить в любое время, извлекая все возможные отдельные шаги из вашей конструкции цикла,то есть:

  • Регулярная итерация внутреннего цикла
  • Внутренний цикл завершен, продвигается внешний цикл
  • Внешний цикл завершен, алгоритм выполнен

Я бы создал класс Sorter, в котором эти индексы и массив были бы полями, затем вы можете предоставить простой метод sortStep, который выполняет только один шаг и обновляет индексы.

Решение

public class Sorter {
    private final int[] values;
    private int i = 1;
    private int j = 1;

    public Sorter(int[] values) {
        this.values = values;
    }

    public int[] getValues() {
        return values;
    }

    // @returns Whether sorting algorithm has finished
    public boolean sortStep() {
        if (i >= values.length) {
            // Outer loop has finished
            return true;
        }

        if (j > 0 && values[j] < values[j - 1]) {
            // Inner loop iteration
            ArrayUtility.swap(j, j - 1, values);
            j--;
        } else {
            // Inner loop has finished, outer loop iteration
            i++;
            j = i;
        }
        return false;
    }
}

Теперь вы можете просто вызывать sortStep в цикле до его завершения: 

int[] values = ...
Sorter sorter = new Sorter(values);

while (!sorter.sortStep()) {
    // Animate
    displayValues(values);
    Thread.sleep(100);
}

Или подключить метод к приятным кнопкам паузы и возобновления вашего пользовательского интерфейса.

Примечания

Если вы не хотите обрабатывать

  • Регулярная итерация внутреннего цикла
  • Внутренний цикл завершен, продвигается внешний цикл

как два отдельных шага, но как один шаг, йовы можете просто переместить регистр из конструкции if-else и сделать это непосредственно после внутренней итерации: 

if (j > 0 && values[j] < values[j - 1]) {
    // Inner loop iteration
    ArrayUtility.swap(j, j - 1, avaluesrr);
    j--;
}

if (j <= 0 || values[j] >= values[j - 1]) {
    // Inner loop has finished, outer loop iteration
    i++;
    j = i;
}

Аналогично вы можете поместить определение done в конец методачтобы метод вывел true в тот момент, когда его действительно сделали.Таким образом, вам не нужно вызывать его снова без эффекта: 

// Duplicated at the end of sortStep
if (i >= values.length) {
    // Outer loop has finished
    return true;
}
...