In this article we will discus about quick sort which is one of the sorting algorithm. The Quick sort algorithm uses divide and conquer strategy. First divide the unsorted array into multiple sub arrays and then recursively sort the sub-arrays and combine them to obtain a solution.
The division of sub-arrays are based on pivot element. First select the pivot element from the array and then divide the array into two parts such that the elements which are smaller than pivot element are placed to the left side and the elements which are larger than pivot element are placed to the right side of pivot element.
This process continues until the array contains a single element in an array and here all the elements become sorted so the elements are combined to get a sorted array.
Pivot Element
Pivot element is the element of an array. We can either pick any random element as a pivot element or we take either the leftmost element or the right most element.
Example
quick sort java code
package gangforcode;
import java.util.*;
public class quickSort
{
static void quicksort(int arr[],int s,int e){
if(s>=e){
return;
}
int p=partition(arr,s,e);
quicksort(arr,s,p-1);
quicksort(arr,p+1,e);
}
static void swap(int arr[],int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
static int partition(int arr[],int s,int e){
int pivot=arr[s];
int count=0;
for(int i=s+1;i<=e;i++){
if(arr[i]<=pivot){
count++;
}
}
int pivoitindex=s+count;
swap(arr,pivoitindex,s);
int i=s;
int j=e;
while(i<pivoitindex && j>pivoitindex){
while(arr[i]<pivot){
i++;
}
while(arr[j]>pivot){
j--;
}
if(i<pivoitindex && j>pivoitindex){
//swap(arr[i++],arr[j--]);
swap(arr,i++,j--);
}
}
return pivoitindex;
}
public static void main(String[] args) {
int arr[]={2,4,6,5,1,9};
int n=5;
quicksort(arr,0,n-1);
System.out.println(Arrays.toString(arr));
}
}
Output –
