QuickSort nicht iterative Lösung sortieren

Question

Ich habe derzeit den folgenden Code für meine schnelle Sortierung. Wie Sie sehen können, produziert es nicht die korrekte Ausgabe. Jede Hilfe wird sehr geschätzt. Ich brauche den Pivot als erstes Element im Array. Wie Sie auch sehen können, messe ich die Zeit, die es braucht, um zu laufen, aber bitte ignorieren Sie das vorläufig.

edit: um genau zu sein, es funktioniert korrekt, wenn ich eine Liste in absteigender Reihenfolge und aufsteigender Reihenfolge (bereits sortiert), aber wenn ich eine zufällige Liste versuchen, funktioniert es nicht.

Ausgang:

QuickSort: 
Quick Sort Took 181023 nanoseconds 
Quick Sort Took 0 milliseconds 
Sorted Quick Sort: 25, 12, 17, 13, 20, 7, 5, 16, 11, 26, 24, 18, 9, 4, 21, 1, 23, 27, 15, 19, 28, 14, 8, 22, 6, 3, 2, 10, 29, 40, 37, 32, 44, 38, 35, 41, 39, 31, 42, 30, 43, 36, 34, 33, 45, 46, 47, 48, 49, 50, 

Code:

class QuickSort { 

    public static int Partition(int[] numbers, int left, int right){ 


    //selects the first item at position [0] as the pivot 
    //left is given 0 when the method is called 
    int pivot = numbers[left]; 
    while (true) 
    { 
     while (numbers[left] < pivot) 
      left++; 

     while (numbers[right] > pivot) 
      right--; 

     if (left < right) 
      { 
      int temp = numbers[right]; 
      numbers[right] = numbers[left]; 
      numbers[left] = temp; 
      } 
      else 
      { 
       return right; 
      } 
    } 
} 
    //method to check for special cases 
    public static void QuickSort_Check(int[] numbers, int left, int right) 
    { 
    //special case of 2 items to be sorted 
    if(right == 1){ 
     if(numbers[0] >= numbers[1]){ 
      System.out.print("This is a special case of 2 inputs: "); 
      System.out.print(numbers[1] + ", " + numbers[0]); 
      System.exit(0); 
     } 
     else { 
      System.out.print("This is a special case of 2 inputs: "); 
      System.out.print(numbers[0] + ", " + numbers[1]); 
      System.exit(0); 
     } 
     System.exit(0); 
    } 

    //special case of 1 item to be sorted 
    else if (right == 0){ 
     System.out.print("This is a special case of 1 input: "); 
     System.out.print(numbers[0]); 
     System.exit(0); 
    } 
    else { 
     QuickSort_Iterative(numbers, left, right); 
    } 

    } 

public static class QuickPosInfo 
{ 
    public int left; 
    public int right; 
}; 

    public static QuickPosInfo spot = new QuickPosInfo(); 

    public static void QuickSort_Iterative(int[] numbers, int left, int right) 
{ 

    if(left >= right) 
     return; // Invalid index range 


     LinkedList<QuickPosInfo> list = new LinkedList< QuickPosInfo>(); 

    spot.left = left; 
    spot.right = right; 
     list.add(spot); 

    while(true) 
    { 
     if(list.size() == 0) 
      break; 

       left = list.get(0).left; 
       right = list.get(0).right; 
       list.remove(0); 

     int pivot = Partition(numbers, left, right); 

     if(pivot > 1) 
     { 
      spot.left = left; 
      spot.right = pivot - 1; 
      list.add(spot); 
     } 

     if(pivot + 1 < right) 
     { 
      spot.left = pivot + 1; 
      spot.right = right; 
      list.add(spot); 
     } 
    } 
} 

} 

Answer 1

Diese Partition Methode richtig Hälfte der Array sortiert, dann nicht die andere Hälfte sortieren war so glaube ich, das Problem in Ihrem QuickSort_Iterative ist(); wenn der Drehpunkt 21 entspricht es nur unendlich Swaps 20 und 21.

private static int partition(int[] arr,int left,int right) { 
     int pivot = arr[right]; 
     int small = left-1; 
     for(int k = left;k < right;k++) 
     { 
      if(arr[right] <= pivot) 
      { 
       small++; 
       swap(arr,right,small);    
      } 


     } 
     swap(arr,right,small+1); 
     System.out.println("Pivot= "+arr[small+1]);//prints out every sort 
     System.out.println(Arrays.toString(arr)); 
     return small+1; 


    } 

    private static void swap(int[] arr, int k, int small) {//easy swap method 
     int temp; 
     temp = arr[k]; 
     arr[k] = arr[small]; 
     arr[small] = temp; 

    }  

UPDATE

Hier wird die angeforderte Methode ist. Ich glaube, dass das Problem mit Ihrem ursprünglichen Problem darin besteht, dass Sie die Werte von links und rechts nicht richtig ändern, da das Array sortiert ist.

void QuickSort(int arr[], int left, int right) 
{ 
    // create auxiliary stack 
    int stack[] = new int[right-l+1]; 

    // initialize top of stack 
    int top = -1; 

    // push initial values in the stack 
    stack[++top] = left; 
    stack[++top] = right; 

    // keep popping elements until stack is not empty 
    while (top >= 0) 
    { 
     // pop right and l 
     right = stack[top--]; 
     left = stack[top--]; 

     // set pivot element at it's proper position 
     int p = partition(arr, left, right); 

     // If there are elements on left side of pivot, 
     // then push left side to stack 
     if (p-1 > left) 
     { 
      stack[ ++top ] = l; 
      stack[ ++top ] = p - 1; 
     } 

     // If there are elements on right side of pivot, 
     // then push right side to stack 
     if (p+1 < right) 
     { 
      stack[ ++top ] = p + 1; 
      stack[ ++top ] = right; 
     } 
    } 
} 

Answer 2

Ich weiß nicht, dass Ihnen das helfen wird oder nicht, Sie können auch den untenstehenden Code für das gleiche ausprobieren.

public class Demo { 

private int array[]; 
    private int length; 

    public void sort(int[] inputArr) { 

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

    private void quickSort(int lowerIndex, int higherIndex) { 

     int i = lowerIndex; 
     int j = higherIndex; 

     int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; 

     while (i <= j) { 

      while (array[i] < pivot) { 
       i++; 
      } 
      while (array[j] > pivot) { 
       j--; 
      } 
      if (i <= j) { 
       exchangeNumbers(i, j); 
       i++; 
       j--; 
      } 
     } 

     if (lowerIndex < j) 
      quickSort(lowerIndex, j); 
     if (i < higherIndex) 
      quickSort(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 a[]){ 

     Demo sorter = new Demo(); 
     int[] input = {8,693,29,3,2,8,29,82,4,26,2,62,82,6,52,9,42,6,52,66,2,8}; 
     sorter.sort(input); 
     for(int i:input){ 
      System.out.print(i); 
      System.out.print(" "); 
     } 
    } 
}