QuickSort is a sorting algorithm which follows Divide and Conquer apporach. It picks an element as pivot and partitions the given array around the picked pivot.
There are many different ways quickSort to pick pivot element.
- pick last element as pivot.
- pick first element as pivot (implemented below)
- Pick a random element as pivot.
- Pick median as pivot
Pseudo Code for QuickSort function :
quickSort(arr[], low, high)
{
if (low < high)
{
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
Pseudo code for partition()
partition (arr[], low, high)
{
// pivot (Element to be placed at right position)
pivot = arr[high];
i = (low - 1) // Index of smaller element
for (j = low; j <= high- 1; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap arr[i] and arr[j]
}
}
swap arr[i + 1] and arr[high])
return (i + 1)
}
Quick Sort Program
class QuickSort
{
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; //take last element as pivot
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
if (arr[j] < pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and pivot
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
void sort(int arr[], int low, int high)
{
if (low < high)
{
/* here partiton function returns pivot element index so we
will collect it in integer variable
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
//function to print array
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
//main method
public static void main(String args[])
{
int arr[] = {50, 4, 7, 13, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);
System.out.println("sorted array");
printArray(arr);
}
}
Output:
Sorted array: 1 4 5 7 13 50 Time Complexity : 1. Best Case O(N) 2. Worst case O(N^2) 3.Average Case O(N)
Hope you guys understand the concept of Quick Sort
Thank You, Happy Coding
THE NUCLEAR GEEKS 
One thought on “Quick Sort in java”