Java: QuickSort на LinkedList дает мне исключение

Question

Я учусь на экзамен (алгоритмы и структуры данных), и я пытаюсь сделать quicksort работать на LinkedList но это дает мне ListIndexOutOfBoundsException,

Для домашней работы некоторое время назад я использовал straightinsertion для сортировки ArrayList а также VectorТеперь я хотел бы понять QuickSorт (я делаю в теории) для LinkedList, Я не слишком знаком с linkedlist, но это не должно быть слишком отличается от ArrayList?

public class Sort {

public static void quickSort(LinkedList<Oseba> a) {
    sort(a, 0, a.size() - 1); // this is line 16
}

public static void sort(LinkedList<Oseba> a, int l, int r) {
    int i = l;
    int j = r;

    Oseba x = a.get((l + r) / 2), w;

    do {
        while (a.get(i).mlajsi(x)) {
            ++i;
        }
        while (x.mlajsi(a.get(j))) { // this is line 31
            --j;
        }
        if (i <= j) {
            w = a.get(i);
            a.set(i, a.get(j));
            a.set(j, w);
            ++i;
            --j;
        }
    } while (i <= j);

    if (l < j) {
        sort(a, l, j);
    }

    if (i < r) {
        sort(a, i, r);
    }
}
}

Oseba означает "Человек", это класс, который я создал для тестирования различных методов (таких как сортировка, сравнение)

public class Oseba implements Comparable<Oseba> {

protected String priimekIme; //surnameName
protected int letoRojstva; //year of birth
protected Spol spol; //gender (enum)

public Oseba(String priimekIme, int letoRojstva, Spol spol) {
    this.priimekIme = priimekIme;
    this.letoRojstva = letoRojstva;
    this.spol = spol;
}

@Override
public int compareTo(Oseba o) {
    if (this.letoRojstva < o.letoRojstva) {
        return -1;
    } else if (this.letoRojstva > o.letoRojstva) {
        return 1;
    } else {
        return this.priimekIme.compareTo(o.priimekIme);
    }
}

public boolean mlajsi(Oseba o) { //younger
    return (o.letoRojstva - this.letoRojstva <= 0);
}

@Override
public String toString() {
    String s = priimekIme + ", " + spol.getKratko() + ", " + letoRojstva;
    return s;
}
}

И это ошибка, которую я получаю:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: -1, Size: 6
    at java.util.LinkedList.checkElementIndex(LinkedList.java:553)
    at java.util.LinkedList.get(LinkedList.java:474)
    at javaapplication1.Sort.sort(Sort.java:31)
    at javaapplication1.Sort.quickSort(Sort.java:16)
    at javaapplication1.JavaApplication1.main(JavaApplication1.java:55)
Java Result: 1

это quicksort метод должен работать с Vector или же ArrayListЯ не знаю, почему это не будет с LinkedList?

Спасибо!

Answer 1

Ну, вы не проверяете границы во время своих циклов.

   while (a.get(i).mlajsi(x)) {
        ++i;
    }
    while (x.mlajsi(a.get(j))) { // this is line 31
        --j;
    }

должно быть

   while (i <= r && a.get(i).mlajsi(x)) {
        ++i;
    }
    while (j >= l && x.mlajsi(a.get(j))) { // this is line 31
        --j;
    }

а также

} while (i <= j);

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

Answer 2

Одно из главных правил в Java (и OO в целом) - это "код для интерфейсов, а не для реализаций". Прямо сейчас вы кодируете LinkedList реализация List интерфейс. Единственный способ гарантировать, что этот код будет работать с любым списком (Vector, ArrayListи т. д.), чтобы изменить ваши декларации. Например:

public static void quickSort(LinkedList<Oseba> a) {

Должен стать

public static void quickSort(List<Oseba> a) {

И аналогично с сортировкой:

public static void sort(List<Oseba> a, int l, int r) {

Теперь, когда вы объявляете человека, это должно выглядеть так:

List<Oseba> a = LinkedList<Oseba>();

Но на месте LinkedListВы можете заменить любой другой тип списка.

Это не отвечает на вопрос о том, почему ваш код дает сбой - я думаю, что совет UmNyobe хорош, хотя я и не тестировал его, но он отвечает на ваш менее важный вопрос о том, почему этот код не работает как другие типы списков, Это потому, что вы кодируете реализацию, где вы должны использовать интерфейс.