クイックソートのトラブルjava.lang.ArrayIndexOutOfBoundsException：10

Question

私はjava.lang.ArrayIndexOutOfBoundsExceptionといくつかの問題を抱えていますここでエラー public void quicksort() { // Recursion quicksort(0, counter - 1); }

はすべて私のコード

public class Main { 
private static int comparations = 0; 
private static int swaps = 0; 
int[] array; 
int[] a; 
int counter = 0; 
int size; 

public void qwe() throws IOException { 
    Scanner scan = new Scanner(new File("input.txt")); //provide file name from outside 
    while(scan.hasNextInt()) 
    { 
     counter++; 
     scan.nextInt(); 
    } 
    System.out.println(counter); 
    Scanner scan2 = new Scanner(new File("input.txt")); 
    a = new int[counter]; 
    for(int i=0;i<counter;i++) 
    { 
     a[i]=scan2.nextInt(); //fill the array with the integers 
    } 
} 



public int partition(int p, int q) { 
    int i = p; 
    int j = q + 1; 
    // Get the pivot element from the middle of the list 
    int pivot = a[p]; 
    // Divide into two lists 
    do { 
     // If the current value from the left list is smaller then the pivot 
     // element then get the next element from the left list 
     do { 
      i++;// As we not get we can increase i 
     } while (a[i] < pivot); 
     // If the current value from the right list is larger then the pivot 
     // element then get the next element from the right list 
     do { 
      j--;// As we not get we can increase j 
     } while (a[j] > pivot); 
     // If we have found a values in the left list which is larger then 
     // the pivot element and if we have found a value in the right list 
     // which is smaller then the pivot element then we exchange the 
     // values. 
     if (i < j) { 
      swap(i, j); 
     } 

    } while (i < j); 
    // swap the pivot element and j th element 
    swap(p, j); 

    return j; 
} 

private void swap(int p, int j) { 
    // exchange the elements 
    int temp = a[p]; 
    a[p] = a[j]; 
    a[j] = temp; 
    swaps++; 
} 

public void quicksort() { 
    // Recursion 
    quicksort(0, counter - 1); 
} 

public void quicksort(int p, int q) { 
    int j; 
    if (p < q) { 
     // Divide into two lists 
     j = partition(p, q); 
     // Recursion 
     quicksort(p, j - 1); 
     quicksort(j + 1, q); 
    } 
    comparations++; 

} 

public void print() { 
    // print the elements of array 
    for (int i = 0; i < counter; i++) { 
     System.out.print(a[i] + ","); 
    } 
    System.out.println(); 

} 

public static void main(String args[]) throws IOException { 
    Main q = new Main(); 
    q.qwe(); 
    System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<"); 
    q.print(); 
    q.quicksort(); 
    System.out.println("After Sort > > > > > > > > > > > >"); 
    q.print(); 
    System.out.println("Comparisons: " + comparations); 
    System.out.println("Swaps: " + swaps); 

} 
} 

Answer 1

あなたは、コードの末尾

Answer 2

で持っている私は、あなたがdo{...} whileを避け、代わりにwhileを使用することがあると思います。私はあなたのpartitionコードが正しくありません疑う

public int partition(int p, int q) { 
    int i = p; 
    int j = q + 1; 
    // Get the pivot element from the middle of the list 
    int pivot = a[p]; 
    // Divide into two lists 
    while (i < j) { 
     // If the current value from the left list is smaller then the pivot 
     // element then get the next element from the left list 
     while (a[i] < pivot) { 
      i++;// As we not get we can increase i 
     } 
     // If the current value from the right list is larger then the pivot 
     // element then get the next element from the right list 
     while (a[j] > pivot) { 
      j--;// As we not get we can increase j 
     } 
     // If we have found a values in the left list which is larger then 
     // the pivot element and if we have found a value in the right list 
     // which is smaller then the pivot element then we exchange the 
     // values. 
     if (i < j) { 
      swap(i, j); 
     } 

    } 
    // swap the pivot element and j th element 
    swap(p, j); 

    return j; 
} 

Answer 3

：よう

何か。スワップはインデックスにない値に基づいて行われる必要があります。

if (i < j) { 
    swap(i, j); 
} 

Partitioning:ピボットより 値が大きいと、すべての要素が後に来るしながらピボットより 少ない値を持つすべての要素は、ピボットの前に来るように等しい（配列を並べ替えます値はどちらでも に行くことができます）。この分割後、ピボットは最終的に ポジションにあります。これはパーティション操作と呼ばれます。

また、同じファイルを2回読み込んでいると、同じループ内の要素と要素の数を取得できません。