ArrayIndexOutofBound в реализации QUICK-SORT

Question

Я предполагаю, что мой код должен работать, но он бросает исключение ArrayIndexOutofBounds в сортировку, разделение и основные методы.

Где я ошибаюсь?

Вот код:

import java.util.Scanner; 

public class QuickSort 
{ 
public void sort(int a[], int low, int high) 
{ 

    if(low < high) 
    { 
     int q = partition(a, low, high); 
     sort(a, low, q-1); 
     sort(a, q+1, high); 
    } 
} 
public int partition(int a[], int low, int high) 
{ 
    int pivot=a[high]; 
    int i= (low-1); 
    for(int j=low; j<=high-1 ;j++) 
    { 
     if (a[j] <= pivot) 
     { 
      i++; 
      exchange(a[i], a[j]); 
     } 
    } 
    exchange(a[i+1], a[high]); 
    return i+1; 
} 
public void exchange(int v1,int v2) 
{ 
    int var1=v1; 
    int var2=v2; 
    var1 = var1 + var2; 
    var2 = var1 - var2; 
    var1 = var1 - var2; 
    //System.out.println(var1); 
    //System.out.println(var2); 
} 
public void printArr(int a[]) 
{ 
    int n=a.length; 
    System.out.println("SORTED ARRAY"); 
    System.out.println("-------------------------------------------"); 
    for(int i=0;i<n;i++) 
    { 
     System.out.print(a[i]); 
     System.out.print("\t"); 
    } 
} 

public static void main(String[] args) { 
    Scanner sc= new Scanner(System.in); 
    QuickSort obj = new QuickSort(); 
    // TODO Auto-generated method stub 

    System.out.println("Enter the no of elements in array"); 
    int n= sc.nextInt(); 
    int arr[] = new int[n]; 
    System.out.println("Enter the elements of array"); 
    for(int i=1;i<=n;i++) 
     { 
      arr[i]=sc.nextInt(); 
     } 


    obj.sort(arr, 1 , arr.length); 
    obj.printArr(arr); 

    sc.close(); 
} 
} 

Эти ошибки в Затмении

Исключение в нити "основной" java.lang.ArrayIndexOutOfBoundsException: 2
в QuickSort. раздел (QuickSort.java:17)
на QuickSort.sort (QuickSort.java:10)
на QuickSort.main (QuickSort.java:67)

Answer 1

Вы призываете sort из main с arr.length как high параметром, который вы передаете partition.

В partition вы

int pivot = a[high]; 

, который на самом деле

int pivot = a[a.length]; 

Индексы в Array являются от 0 к array size - 1, это то, что вызывает ArrayIndexOutOfBoundsException.

Изменения main

obj.sort(arr, 1 , arr.length); 

Для

obj.sort(arr, 1 , arr.length - 1); 

Answer 2

Вашего кода было несколько ошибок:

1. Вы использовали свои массивы, как если бы были проиндексированы от 1 до длины. В Java первый элемент находится в [0] -клете, а последний в [length-1]-cell

2. Ваш метод обмена не работает: вы меняли локальные переменные. В Java, если вы вызываете метод в двух ints, метод копирует значения этих переменных, заданных как входные данные, и любая модификация, которую вы делаете внутри метода, не влияет на исходную переменную. Решение: дайте массив как входной сигнал метода, с двумя индексами, которые вы хотите обменять.

3. Этот тип обмена (добавление двух переменных внутри 1 ...) не работает, если две переменные на самом деле одинаковы. Вам нужно отфильтровать этот случай. (Своп были использовать третью переменную не требует этого фильтра)

В выборе дизайна, при написании методы массивов, аргументы (INT [] массив, Int, Int от до), как правило, такой, чтобы он был включен в случае «из» и был исключительным в случае «to». Я также изменил ваш код, чтобы соответствовать этой норме.

Закрепление всех тех, вы получите этот код, который работает correcty на моем собственном компьютере: (Я пометил модификацию с «// Там» комментариями)

import java.util.Scanner; 

public class QuickSort { 
public void sort(int a[], int low, int high) { 

    if (low < high - 1) { 
     int q = partition(a, low, high); 
     sort(a, low, q);// There 
     sort(a, q + 1, high);// There 
    } 
} 

public int partition(int a[], int low, int high) { 
    int pivot = a[high - 1]; 
    int i = (low - 1); 
    for (int j = low; j < high - 1; j++) { 
     if (a[j] <= pivot) { 
      i++; 
      exchange(a, i, j); 
     } 
    } 
    exchange(a, i + 1, high - 1); // There 
    return i + 1; 
} 

public void exchange(int[] tab, int i1, int i2) // There 
{ 
    if (i1 != i2) { 
     tab[i1] = tab[i1] + tab[i2]; 
     tab[i2] = tab[i1] - tab[i2]; 
     tab[i1] = tab[i1] - tab[i2]; 
    } 
    // System.out.println(tab[i1]); 
    // System.out.println(tab[i2]); 
} 

public void printArr(int a[]) { 
    int n = a.length; 
    System.out.println("SORTED ARRAY"); 
    System.out.println("-------------------------------------------"); 
    for (int i = 0; i < n; i++) { 
     System.out.print(a[i]); 
     System.out.print("\t"); 
    } 
} 

public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in); 
    QuickSort obj = new QuickSort(); 
    // TODO Auto-generated method stub 

    System.out.println("Enter the no of elements in array"); 
    int n = sc.nextInt(); 
    int arr[] = new int[n]; 
    System.out.println("Enter the elements of array"); 
    for (int i = 0; i < n; i++) // There 
    { 
     arr[i] = sc.nextInt(); // There 
    } 

    obj.sort(arr, 0, arr.length); // There 
    obj.printArr(arr); 

    sc.close(); 
} 
}