Problem Link:
Difficulty:
Easy-Medium
Prerequisites:
Basic Sorting
Problem:
You’re given an array ar and a number p. Partition the array, so that all elements greater than p are to its right, and all elements smaller than p are to its left. p is called the pivot of the partition.
Explanation:
Initially read the size of the array or the number of elements and the array elements.
- Pick one element in the array, which will be the pivot.
- Make one pass through the array, called a partition step, re-arranging the entries so that:
• the pivot is in its proper place.
• entries smaller than the pivot are to the left of the pivot.
• entries larger than the pivot are to its right. - Recursively apply quicksort to the part of the array that is to the left of the pivot, and to the right part of the array.
Here we don’t have the merge step, at the end all the elements are in the proper order.
Solution:
#include<stdio.h>
void quicksort(int [10],int,int);
int main()
{
int x[20],size,i;
//printf(“Enter size of the array: “);
scanf(”%d”,&size);
//printf(“Enter %d elements: “,size);
for(i=0;i<size;i++)
scanf(”%d”,&x[i]);
quicksort(x,0,size-1);
//printf(“Sorted elements: “);
for(i=0;i<size;i++)
printf(” %d”,x[i]);
return 0;
}
void quicksort(int x[10],int first,int last)
{
int pivot,j,temp,i;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j)
{
while(x[i]<=x[pivot]&&i<last)
i++;
while(x[j]>x[pivot])
j–;
if(i<j){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}