Quick Sort

Quick Sort: This algorithm is also based on the divide and conquer approach. It reduces the space complexity and removes the use of auxiliary array used in merge sort.

Idea: It is based on the idea of choosing one element as pivot element and partitioning the array around it such that the left side of pivot contains all elements less than the pivot element and right side contains all elements greater than the pivot.

Selecting a random pivot in an array results into an improved time complexity in average cases.

Implementation:
Choose the first element of array as pivot element First, we will see how the partition of the array takes place around the pivot.

Example: you have an array A[]={9,7,8,3,2,1}.

import java.util.Scanner;

class Quick

{

void sort(int a[],int start,int end)

{

if(start<end)

{

int pos=partition(a,start,end);

sort(a,start,pos);

sort(a,pos+1,end);

}

}

int partition(int a[],int start,int end)

{

int piv=a[start];

int pindex=start+1;

for(int i=start+1;i<end;i++)

{

if(a[i]<=piv)

{

int temp=a[i];

a[i]=a[pindex];

a[pindex]=temp;

pindex=pindex+1;

}

}

pindex=pindex-1;

int x=a[pindex];

a[pindex]=a[start];

a[start]=x;

return pindex;

}

}

class QuickTest

{

public static void main(String args[])

{

Quick q1=new Quick();

Scanner sc=new Scanner(System.in);

System.out.println("enter the total number of elements:");

int n=sc.nextInt();

int arr[]=new int[n];

for(int i=0;i<n;i++)

{

System.out.printf("enter the %d elements:",(i+1));

arr[i]=sc.nextInt();

}

q1.sort(arr,0,n);

System.out.println("the sorted array is:");

for(int i=0;i<n;i++)

{

System.out.println(arr[i]);

}

}

}

Complexity:The worst case time complexity of this algorithm is O(n²),but as this is randomized algorithm,its time complexity fluctuates between O(n²) and O(n(log n) ) and mostly it comes out to be O(n(log n)) .