0

私は試験（アルゴリズムとデータ構造）のために勉強していて、quicksort仕事をしようとしてLinkedListいますが、それは私にListIndexOutOfBoundsException.

少し前の宿題では、straightinsertionソートArrayListに とを使用しましたが、今はt (理論上はそうです) の をVector理解したいと思います。はあまりよく知らないが、 ?とあまり変わらないはずだ。QuickSorLinkedListlinkedlistArrayList

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メソッドは or で動作するはずですが、なぜ ? で動作VectorしないArrayListのかわかりません。LinkedList

ありがとう！

4

2 に答える 2

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ます (ただし、必要ではないと思います)。例外の問題は解決しますが、アルゴリズムの正確性は確認していません。

于 2013-01-25T14:39:55.760 に答える
0

Java (および一般的なオブジェクト指向)の大きなルールの 1 つは、 「実装ではなく、インターフェイスへのコード」です。現在、インターフェイスの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 のアドバイスは良いと思いますが、私はそれをテストしませんでした -- しかし、なぜこのコードが他のリストタイプのように振る舞わないのかというあなたのより少ない質問に答えます. これは、インターフェイスを使用する必要がある実装に合わせてコーディングしているためです。

于 2013-01-25T14:52:27.690 に答える