Оптимизация быстрой сортировки

Question

Я реализую быстрый алгоритм сортировки в Java и вот код:

public class quickSort { 
     private int array[]; 
    private int length; 

    public void sort(int[] inputArr) { 

     if (inputArr == null || inputArr.length == 0) { 
      return; 
     } 
     this.array = inputArr; 
     length = inputArr.length; 
     quickSorter(0, length - 1); 
    } 

    private void quickSorter(int lowerIndex, int higherIndex) { 

     int i = lowerIndex; 
     int j = higherIndex; 

     // calculate pivot number, I am taking pivot as middle index number 
     int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; 
     // Divide into two arrays 
     while (i <= j) { 

      while (array[i] < pivot) { 
       i++; 
      } 
      while (array[j] > pivot) { 
       j--; 
      } 
      if (i <= j) { 
       exchangeNumbers(i, j); 
       //move index to next position on both sides 
       i++; 
       j--; 
      } 
     } 
     // call quickSort() method recursively 
     if (lowerIndex < j) 
      quickSorter(lowerIndex, j); 
     if (i < higherIndex) 
      quickSorter(i, higherIndex); 
    } 

    private void exchangeNumbers(int i, int j) { 
     int temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
    } 

} 

Тогда я реализую его (медиана трех)

public class quickSort { 
     private int array[]; 
private int length; 

public void sort(int[] inputArr) { 

    if (inputArr == null || inputArr.length == 0) { 
     return; 
    } 
    this.array = inputArr; 
    length = inputArr.length; 
    quickSorter(0, length - 1); 
} 

private void quickSorter(int lowerIndex, int higherIndex) { 

    int i = lowerIndex; 
    int j = higherIndex; 
    int mid = lowerIndex+(higherIndex-lowerIndex)/2; 
    if (array[i]>array[mid]){ 
     exchangeNumbers(i, mid); 
    } 
    if (array[i]>array[j]){ 
     exchangeNumbers(i, j); 
    } 
    if (array[j]<array[mid]){ 
     exchangeNumbers(j, mid); 
    } 

    int pivot = array[mid]; 
    // Divide into two arrays 
    while (i <= j) { 

     while (array[i] < pivot) { 
      i++; 
     } 
     while (array[j] > pivot) { 
      j--; 
     } 
     if (i <= j) { 
      exchangeNumbers(i, j); 
      //move index to next position on both sides 
      i++; 
      j--; 
     } 
    } 
    // call quickSort() method recursively 
    if (lowerIndex < j) 
     quickSorter(lowerIndex, j); 
    if (i < higherIndex) 
     quickSorter(i, higherIndex); 
} 

private void exchangeNumbers(int i, int j) { 
    int temp = array[i]; 
    array[i] = array[j]; 
    array[j] = temp; 
} 
} 

и основной проверки:

public static void main(String[] args) { 
     File number = new File ("f.txt"); 
     final int size = 10000000; 

     try{ 
      quickSortOptimize opti = new quickSortOptimize(); 
      quickSort s = new quickSort(); 
     PrintWriter printWriter = new PrintWriter(number); 
     for (int i=0;i<size;i++){ 
      printWriter.println((int)(Math.random()*100000)); 
     } 
     printWriter.close(); 
     Scanner in = new Scanner (number); 
     int [] arr1 = new int [size]; 
     for (int i=0;i<size;i++){ 
      arr1[i]=Integer.parseInt(in.nextLine()); 
     } 
     long a=System.currentTimeMillis(); 
     opti.sort(arr1); 
     long b=System.currentTimeMillis(); 
     System.out.println("Optimaized quicksort: "+(double)(b-a)/1000); 
     in.close(); 
     int [] arr2 = new int [size]; 
     Scanner in2= new Scanner(number); 
     for (int i=0;i<size;i++){ 
      arr2[i]=Integer.parseInt(in2.nextLine()); 
     } 
     long c=System.currentTimeMillis(); 
     s.sort(arr2); 
     long d=System.currentTimeMillis(); 
     System.out.println("normal Quicksort: "+(double)(d-c)/1000); 
     }catch (Exception ex){ex.printStackTrace();} 

    } 

Проблема в том, что этот метод оптимизации должен повысить производительность на 5%

, но то, что происходит на самом деле является то, что я сделал этот тест много раз, и почти всегда получать лучший результат на нормальной сортировке, что оптимизированной один

так, что случилось со второй реализацией

Answer 1

Медианой три (или более) обычно будет медленнее для ввода, который произвольно упорядочен.

Среднее из трех предназначено для предотвращения того, чтобы действительно плохой случай был столь же ужасным. Есть способы сделать его довольно плохим в любом случае, но, по крайней мере, избегает проблемы для нескольких общих порядков - например, выбирая первый элемент, поскольку стержень может создавать ужасные результаты, если/когда (большая часть) вход уже заказан.