Quicksort in C
Learn C - C tutorial - c program example quick sort - C examples - C programs
Quicksort in C
- Quicksort is a Divide and Conquer algorithm.
- Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation is defined.
- Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.
- It picks an element as pivot and partitions the given array around the picked pivot.
- There are many different versions of quicksort that pick pivot in different ways.
- Always pick first element as pivot.
- Always pick last element as pivot (implemented below)
- Pick a random element as pivot.
- Pick median as pivot.
Sample Code
#include<stdio.h>
void quicksort(int number[25],int first,int last)
{
int i, j, pivot, temp;
if(first< last)
{
pivot=first;
i=first;
j=last;
while(i< j)
{
while(number[i]<=number[pivot]&&i< last)
i++;
while(number[j]> number[pivot])
j--;
if(i< j)
{
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main()
{
int i, count=5, number[25]= {25,92,79,48,12};
printf("Entered elements: 5 ");
for(i=0; i< count; i++)
scanf("%d",& number[i]);
quicksort(number,0,count-1);
printf("\nOrder of Sorted elements:\n ");
for(i=0; i< count; i++)
printf(" %d",number[i]);
return 0;
}
Output
Entered elements: 5
Order of Sorted elements:
12 25 48 79 92