What is a quick sort algorithm and How to Write a Java Program to implement quick sort algorithm? So, let us first understand what quick sort algorithm is then will jump to write a java code to implement quicksort algorithm

What is quick sort algorithm?

Quick sort algorithm is a sorting algorithm that uses divide and conquer mechanism to sort an array. It uses a recursive approach for the same. The key element in the quick sort algorithm is the pivot. Quicksort partitions the array around the pivot element. Any element can be chosen as the pivot element – first element, last element, middle element, or any other element of your choice. In this tutorial, we will choose the last element as the pivot element.

The most important method in the quick sort algorithm is the partition() method. This method returns a partition element. The element is such that all the elements on the left side of the partition element are lesser than the partition element and all the elements on the right side of the partition element are greater than the partition element. We will understand the same diagrammatically.

Example of quick sort:

Input:

Enter the no. of elements:

5

Enter the array elements:

4 1 2 9

Output:

The sorted array is:

1 4 5 9

Algorithm for Quick Sort?

1. First, take no. of elements in an array and the array elements as input from the user.
2. The first index ( f ) is o and the last index ( l ) is n-1, where n is the no. of elements in the array.
3. We will then pass the first and last index in the sort() function. Inside sort() function, if the first index is found to be lesser than the last index, then call partition() function. The pivot element thus returned by the method will be used to sort it further on the left and right side of the pivot element.
4. The partition()  function returns the index of the pivot element. For this, we will choose the last element as the pivot. The variable i will be initialized to f-1 ( i.e. first index-1 ). We will then create a for loop that runs from j=f to j=l-1. If the pivot element is found to be greater than a[i], we will swap a[++i] element with a[j] element of the array. When the loop ends, we will again swap a[++i] element with a[l] element. Finally, return the value of i from the function. It is the index of the pivot element.
5. The array obtained is in a sorted manner. Simply, print the array.

Java Program for Quick Sort Algorithm

import java.util.Scanner;
public class QuickSort 
{
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the no. of elements in array:");
        int n=sc.nextInt();
        int a[]=new int[n];
        System.out.println("Enter the array elements:");
        for(int i=0;i<n;i++) a[i]=sc.nextInt();
        int f=0;
        int l=n-1;
        sort(a, f, l);
        System.out.println("The sorted array is:");
        for(int i=0;i<n;i++) System.out.print(a[i]+" ");
    }

    public static void sort(int a[], int f, int l) 
    {
        if(f<l)
  {
    int pos=partition(a,f,l);
    sort(a,f,pos-1);
    sort(a,pos+1,l);
  }
    }

    public static int partition(int a[], int f, int l) 
    {
        int pivot=a[l];
        int i,j;
  i=f-1;
  for(j=f;j<=l-1;j++)
  {
    if(pivot>=a[j])
    {
                    i=i+1;
                    int temp=a[i];
                    a[i]=a[j];
                    a[j]=temp;
    }
  }
        i=i+1;
        int temp=a[i];
        a[i]=a[l];
        a[l]=temp;
        return i;
    }
}

Output of the Quick Sort Algorithm: