Monday, 22 March 2021

QuickSort Implementation In Java

This is a working solution of Quick Sort algorithm in Java. I haven't written the main method. You can add it & call quickSort(arr, 0, arr.length - 1) with your custom input array. Hope this Java program is self-explanatory.

class Solution
{
    //Function to sort an array using quick sort algorithm.
    static void quickSort(int arr[], int low, int high)
    {
        if(low >= high){
            return;
        }
        int sortedIndex = partition(arr, low, high);
        quickSort(arr, low, sortedIndex - 1);
        quickSort(arr, sortedIndex + 1, high);
    }
    
    static int partition(int arr[], int low, int high)
    {
        int pivot = high;
       
        /* keeps track of the current index where left-hand side
        elements are less than pivot element*/
        int index = low;
       
        for(int i=low; i < high; i++){
            if(arr[i] < arr[pivot]){
                swap(arr, i, index);
                index++;
            }
        }
       
        swap(arr, pivot, index);
        return index;
    }
    
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

No comments:

Post a comment

Evaluate Reverse Polish Notation In Java

Here is a fully working Java solution for evaluation of Reverse Polish Notation (Postfix Expression). This is a common interview question th...