クイックソート配列コード

Question

public class Main 
{ 

    public static void main (String args[]) 
    { 
    int nums[]= {2, 3, 4, 5, 6, 7, 8, 9, 0, 1}; 
    for (int index = 0; index < 10; index++) 
     System.out.print(" " +nums[index]);; 
    System.out.println(); 

    quickSort(nums,0,9); 
    for (int index = 0; index < 10; index++) 
     System.out.print(" " +nums[index]); 
    System.out.println(); 
    } 


    private static void swap(int a[], int lft, int rt) 
    { 
    int temp; 
    temp = a[lft]; 
    a[lft] = a[rt]; 
    a[rt] = temp; 
    } 


    public static int pivot(int firstpl, int lastpl) 
    { 
    if(firstpl >= lastpl) 
     return -1; 
    else 
     return firstpl; 
    } 



    private static void quickSort(int a[], int first, int last) 
    { 
    int left,right; 
    int pivindex = pivot(first,last); 
    if(pivindex >= 0) 
    { 
     left = pivindex +1; 
     right = last; 
     do 
     { 
     while (a[left] < a[pivindex] && left <= right) 
      left++; 
     while (a[right] > a[pivindex]) 
      right--; 
     if (right > left) 
      swap(a,left,right); 
     } 
     while(left < right); 

     swap (a, pivindex, right); 
     quickSort(a, first, right-1); 
     quickSort(a, right+1, last); 

    } 
    }  
} 

これはクイックソートのコードです。配列の0の位置番号が "2"の場合はすべて正常に動作しますが、それ以外の場合は例外がスローされます。私は配列のためにこれを入れた場合例えば

は、：

をそれは次のエラーを与える：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10 
    at Main.quickSort(Main.java:48) 
    at Main.quickSort(Main.java:59) 
    at Main.quickSort(Main.java:59) 
    at Main.main(Main.java:12) 

助けてください！

Answer 1

quickSort()の呼び出しの1つにfirst = 8とlast = 9があるとします。 a [8]> a [9]とする。この方法を歩いてみてください、OK

（条件の a[left] < a[pivindex]一部が left <= right部分の前にチェックされている、覚えておいてください）

... left++ループの中で何が起こるかについて考えてみて：

で開始最初= 8、9 =最後、私は9 =左pivindex = 8、右= 9で終わる私は、while条件を確認してください。

while(a[9] < a[8] && 9 <= 9) 

それは本当だので、私は左に増加します。今= 10と9 =右、左、私は再び...

while(a[10] < a[8] && 10 <= 9) 

while条件を確認...と、配列の末尾をオフに行きます。さて、もし私が[左]を見る前にそれを確認しただけであれば、10 < = 9！

あなたがまだ立ち往生していれば、私はちょうどすぐに出てきて、あなたに伝えます。そのループの問題は、leftが大きすぎるかどうかを確認する前に、の前にa[left]にアクセスしようとしていることです。次のいずれかの方法で問題を解決することができます

1. スイッチ条件のため、あなたが最初に左にチェックするように、または
2. 変更<を= <に、leftがより大きくなったことがないように、 right。

Answer 2

問題は簡単です。偶然に、有効なインデックスが0-9の場合に、インデックスがの10要素配列にアクセスしようとしています。

これは＃48行目（あるいは47または49行目）で起こっています。インデックスを理解していないときや、配列の境界を超えているときに誤って+1をインデックスに追加している可能性があります。

あなたの特別なケースが起こっている理由を理解して、あなたは帰るでしょう。