Quick Sort in Java

Quick Sort in Java.

---

Given a unsorted array, Sort it using Quick Sort Algorithm.

Merge sort linked list java

Lets understand what is the input and the expected output.

Algorithm (We will use Quick Sort for sorting Array.)

---

How Quick Sort works

1. If the array contains only one element than it already sorted, no need to sort.
2. If the array contains more than one element then,
1. Select middle element from the array and lets call it pivot element. 
2. Scan the array with two pointers start and end, start pointing to first index 0 and end pointing to last index = arr.length-1.
3. find element from start that is less than pivot, and find element from end that is higher than pivot.
4. if we find such element swap those, increment start, decrement end, continue search.
3. What we are trying to achieve by this is to find all elements which are smaller than the pivot element are placed on left side of pivot and elements which are larger are placed on right side of pivot. 
4. If we do this, it means pivot is now at its correct position and remaining item to sort is left subarray from pivot and right subarray from pivot.
5. Example: 
1. {4, 9, 2, 8, 11, 1, 10}; start = 4; end = 10; pivot = 8
2. Swap 9 with 1 {4, 1, 2, 8, 11, 9, 10};
3. Now pivot 9 is at its correct position and left subarray {4,1,2} and right subarray {11,9,10} is pending to sort, 
4. repeat the steps for left and right subarrays
6. Quicksort is "in-place" algorithm, this means that the sorting takes place in the array and that no additional space is required.

Quicksort complexity in worst case is O(N^2)
Quicksort complexity in best and average case is O(N Log N)

Sorting Array using Quick sort in Java. 

---

package com.javabypatel.sort;

public class QuickSortDemo {
    public static void main(String[] args) {

        int arr[] = {4, 9, 2, 8, 11, 1, 10};

        quickSort(arr, 0, arr.length-1);

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

    private static void quickSort(int[] arr, int start, int end) {
        int i = start;
        int j = end;

        int pivot = start + (end - start) / 2;

        //we are doing i<=j because we want pointers to get crossed of pivot and then stop
        //example if array is {4, 1, 2, 8, 11, 1, 10}, pivot is at 8, so we want i should point after pivot that is at 11
        //and j to point at 2 after loop ends.
        while (i <= j) {
            //increment i if element at i is less than pivot,
            //If array is {4, 9, 2, 8, 11, 1, 10}, pivot is 8(mid) and i is pointing to first element 4,
            //We want to move all element that are higher than pivot(8) to right of pivot and only keep element less than 8 on left.
            //increment i till we find element greater than 8, (i will stop at 9)
            while (arr[i] < arr[pivot]) { i++; }

            //increment j if element at j is greater than pivot,
            //If array is {4, 9, 2, 8, 11, 1, 10}, pivot is 8(mid) and j is pointing to last element 10,
            //We want to move all element that are less than pivot(8) to left of pivot and only keep element greater than 8 on right.
            //increment j till we find element less than 8, (j will stop at 1)
            while (arr[j] > arr[pivot]) {
                j--;
            }

            //if we find any element on left of pivot that is greater and on right that is less than pivot, swap them.
            //if say array is already sorted in that case i would cross j, so we check swap only if i < j.
            //After swapping increment pointers and continue for rest of elements on left and right of pivot
            if(i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }

        //After coming out of above loop, array will be {4, 1, 2, 8, 11, 9, 10}
        //If you observe pivot element is now at its correct position,
        //only remaining elements to sort is left of pivot {4, 1, 2} and right of pivot {11, 9, 10}

        //sort left sub-array of pivot
        //If j is greater than start, it means we have something on left of pivot remaining to sort
        if(start < j) {
            //After coming out of above loop, array will be {4, 1, 2, 8, 11, 9, 10}, j would be pointing to 2 and start is pointing to 4.
            //So we will sort {4, 1, 2}
            quickSort(arr, start, j);
        }

        //sort right sub-array of pivot
        //If i is less than end, it means we have something on right of pivot remaining to sort
        if(i < end) {
            //After coming out of above loop, array will be {4, 1, 2, 8, 11, 9, 10}, i would be pointing to 11 and end is pointing to 10.
            //So we will sort {11, 9, 10}.
            quickSort(arr,  i, end);
        }
    }

}

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.