クイックソート（ランダムピボット）コードが正しくソートされないJava

Question

コードはランダムピボットのクイックソートアルゴリズムです。ランダム配列を完全にソートしていません。なぜ私は理解できません。エラーは、再帰呼び出しとスワッピングの境界にあるようです。コードがあなたfirstとlastがあろう従って第二の要素をポイントし、6の両方ので、簡単な入力、{6,0}、のために機能しない方法

public static void testQuickSort(){ 

     //creates a random list of integers to be sorted and prints it 
     ArrayList<Integer> list = new ArrayList<Integer>(); 
     Random rand = new Random(); 
     for (int i = 0; i <= 19; i++){ 
      list.add(rand.nextInt(100)); 
      System.out.print(list.get(i)+" "); 
    } 
     //calls quicksort and then prints the sorted array 
     System.out.println(); 
     Assignment2.quickSort(list); 
     for (int i = 0; i <= 19; i++){ 
      System.out.print(list.get(i)+" "); 
    } 
    } 

Answer 1

を実装

public static <E extends Comparable<E>> void quickerSort(ArrayList<E>   input, int lower, int higher){ 
      int first = lower; 
      int last = higher; 
      if (lower >= higher) 
      return; 
     //generates the random pivot 
      int pivot = rand.nextInt(higher-lower+1) + lower; 

     //moves the pivot to the beginning of the list 

      E temp = input.get(first); 
      input.set(first, input.get(pivot)); 
      input.set(pivot, temp); 
      pivot = first; 
      first++; 

     //if the values on the left side of the array are less than the 
     //value of the pivot, first is incremented (first part of loop) until 
     //a greater value is reached 

     //if the values on the right side of the array are greater than the 
     //value of the pivot, last is incremented until a lesser value is reached 

      while (first < last){ 
        while (input.get(first).compareTo(input.get(pivot)) <= 0 && first < last){ 
         first++; 
      } 
        while(input.get(last).compareTo(input.get(pivot)) > 0 && last >= first){ 
         last--; 
      } 

     //switches the two values reached through the while loops 
      if (first < last){ 
       temp = input.get(first); 
       input.set(first, input.get(last)); 
       input.set(last, temp); 
      } 
     } 

    //moves the pivot to where first is 
     temp = input.get(first-1); 
     input.set(first-1, input.get(pivot)); 
     input.set(pivot, temp); 

    //calls the method recursively 
     if (lower < first-1){ 
      quickerSort(input,lower,first-1); 
     } 
     if (first < higher){ 
      quickerSort(input,first,higher); 

     } 
    } 

// 0はスワップされません。

私はあなたのコードを少し修正しています。私はここでより意味をなさない変数名を使用しましたが、ロジックは同じです。

public static <E extends Comparable<E>> void quickSort(ArrayList<E> input, int low, int high) { 
    if (low >= high) 
     return; 

    // generates the random pivot 
    int pivotIndex = new Random().nextInt(high - low + 1) + low; 

    E pivot = input.get(pivotIndex); 

    // moves the pivot to the beginning of the list 
    Collections.swap(input, pivotIndex, low); 

    int i = low; 
    int j = high; 

    // if the values on the left side of the array are less than the 
    // value of the pivot, first is incremented (first part of loop) until 
    // a greater value is reached 

    // if the values on the right side of the array are greater than the 
    // value of the pivot, last is incremented until a lesser value is 
    // reached 

    while (i <= j) { 
     while (input.get(i).compareTo(pivot) <= 0 && i < j) { 
      i++; 
     } 
     while (input.get(j).compareTo(pivot) > 0 && j >= i) { 
      j--; 
     } 

     // break here when two pointers meet since the pivot position has been found 
     if (i >= j) 
      break; 

     // switches the two values reached through the while loops 
     Collections.swap(input, i, j); 
    } 

    // moves the pivot to where j is 
    Collections.swap(input, low, j); 

    // calls the method recursively 
    quickSort(input, low, j - 1); 

    quickSort(input, j + 1, high); 

}