Pages

Custom Search

Friday, March 23, 2012

Quicksort to sort elements in ascending order using the first element as the Pivot.



Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.
The steps are:
    -Pick an element, called a pivot, from the list.[Fisrt element in this program.]
    -Reorder the list so that all elements with values less than the pivot come before the pivot,      while all elements with values greater than the pivot come after it (equal values can go             either way).
      After this partitioning, the pivot is in its final position. This is called the partition operation.
    -Recursively sort the sub-list of lesser elements and the sub-list of greater elements.



Source Code:




 #include <stdio.h>  
 #include <stdlib.h>  
 int partition(int a[], int l, int r)  
 {  
     int p, i, j, t;  
     p = l;  
     i = l;  
     j = r;  
     while(i<j)  
     {  
          while((a[ i ] <= a[ p ]) && (i<r))  
          {  
             i++;  
          }  
          while(a[ j ] > a[ p ])  
          {  
             j--;  
         }  
         if(i<j)  
         {  
             t=a[ i ];  
             a[ i ] = a[ j ];  
             a[ j ] = t;  
         }  
     }  
     t=a[ p ];  
     a[ p ] = a[ j ];  
     a[ j ] = t;  
     return j;  
 }  
 void quicksort(int a[50], int l, int r)  
 {  
     int s;  
     if(l < r)  
     {  
         s=partition(a,l,r);  
         quicksort(a, l, s-1);  
         quicksort(a, s+1, r);  
     }  
 }  
 int main()  
 {  
     int a[50], l, r, i, n;  
     printf("\nEnter the size of the array: ");  
     scanf("%d", &n);  
     srand(time(NULL));  
     for(i=0;i<n;i++)  
     {  
         a[ i ] = rand()%50 + 1;  
     }  
     printf("\nThe elements of the array before sort are: \n");  
     for(i=0;i<n;i++)  
     {  
         printf("%d ", a[ i ]);  
     }  
     quicksort(a,0,n-1);  
     printf("\nThe elements of the array after sort are: \n");  
     for(i=0;i<n;i++)  
     {  
         printf("%d ", a[ i ]);  
     }  
     getch();  
 }  
Sample Output:





Custom Search