Код массива быстрой сортировки

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», но если это что-то еще, он выдает исключение.

Например, если я добавлю это для массива:

5 6 8 9 7 8 0 1 8 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

Проблема проста: вы случайно пытаетесь получить доступ к массиву из 10 элементов с индексом 10, когда единственными допустимыми индексами являются 0-9.

Это происходит в режиме онлайн# 48 (или, возможно, 47, или 49).Вы, вероятно, случайно добавляете +1 к индексу, когда не понимаете этого, и превышаете границы массива.

Выясните, почему происходит ваш особый случай, и вы будете дома.

Answer 2

Предположим, что first = 8 и last = 9 в одном из вызовов quickSort().Предположим также, что a [8]> a [9].Подумайте о том, что произойдет в цикле left++ ...

(помните, что часть условия a[left] < a[pivindex] проверяется перед частью left <= right)

ОК, попробуйте пройтичерез метод:

Начиная с first = 8, last = 9, я получаю pivindex = 8, left = 9, right = 9. Я проверяю условие while:

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

Это правда, поэтому я увеличиваю влево.Теперь влево = 10 и вправо = 9. Я снова проверяю условие while ...

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

... и выхожу из конца массива.Теперь, если бы только я проверил эти 10 <= 9, прежде чем посмотреть на [влево]! </p>

ОК, если вы все еще застряли, я просто выйду и скажу вам.Проблема в этом цикле заключается в том, что вы пытаетесь получить доступ к a[left] до , проверяя, слишком ли велико left.Вы можете решить проблему одним из двух способов:

1. Переключите порядок условий, чтобы сначала проверить слева, или
2. Измените <= на <, такчто <code>left никогда не становится больше right.