Skip to content

Instantly share code, notes, and snippets.

@anubhavshrimal
Created March 1, 2016 20:18
Show Gist options
  • Save anubhavshrimal/4b6d44abc909a6f1c805 to your computer and use it in GitHub Desktop.
Save anubhavshrimal/4b6d44abc909a6f1c805 to your computer and use it in GitHub Desktop.
quick sort an array using pivot as last element
#include <stdio.h>
#include <stdlib.h>
#define max 10001
void quickSort(int a[],int l,int r);
int partition(int a[],int l,int r);
//main function definition
int main()
{
int size,i,a[max];
printf("Enter the array size: ");
scanf("%d",&size);
//getting the array input
printf("Enter the array elements:\n ");
for(i=0;i<size;i++)
scanf("%d",&a[i]);
//calling quick sort function for the array
quickSort(a,0,size);
//displaying the sorted array
printf("After quick sorting the array:\n ");
for(i=0;i<size;i++)
printf("%d ",a[i]);
return 0;
}
//quickSort function definition
void quickSort(int a[],int l,int r)
{
if(l<r)
{
int q=partition(a,l,r); //finding the pivot position in sorted array
quickSort(a,l,q-1); //recursive calling before pivot sub array
quickSort(a,q+1,r); //recursive calling after pivot sub array
}
}
//partition function definition
int partition(int a[],int l,int r)
{
int j,temp,i=l;
for(j=l;j<r-1;j++)
{
//swap values if a[j]<=a[r-1](i.e. pivot)
if(a[j]<=a[r-1])
{
temp=a[j];
a[j]=a[i];
a[i]=temp;
i++;
}
}
//place pivot at its position by swapping
temp=a[i];
a[i]=a[r-1];
a[r-1]=temp;
return i;
}
@viveks4ever
Copy link

Output :-
Enter the array size: 7
Enter the array elements:
7
2
1
6
8
5
3
After quick sorting the array:
2 1 3 6 5 7 8

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment