QuickSort

public class QuickNaive {
    public static void main(String[] args) {
        int[] arrr = {9,2,4,51,2,3,7,84,2,4,10,21};
        // quickSortAsc(arrr, 0, arrr.length-1);
        quickSortDesc(arrr, 0, arrr.length-1);
        printArray(arrr);
    }

    static int partitionAsc(int arr[], int low, int high){
        int pivot = arr[high]; // pivot choice last element
        int i = low-1;

        for(int j = low;j<=high;j++){
            if(arr[j] < pivot){
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // move pivot
        arr[high] = arr[i+1];
        arr[i+1] = pivot;
        return i+1;
    }

    static void quickSortAsc(int arr[], int low, int high){
        if(low < high) { // Base case coy
            int pivot = partitionAsc(arr, low, high);

            // D&Q
            quickSortAsc(arr, low, pivot-1);
            quickSortAsc(arr, pivot+1, high);
            
        }
    }

    static int partitionDesc(int arr[], int low, int high){
        int pivot = arr[high];
        int i = low-1;

        for(int j = low;j<=high;j++){
            if(arr[j] > pivot){
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // move pivot
        arr[high] = arr[i+1];
        arr[i+1] = pivot;
        return i+1;
    }

    static void quickSortDesc(int arr[], int low, int high){
        if(low < high){
            int pivot = partitionDesc(arr, low, high);

            // D&Q
            quickSortDesc(arr, low, pivot-1);
            quickSortDesc(arr, pivot+1, high);
        }
    }
    
    static void printArray(int arr[]){
        for(int a : arr){
            System.out.print(a + " ");
        }
        System.out.println();
    }
}


public class QuickLomuto {
    public static void main(String[] args) {
        int[] arrr = {9,2,4,51,2,3,7,84,2,4,10,21};
        quickSort(arrr, 0, arrr.length-1);
        printArray(arrr);
        
    }

    static void quickSort(int arr[], int low, int high){
        if(low < high){
            int pivot = lomutoPartition(arr, low, high);

            quickSort(arr, low, pivot-1);
            quickSort(arr, pivot+1, high);
        }
        
    }

    static int lomutoPartition(int arr[], int low, int high){
        int pivot = arr[high];
        int i = low;
        for(int j = low;j<high;j++){
            if(arr[j] < pivot){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }

        // int pivpos = ++i;
        int temp = arr[i];
        arr[i] = arr[high];
        arr[high] = temp; 
        return i;
    }

    static void printArray(int arr[]){
        for(int a : arr){
            System.out.print(a + " ");
        }
        System.out.println();
    }
    
}



public class QuickHoare {
    public static void main(String[] args) {
        int[] arrr = {9,2,4,51,2,3,7,84,2,4,10,21};
        quickSort(arrr, 0, arrr.length-1);
        printArray(arrr);
    }

    static void quickSort(int arr[], int low, int high){
        if(low < high){
            int pivot = hoare(arr, low, high);

            quickSort(arr, low, pivot-1);
            quickSort(arr, pivot+1, high);
        }
    }

    static int hoare(int arr[], int low, int high){
        int pivot = arr[low];
        int i = low-1;
        int j = high+1;
        while(true){
            do { 
                i++;
            } while (arr[i] < pivot);

            do { 
                j--;
            } while (arr[j] > pivot);

            if(i >= j){
                return j;
            }

            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    static void printArray(int arr[]){
        for(int a : arr){
            System.out.print(a + " ");
        }
        System.out.println();
    }
}