Simple Way to Learn Quick Sort in Java Using Recursion Technique

Quick Sort Explanation in JAVA
Point to remember before start quick sort

Quick Sort is developed by Tony Hoare in 1959 and published in 1961.

• Quick sort is sometimes called as partition exchange sort.

• It is an efficient sorting algorithm serving as a systematic method for placing the elements of an array in order.

• The three step of quick sort algorithm are as follows :

1. Divide : Rearrange the elements and split the array into two sub array and an element (known as pivot) in between such that each element in the left subarray is less than or equal to pivot elements and each element in the right subarray is greater than the pivot element.
2. Conquer : Recursively sort the two subarrays.
3. Combine : Recursively sort the two subarrays.

• Three option to choose pivote elements are : 

1. Left end or right end.this could give O(n^2) permanence depending on the input so this is a bad choice but easiest to implements.
2. Best of 3 left middle or right.this gives substantially better permanence than simply choosing an end in the worst case
3. Random.choosing a random pivote is family easy to implements.

Program :

public class QuickSort {

    public static void main(String[] args) {

        int arr[]={15,9,7,13,12,16,4,18,11};

        int length=arr.length;

        QuickSort qs=new QuickSort();

        qs.quickSortRecursion(arr,0,length-1);

        qs.printArray(arr);

    }

    int partition(int[] arr, int low, int high){

        int pivot=arr[low]; //taking lower index pivot value

        while (low<=high){

            while (arr[low]<pivot){

                low++;

            }

            while (arr[high]>pivot){

                high--;

            }

            if (low<=high){

                int temp=arr[low];

                arr[low]=arr[high];

                arr[high]=temp;

                low++;

                high--;

            }

        }

        return low;

    }

     void quickSortRecursion(int []arr,int low,int high){

        int pi=partition(arr,low,high);

        if (low<pi-1){

            quickSortRecursion(arr, low, pi-1);

        }

        if (pi<high){

            quickSortRecursion(arr, pi, high);

        }

    }

    void printArray(int[]arr){

        for (int i:arr){

            System.out.print(i+" ");

        }

    }

}

Output : 

Click to next or Searching Programs

• Bubble Sort
• Insertion Sort
• Selection Sort
• Merge Sort
• Linear Search and 
• Binary Search

Start with your Choice

-Important Programs for Freshers

• Palindrome Number
• Prime Number
• Swapping Number
• Leap Year
• Odd and Even Number
• Fibonacci Series
• Armstrong Number
• Factorial Number
• Print Table

Learn Pattern Programs 

• Alphabet pattern program in java
• Star Pattern Programs in Java
• Square pattern programs in java
• Diamond Star pattern programs in java
• Number Pattern Programs in java
• Diagonal pattern program in java

Click to learn Array Programs

• 4 ways to print Array in Java
• 2D Array in Java
• Anonymous Array in Java
• Single Dimensional  Array in Java
• Find Second Largest Number in Array
• Delete an Element in Array in Java 
• Common Element in Array in Java
• Missing Element in Array
• Insert Element in Array
• Reverse Array in Java
• Merge Two Array in Java
• Smallest and Largest Elements in Array
• Find Odd and Even Number in Array

Click to Learn MySQL 

• MySQL Database
• Table & View
• MySQL Query
• Clauses
• Conditions
• MySQL Function
• Join
•  Indexes
• Triggered

for any complaint regarding my Blog please visit contact us page and write what problem you have!

Learn with us | HTML | CSS | JS | Bootstrap | JAVA | ADV JAVA | MySQL | GIT