Quick Sort Implementation Attempt

Question

I attempted to write a quicksort implementation after watching this video on youtube. https://www.youtube.com/watch?v=MZaf_9IZCrc&t=215s but it does not work. Can someone tell me what I am doing wrong? Thank you 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

Quicksort is something like that:

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

After that, you can use your video to implement partition method

Answer 2

Video which you mentioned here, tells about partition mechanism.So elements with value less than pivot come before the pivot, elements value greater than pivot come after pivot(equal can go either way).There are two parts if quick sort algorithms, partition and quicksort . Quicksort is in place sort, and you do not need to create new array here. And you chose last element as pivot element, you can follow below given pseudo code to implement 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