Summary: In this tutorial, we will learn what the Quicksort algorithm is, how it works, and how to sort an array using the Quicksort algorithm in C, C++, and Java.
Introduction to QuickSort Algorithm
Quicksort is a divide-and-conquer algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
Wikipedia
The Quicksort algorithm recursivley selects a pivot element and partition the array into two sub-arrays around it.
The partition is done by moving the smaller elements to the left sub-array and larger element to the right sub-array.
This process is repeated recursively for the sub-arrays until the sub-array is left with only a single element.
For example, consider the following sorting of an array using the Quicksort Algorithm:
The blue element is the pivot element of the respective sub-array.
After selecting the pivot element we shift other elements accordingly – If less, it is shifted to the left of the pivot otherwise to its right.
The position of the pivot element after the partition is its final correct position in the sorted array.
This process is repeated for every partition (sub-array) i.e. every time we select a pivot element we move it to its correct final position by partitioning and shifting other elements.
Since the process of selecting a pivot element and partitioning others happens on the same array, the array gets sorted in the process.
Quicksort Algorithm
- Choose a pivot element i.e.
pivot element = array[startIndex]. - Shift all the elements to the left of the pivot element which is less than the pivot element.
- Again shift all the elements to the right of the pivot element which is greater than the pivot element.
- The final index of the pivot element is the dividing point of the array.
- Repeat the process (again from step-1) for the subarrays until the sub-array is left with a single element.
Note: On starting we assumed pivot element = array[startIndex]. Here startIndex is the first index of the array or sub-array.
Here is the implementation of the Quicksort Algorithm in C, C++, Java, and Python:
Python
def findPivot(arr, s, e):
element = arr[s]
i = s
j = e-1
while i<j and arr[j]>element:
j = j-1
arr[i] = arr[j]
while i<j and arr[i]<element:
i = i+1
arr[j] = arr[i]
arr[i] = element
if i<j:
return findPivot(arr, i, j)
return i
def quickSort(arr, s, e):
if s >= e:
return
pivot = findPivot(arr, s, e)
quickSort(arr, s, pivot)
quickSort(arr, pivot+1, e)
if __name__ == '__main__':
arr = [8, 36, -51, 9, 21, 46, 2]
print(arr)
quickSort(arr, 0, len(arr))
print(arr)C
#include <stdio.h>
void quickSort(int [],int , int );
int findPivot(int [],int,int);
int main()
{
int arr[] = {5, -6, 22, 37, 4, -11, 15};
printf("Unsorted Array: \n");
for(int i=0; i<7; i++){
printf("%d ",arr[i]);
}
printf("\n ");
quickSort(arr,0,7);
printf("Sorted Array: \n");
for(int i=0; i<7; i++){
printf("%d ",arr[i]);
}
return 0;
}
void quickSort(int arr[], int s, int e){
if(e-s < 1)
return;
int p = findPivot(arr,s,e);
quickSort(arr,s,p);
quickSort(arr,p+1,e);
}
int findPivot(int arr[], int s, int e){
int newElement = arr[s];
int i = s, j = e;
while(i<j && arr[--j] > newElement);
arr[i] = arr[j];
while(i<j && arr[++i] < newElement);
arr[j] = arr[i];
arr[i]= newElement;
if (j>i)
return findPivot(arr,i,j);
else
return i;
}C++
#include <iostream>
using namespace std;
void quickSort(int [],int , int );
int findPivot(int [],int,int);
int main()
{
int arr[] = {5, -6, 22, 37, 4, -11, 15};
cout << "Unsorted Array:" << endl;
for(int i=0;i<7;i++){
cout << arr[i] << " ";
}
cout<<endl;
quickSort(arr,0,7);
cout << "Sorted Array:" << endl;
for(int i=0;i<7;i++){
cout << arr[i] << " ";
}
return 0;
}
void quickSort(int arr[], int s, int e){
if(e-s < 1)
return;
int p = findPivot(arr,s,e);
quickSort(arr,s,p);
quickSort(arr,p+1,e);
}
int findPivot(int arr[], int s, int e){
int newElement = arr[s];
int i = s, j = e;
while(i<j && arr[--j] > newElement);
arr[i] = arr[j];
while(i<j && arr[++i] < newElement);
arr[j] = arr[i];
arr[i]= newElement;
if (j>i)
return findPivot(arr,i,j);
else
return i;
}Java
public class App {
public static void main(String args[]){
int arr[] = {5, -6, 22, 37, 4, -11, 15};
QuickSort qs = new QuickSort(arr);
System.out.println("Unsorted Array:");
for(int i=0; i<7; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
qs.sort(0,7);
System.out.println("Sorted Array:");
for(int i=0; i<7; i++){
System.out.print(arr[i]+" ");
}
}
}
public class QuickSort {
int arr[];
public QuickSort(int[] arr) {
this.arr = arr;
}
public void sort(int s, int e){
if(e-s < 1){
return;
}
int p = findPivot(s,e);
sort(s,p);
sort(p+1,e);
}
private int findPivot(int s, int e) {
int newElement = arr[s];
int i = s, j = e;
while(i<j && arr[--j] > newElement);
arr[i] = arr[j];
while(i<j && arr[++i] < newElement);
arr[j] = arr[i];
arr[i]= newElement;
if (j>i)
return findPivot(i,j);
else
return i;
}
}Output:
Unsorted Array: 5 -6 22 37 4 -11 15 Sorted Array: -11 -6 4 5 15 22 37
In the above program, the findPivot(...) function is sorting the array as stated in the algorithm and the quickSort(...) function is dividing the array into sub-arrays at index being returned by findPivot(...) function.
Quick Sort Overview:
- In-place Algorithm: No need for extra arrays.
- O(nlog2n) time complexity: The array is repeatedly being partitioned into two sub-arrays.
- Unstable algorithm: Interchanging of duplicate values, which is useless.
Quicksort performs better than Merge sort because it doesn’t require an extra array for the sort process, but is less efficient than Insertion sort.
In this tutorial we learned, what the Quick sort algorithm is, how it works and how to implement Quicksort algorithm in C, C++, and Java to sort an array.