中間要素コードの代わりにランダムピボット要素を使用したクイックソートの実行

Question

次のコードは正常に動作していますが、ランダムピボット要素を使用するようにアルゴリズムを変更する方法を教えてください。代わりに以下の

、iはランダムにピボット要素を選択する、任意のヘルプは

 int pivot = arr[(left + right)/2]; 

import java.util.Random; 


public class QuickSort { 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 

      int i; 
      int array[] = {10,9,1,2,3,4,100,200,300,400}; 
      System.out.println(" Quick Sort\n\n"); 
      System.out.println("Values Before the sort:\n"); 
      for(i = 0; i < array.length; i++) 
      System.out.print(array[i]+" "); 
      System.out.println(); 
      quickSort(array,0,array.length-1); 
      System.out.print("Values after the sort:\n"); 
      for(i = 0; i <array.length; i++) 
      System.out.print(array[i]+" "); 
      System.out.println(); 

    } 

    public static int partition(int arr[], int left, int right) 
    { 
      int i = left, j = right; 
      int tmp; 



      int pivot = arr[(left + right)/2]; 

      while (i <= j) { 
       while (arr[i] < pivot) 
         i++; 
       while (arr[j] > pivot) 
         j--; 
       if (i <= j) { 
         tmp = arr[i]; 
         arr[i] = arr[j]; 
         arr[j] = tmp; 
         i++; 
         j--; 
       } 
      }; 

      return i; 
    } 

    public static void quickSort(int arr[], int left, int right) { 
      int index = partition(arr, left, right); 
      if (left < index - 1) 
       quickSort(arr, left, index - 1); 
      if (index < right) 
       quickSort(arr, index, right); 
    } 

} 

Answer 1

を理解されるであろうとピボット変数割当を元に戻し：RNDクラスランダムオブジェクトである

int pivot = arr[left + rnd.nextInt(right - left)]; 

、プライベート静的最終フィールドとして設定することができます。