29.Quick Sort

Quicksort sorts a list based on the divide and conquer strategy. In quicksort algorithm we divide the list into two sub-lists, sort these sub-lists and recursively until the list is sorted; The basic steps of quicksort algorithm are as follows:

1. Choose a key element in the list which is called a pivot.
2. Reorder the list with the rule that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it. After the partitioning, the pivot is in its final position.
3. Recursively reorder two sub-lists: the sub-list of lesser elements and the sub-list of greater elements.

Quick Sort Program

#include<stdio.h>

int main(){

  int x[20],size,i;

  printf("\nEnter size of the array :");

  scanf("%d",&size);

  printf("\nEnter %d elements :",size);

  for(i=0;i<size;i++)

    scanf("%d",&x[i]);

  quicksort(x,0,size-1);

  printf("\nSorted elements :");

  for(i=0;i<size;i++)

    printf(" %d",x[i]);

  return 0;

}

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);

    }

}

Output of the Program:

Enter the size of the array:5

Enter 5 elements:6 8 5 9 3

Sorted elements:3 5 6 8 9

If you like this please Link Back to this article...

<a href="http://learning-tutorial.blogspot.com/2011/01/29quick-sort.html">29.Quick Sort</a>