Quick sort is an efficient sorting algorithm. It is even two or three times faster than mergesort and heapsort in some particular cases. The sorting
method compares n items in O(nlogn) time in average and best cases,
while it is O(n^2) in worst case. Quick sort comes under divide and conquer
algorithm which divides the large set of array in small by picking up a pivot
element as a reference element, and do sorting.
Algorithm:
(1) Make a list of items that need to be sorted, let’s
apply in an array.
(2) Choose a suitable element as pivot element from the
array list, because complexity largely depends on choosing the pivot element.
(3) Rearrange the array list so that all the elements
with value less than the pivot will come before the pivot and the element with
value greater will come after the pivot with in the same array, which make
pivot element in the sorted position.
(4) Apply recursively the third step to the sub array
of the element with smaller values and separate the sub array of the elements
with the greater values.
Note: In the following quicksort program, the first element is always used as the Pivot element for the remaining unsorted list.
#include<stdio.h>
#include<conio.h>
//quick Sort function to Sort Integer array list
void quicksort(int array[], int firstIndex, int
lastIndex) {
int pivotIndex, temp, index1, index2;
//assigninh first element index as pivot element
if(firstIndex < lastIndex)
{
pivotIndex = firstIndex;
index1 = firstIndex;
index2 = lastIndex;
//Sorting in Ascending order with quick sort
while(index1 < index2) {
while(array[index1] <= array[pivotIndex]
&& index1 < lastIndex) {
/* To sort in descending order, change to index1
> lastIndex */
index1++;
}
while(array[index2]>array[pivotIndex]) {
/* To sort in descending order, change > to <
*/
index2--;
}
//Swapping opertation
if(index1<index2)
{
temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}}
//At the end of first iteration, swap pivot element
with index2 element
temp = array[pivotIndex];
array[pivotIndex] = array[index2];
array[index2] = temp;
//Recursive call for quick sort, with partiontioning
quicksort(array, firstIndex, index2-1);
quicksort(array, index2+1, lastIndex);
}}
int main() {
int array[100],n,i;
printf("Enter How Many Data You Want To Sort:
");
scanf("%d",&n);
if(n<=0) printf("\n\tWrong Input?\t");
else {
printf("\n\nEnter %d Elements: ",n);
for(i = 0; i < n; i++) {
scanf("%d",&array[i]);
}
//calling quickSort function defined above
quicksort(array,0,n-1);
printf("\n\nAfter Sorting In Ascending Order:
");
for(i=0;i<n;i++)
printf(" %d",array[i]);
}
getch();
printf("\n\n");
}