Реализую поиск выбором на Java, метод searchIndexSmallest ищет минимальное значение и возвращает int, метод sortSearch требует переделать его boolean

Рейтинг: 0Ответов: 2Опубликовано: 02.05.2023

Реализую алгоритм поиск выбором на Java из книги Адитъя Бхаргава "Грокаем алгоритмы" (в книге пример на Python), метод searchIndexSmallest ищет минимальное значение и возвращает int, используя его, метод sortSearch заполняет новый лист в порядке убывания, но у меня он требует переделать searchIndexSmallest из int в boolean. Почему и куда копать не пойму. Прошу подсказать!

import java.util.ArrayList;
import java.util.Collections;

public class Current {
    public static void main(String[] args) {
        Integer [] array = {7, 5, 3, 4, 9, 1, 2, 6, 8, 4, 7};
        ArrayList<Integer> list= new ArrayList<>();
        ArrayList<Integer> sortList = new ArrayList<>();
        Collections.addAll(list, array);

        System.out.println(sortSearch(list, sortList));
    }

    public static int searchIndexSmallest(ArrayList<Integer> list) {
        int smallest = list.get(0);

        for (int i = 0; i < list.size(); i++) {
            if (smallest > i) {
                smallest = list.get(i);
            }
        }
        return smallest;
    }

    public static ArrayList<Integer> sortSearch(ArrayList<Integer> list, ArrayList<Integer> sortList) {
        for (int i = 0; i < list.size(); i++) {
            sortList.add(i) = searchIndexSmallest(list); // Make 'searchIndexSmallest' return 'boolean'
            list.remove(i);
        }
        return sortList;
    }
}
java алгоритм сортировка-выбором
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

Ошибка не в том, что List::add возвращает boolean, а в попытке присвоить целочисленный результат, возвращаемый одним методом (searchIndexSmallest), результату другого метода:

 error: unexpected type
            sortList.add(i) = searchIndexSmallest(list); // Make 'searchIndexSmallest' return 'boolean'
                        ^
  required: variable
  found:    value

Для оператора присваивания в левой части должна быть переменная.

Однако алгоритм содержит и другие логические ошибки, даже если исправить предыдущую:

  • в методе searchIndexSmallest значение в списке list сравнивается с индексом, поэтому результат работы этого метода неправильный
  • в методе sortSearch размер списка list будет уменьшаться после вызова list.remove, соответственно в "отсортированном" списке будет только половина значений

Вариант исправленного кода:

public static int findSmallest(ArrayList<Integer> list) {
    int smallest = list.get(0);

    for (int i = 0; i < list.size(); i++) {
        if (smallest > list.get(i)) {
            smallest = list.get(i);
        }
    }
    return smallest;
}

public static ArrayList<Integer> sortSearch(ArrayList<Integer> list, ArrayList<Integer> sortList) {
    for (int i = 0, n = list.size(); i < n; i++) {
        Integer min = findSmallest(list);
        sortList.add(min);
        list.remove(min);
    }
    return sortList;
}

Важно, чтобы из исходного списка удалялось Integer значение, а не int индекс.

Вариант с индексами выглядит так:

public static int findSmallestIndex(ArrayList<Integer> list) {
    int smallestIndex = 0;

    for (int i = 1; i < list.size(); i++) {
        if (list.get(smallestIndex) > list.get(i)) {
            smallestIndex = i;
        }
    }
    return smallestIndex;
}

public static ArrayList<Integer> sortSearch(ArrayList<Integer> list, ArrayList<Integer> sortList) {
    for (int i = 0, n = list.size(); i < n; i++) {
        int minIx = findSmallestIndex(list);
        sortList.add(list.get(minIx));
        list.remove(minIx);
    }
    return sortList;
}
▲ 0

Метод

sortList.add(i)

самодостаточен, к списку добавляется i, результат - boolean - успешно или нет.

Присваивать левой части ничего не надо. Возможно, вместо i вы хотели подставить результат searchIndexSmallest, но сначала реализуйте этот метод правильно