Quick Sort-Implementierungsversuch

Question

Ich habe versucht, eine Quicksort-Implementierung zu schreiben, nachdem ich dieses Video auf youtube angeschaut habe. https://www.youtube.com/watch?v=MZaf_9IZCrc&t=215s aber es funktioniert nicht. Kann mir jemand sagen, was ich falsch mache? Danke Ferda

public class Trial{ 

    public static void main(String []args){ 
     int arr[] = {7, 3, 4, 2, 6, 1, 5}; 
     quickSort(arr, 0, 6); 
    } 


    public static void quickSort(int[] arrInput, int start, int end){ 

     int arr[] = new int[end-start+1]; 
     for(int i=start, j=0; i<end; i++, j++){ 
      arr[j]=arrInput[i]; 
     } 
     int size = arr.length; 
     int pivotValue = arr[size-1]; 

     for (int i=-1; i<arr.length; i++){ 
      for(int j=0; j<arr.length; j++){ 
      if(arr[j]< pivotValue){ 
       int temp = arr[j]; 
       i++; 
       arr[j] = arr[i]; 
       arr[i] = temp; 
      } 
      for(int p = i; p< size-2; p++){ 
       arr[p+1] = arr[p]; 
      } 
      arr[i] = pivotValue; 
      quickSort(arr, 0, i); 
      quickSort(arr, i+1, size-1); 
      } 
     } 

     } 
} 

Answer 1

Video zu implementieren, die Sie hier erwähnt, erzählt von Teilungsmechanismus .So Elemente mit einem Wert kleiner als Pivot kommen vor dem Pivot, Elementwerte größer als Pivot kommen nach Pivot (Gleiches kann in beide Richtungen gehen). Es gibt zwei Teile, wenn schnelle Sortieralgorithmen, partition und quicksort. Quicksort ist in place sort, und Sie müssen hier kein neues Array erstellen. Und Sie wählten letztes Element als Pivotelement, können Sie unter Pseudo-Code angegeben folgen zu implementieren quicksort:

quicksort(A, lo, hi) is 
if lo < hi then 
    p := partition(A, lo, hi) 
    quicksort(A, lo, p – 1) 
    quicksort(A, p + 1, hi) 



partition(A, lo, hi) is 
    pivot := A[hi] 
    i := lo  // place for swapping 
    for j := lo to hi – 1 do 
     if A[j] ≤ pivot then 
      swap A[i] with A[j]   
      i := i + 1 
swap A[i] with A[hi] 
return i 

Answer 2

Quicksort ist so etwas wie das:

public static void quicksort(int[] array, int begin, int end) { 
    if (array == null || array.length() == 0) { 
     return; 
    } 
    int pivot = partition(array); 
    quicksort(array, 0, pivot); 
    quicksort(array, pivot + 1, array.length); 
} 

public static void quicksort(int[] array) { 
    quicksort(array, 0, array.length()); 
} 

Danach können Sie Ihr Video verwenden, um Partition Methode