Insertion sort через цикл for с использованием go to

161

09 марта 2019, 21:50

В книге Кормена представлен псевдокод алгоритма сортировки вставками с использованием вложенного цикла while. Я решил реализовать этот алгоритм сортировки с использованием вложенного цикла for, в котором используется переход по метке (аналог go to). Подскажите, в чем допущена ошибка? Например, на входных данных [54, 6, 59, 35, 4] алгоритм выдает [6, 35, 54, 59, 4]

public static void forSort(int arr[]) {
    label1:
    for (int j = 1; j < arr.length; j++) { //слева от j отсортированная часть массива
        int key = arr[j];
        for (int i = j - 1; i > -1; i--) { //проходим по отсортированной части массива с целью поиска места для j-элемента
            if (i == 0 && arr[i] > key) { //частный случай i=0. если не рассмотреть, цикл завершается без свапа элементов 
                arr[i + 1] = arr[i]; //свап первого и второго элементов массива 
                arr[i] = key;
                j++;
                continue label1; //рассматриваем следующий j-элемент
            }
            if (arr[i] > key) {
                arr[i + 1] = arr[i];
            } else {
                arr[i + 1] = key;
                j++;
                continue label1;
            }
        }
    }
}

Answer 1

У Вас перед переходом на метку увеличивается j. Но как только выполнился переход на внешний цикл, j увеличилась еще раз. Уберите в цикле j++ и будет вам счастье. Но тут напрашивается НЕ использовать цикл for, т.к. он плавно превращается в цикл while. Выше вполне красивый ответ, не надо изобретать велосипед.

Answer 2

Алгоритм сортировки вставками в книге Кормена (где индексы массивов начинаются с единицы):

for j = 2 to A.length
    key = A[j]
    // Insert A[j] into sorted sequence A[1..j - 1].
    i = j - 1
    while i > 0 and A[i] > key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key

Если перевести это на Java один в один, получится следующий код:

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

Как видите, всё гораздо проще, чем вы написали и никаких переходов на метки.

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

Считывание текущей даты Android

Имеется следующий код:

189

Java

Копирование строки c JTable в буфер обмена

Не могу скопировать выделеную строку в Jtable, у меня в JTable есть Popup menu , в которов я добавил кнопку копировать, а теперь хочу скопировать данные...

192

Java