Quicksort is based on Divide and Conquer paradigm. It works by partitioning the given input array into two subarrays and sorts them through recursive calls until they get sorted.
In this, a pivot element is used that acts as a base for partitioning the array, where element lesser than pivot element arranged at the left side and bigger ones at the right side.
It requires O(n log n) running time to sort the given array when it comes to the average case.
Therefore, it can be used to sort a large set of elements. However, in the worst case, the running time of this algorithm hops up to O(n2).
Pseudocode
Quicksort( Array,first,last) IF first <last partitionpoint = Partition(arr,first,last); Quicksort(Array,first,partitionpoint-1) Quicksort(Array,partitionpoint+1,last)
Partitioning
Partition(Array,first,last) pivot = arr[last] i=first-1 FOR j=first to last - 1 IF Array[j]<pivot i=i+1 exchange Array[i] with Array[j] END IF END FOR exchange Array[i] with Array[last] return i+1
C program to sort an array using Quicksort in Ascending Order
#include<stdio.h>
#define size 5
void quicksort(int arr[],int first,int last)
{
if(first <last)
{
int partitionpoint;
partitionpoint = sort_me(arr,first,last);
quicksort(arr,first,partitionpoint-1);
quicksort(arr,partitionpoint+1,last);
}
}
int sort_me(int arr[],int first,int last)
{
int pivot = arr[last],j,temp,n;
int i=first-1;
for(j=first;j<last;j++)
{
if(arr[j]<pivot)
{
i++;
temp =arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
temp =arr[i+1];
arr[i+1]=arr[last];
arr[last]=temp;
return i+1;
}
int main()
{
int arr[size],j,temp,n;
printf("Please enter elements: \n ");
for(n=0;n<=size-1;n++)
{
scanf("%d",&arr[n]);
}
quicksort(arr,0,size-1);
printf(" \n Sorted Elements :");
for(n=0;n<=size-1;n++)
{
printf("\n %d ",arr[n]);
}
return 0;
}
Output:
