0

В книге Кормена представлен псевдокод алгоритма сортировки вставками с использованием вложенного цикла 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;
            }
        }
    }
}
6
  • а что не работает? Commented 24 окт. 2018 в 18:35
  • Например, на входных данных [54, 6, 59, 35, 4] выдает [6, 35, 54, 59, 4]
    – Dmi_tri
    Commented 24 окт. 2018 в 18:43
  • Почему метка снаружи самого внешнего цикла?
    – MBo
    Commented 24 окт. 2018 в 18:44
  • @MBo потому что нужно выйти из внутреннего for, после чего зайти во внешний цикл с увеличенным на единицу счетчиком j.
    – Dmi_tri
    Commented 24 окт. 2018 в 18:50
  • Этот код нечитабелен. Что происходит с циклом for при таком управлении - даже представить трудно.
    – MBo
    Commented 24 окт. 2018 в 18:57

2 ответа 2

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;
    }
}

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

1

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.