Модификация quicksort для быстрой сортировки с использованием использования медианного треугольника

Question

Я пытаюсь изменить программу Quicksort, которая использовала первый элемент в качестве поворота для Quicksort, который использует медиану из трех (медиана первого, последнего и среднего элемента) как стержень. Моя реализация до сих пор, однако, дает мне ArrayIndexOutOfBoundsException (s) при ее тестировании. Наверное, мне что-то не хватает, но я просто не могу понять, где я ошибаюсь. Любая помощь и советы высоко ценятся.

public class Sorts { 

    private static void swap(int[] array, int index1, int index2) { 
     // Precondition: index1 and index2 are >= 0 and < SIZE. 
     // 
     // Swaps the integers at locations index1 and index2 of the values array. 
     int temp = array[index1]; 
     array[index1] = array[index2]; 
     array[index2] = temp; 
    } 

    private static int medianOfThree(int[] array, int first, int last) { 

     int mid = array[(first+last)/2]; 

     if (array[first] > array[mid]) { 
      swap(array, first, mid); 
     } 

     if (array[first] > array[last]) { 
      swap(array, first, last); 
     } 

     if (array[mid] > array[last]) { 
      swap(array, mid, last); 
     } 
     swap(array, mid, last-1); 
     return array[last-1]; 
    } 

    private static int partition(int[] array, int first, int last, int median) { 

     int pivot = array[last-1]; 
     int saveF = last-1; 
     boolean onCorrectSide; 

     first++; 
     do { 
      onCorrectSide = true; 
      while (onCorrectSide) {   // move first toward last 
       if (array[first] > pivot) { 
        onCorrectSide = false; 
       } 
       else { 
        first++; 
        onCorrectSide = (first <= last); 
       } 
      } 

      onCorrectSide = (first <= last); 
      while (onCorrectSide) {   // move last toward first 
       if (array[last] <= pivot) { 
        onCorrectSide = false; 
       } 
       else { 
        last--; 
        onCorrectSide = (first <= last); 
       } 
      } 

      if (first < last) { 
       swap(array, first, last); 
       first++; 
       last--; 
      } 
     } while (first <= last); 

     swap(array, saveF, last); 
     return last; 
    } 


    private static void quickSort(int[] array, int first, int last) { 

     if (first < last) { 
      int pivot; 

      int median = medianOfThree(array, first, last); 
      pivot = partition(array, first, last, median); 

      // values[first]..values[splitPoint - 1] <= pivot 
      // values[splitPoint] = pivot 
      // values[splitPoint+1]..values[last] > pivot 

      quickSort(array, first, pivot - 1); 
      quickSort(array, pivot + 1, last); 
     } 
    } 


    public static void quickSort(int[] array) { 
     quickSort(array, 0, array.length-1); 
    } 
} 

Answer 1

вы не используете переменную в правильном направлении:

int mid = array[first+last/2]; 

дает значение в середине массива, но не смещение (индекс) массива. Но вы используете в середине, в качестве индексной переменной в ваших вызовов методов:

swap(array, first, mid);