[Sort] Quick

youtu.be/7BDzle2n47c

youtu.be/hq4dpyuX4Uw

 

 

package algorithm.sort;

public class Quick {

    public static void quickSort(int arr[]){
        quickSort(arr, 0, arr.length-1);
    }

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

        int part = partition(arr, start, end);

        if(start < part-1){
            quickSort(arr, start, part-1);
        }
        if(end > part+1){
            quickSort(arr, part+1, end);
        }

    }

    public static int partition(int arr[], int start, int end){
        int pivot = arr[start + end / 2];

        while(start < end){
            while(arr[start] < pivot){
                start++;
            }
            while(arr[end] > pivot){
                end--;
            }
            if(start < end){
                swp(arr, start, end);
                start++;
                end--;
            }
        }

        return start;
    }

    public static void swp(int arr[], int start, int end){
        int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
    }

    public static void printArr(int[] arr){

        for(int i = 0 ; i < arr.length ; i++){
            if(i != 0) System.out.print(" -> ");
            System.out.print(arr[i]);
        }
        System.out.println();

    }

    public static void main(String[] args) {

        int[] arr = {5,3,4,1,2};

        printArr(arr);

        quickSort(arr);

        printArr(arr);

    }
}