In this article Quick Sort in C we give the information about take a elements from list called pivot from which all the left side of elements are smaller and all the right side elements are greater than pivot elements.
Quick Sort in C:
Introduction:
The idea behind this sorting is divide & conquer i.e. divide a big list of elements into two sub list.
In this methods, take a elements from list called pivot from which all the left side of elements are smaller and all the right side elements are greater than pivot elements. So one list is left side of pivot element and anther one is on right side of pivot.
The process of quick sort is as follows:
- Take first element of list as pivot.
- Place pivot at proper place in list. So one element of the list i.e. pivot will be at its proper place.
- Create two sub list left and right side of pivot.
- Repeat the same process until all elements of list are at proper position in list.
For placing the pivot at proper place do the following process:
- Compare the pivot elements one by one from right to left for getting the elements, which has value less than pivot element.
- Interchange the elements with pivot element.
- Now the comparison will start from the interchange element position from left to right for getting the element, which has higher value than pivot.
- Repeat the same process until pivot is at its proper position.
Quick sort example:
Consider the following elements:
51 28 8 62 73 90 44 74 96
Take 51 as pivot and start comparison from right to left.
Now the first element less than 51 is 44. So interchange 44 with pivot i.e. 51.
44 28 8 62 73 90 51 74 96
Now the comparison will start from 44 and will be form left to right. The first element greater than 51 is 62. So interchange it with pivot.
44 28 8 51 73 90 62 74 96
Now the comparison will start from 51 and will be from right to left. There is no element less than 51 so now 51 is at its proper position in the list.
Now we can divide the list into two sub lists, left and right side of pivot.
44 28 8 51 73 90 62 74 96
Sub-List 1: 44 28 8
Sub-List 2: 73 90 62 74 96
Repeat the same process for sub list 1 and sub list 2.
Sub list 1: 44 28 8
Take 44 as pivot and start comparison from right to left.
Now the first element less than 44 is 8 so interchange 8 with pivot i.e. 44.
8 28 44
Now the comparison will start from 44 and will be from left to right. There are no elements greater than 44 so now 44 is at its proper position in the list.
Also sub-list 1 is properly arranged is ascending order.
8 28 44
Sub list 2: 73 90 62 74 96
Take 73 as pivot and start comparison from right to left.
Now the first element less than 73 is 62 so interchange 62 with pivot i.e. 73
62 90 73 74 96
Now the comparison will start from 62 and will be from left to right. The first element greater than 73 is 90 so interchange it with pivot.
62 73 90 74 96
Now the comparison will start from 73 and will be from right to left. There is no element less than 73 so now 73 is at its proper position in the list.
Now we can divide the list into two sub lists, left and right side of pivot.
62 73 90 74 96
Sub list 3: 62
Sub list 4: 90 74 96
Sub list 3 only one element so sorted.
Sub list 4: 90 74 96
Take 90 as pivot and start comparison from right to left.
Now the first element less than 90 is 74 so interchange 74 with pivot i.e. 90
74 90 96
Now the comparison will start from 74 and will be form right to left. There is no element less than 74. So now 74 is at its proper position in the first and all its arrange in ascending order.
Now we observed sub list 1, sub list 2, sub list 3 and sub list 4 arrange the data in ascending order.
Now the elements are in sorted order.
8 28 44 62 73 74 90 96.
// Quick Sort Program in C
#include<stdio.h>
#include<conio.h>
void quicksort(int number[30],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);
}
}
void main()
{
int i, count, number[30];
printf(“\n How many elements are you going to enter?: “);
scanf(“%d”,&count);
for(i=0;i<count;i++)
scanf(“%d”,&number[i]);
printf(“\nArray before Sorted: “);
for(i=0;i<count;i++)
printf(“\t%d”,number[i]);
quicksort(number,0,count-1);
printf(“Array after Sorted: “);
for(i=0;i<count;i++)
printf(” %d”,number[i]);
getch();
}
O/P:-
How many elements are you going to enter?: 5
52 4 15 66 3
Array before Sorted: 52 4 15 66 3
Array After Sorted: 3 4 15 52 66
Some More:
POP- Introduction to Programming Using ‘C’
OOP – Object Oriented Programming
DBMS – Database Management System
RDBMS – Relational Database Management System
Join Now: Data Warehousing and Data Mining