Quicksort (Random Pivot) Code nicht richtig sortiert Java

Question

Der Code ist ein Quicksort-Algorithmus mit einem zufälligen Pivot. Das zufällige Array wird nicht vollständig sortiert. Ich kann nicht herausfinden warum. Der Fehler scheint mit den Grenzen der rekursiven Aufrufe und Swapping zu sein.

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); 

     } 
    } 

// implementierende Methode

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

Ihr Code würde nicht für einen einfachen Eingang arbeiten, {6, 0}, da Ihr first und last werden beide auf dem zweiten Element, also 6 und 0 werden nie ausgetauscht.

Ich habe Ihren Code ein wenig geändert und es hat funktioniert. Ich habe Variablennamen verwendet, die hier mehr Sinn ergeben, aber die Logik ist dieselbe.

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); 

}