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:





Wednesday, February 29, 2012

Merge-sort for sorting elements in ascending order.

Merge-sort:
It is a sorting technique that sequences data by continuously merging items in the list. Every single item in the original unordered list is merged with another, creating groups of two. Every two-item group is merged, creating groups of four and so on until there is one ordered list.


Source Code:

 #include <stdio.h>  
 #include <stdlib.h>  
 int c[50];  
 void merge(int b[], int low,int mid,int high)  
 {  
     int i, j, k=low;  
     i = low;  
     j = mid+1;  
     while((i <= mid) && (j <= high))   //Comparing & inserting items in new ordered list  
     {  
         if(b[i] <= b[j])  
             c[k++] = b[i++];  
         else  
             c[k++] = b[j++];  
     }  
     while(i <= mid)        //Inserting remaining items from 1st half in new list  
         c[k++] = b[i++];  
     while(j <= high)       //Inserting remaining items from 2nd half in new list  
         c[k++] = b[j++];  
     for(k=low;k<=high;k++)  
         b[k] = c[k];  
 }  
 void mergesort(int a[], int low, int high)  
 {  
     int mid;  
     if(low<high)  
     {  
         mid = (low+high)/2;  
         mergesort(a,low,mid);           //Dividing the list into two - 1st half  
         mergesort(a,mid+1,high);         // 2nd half  
         merge(a,low,mid,high);          //Merging the lists  
     }  
 }  
 int main()  
 {  
     int a[50], i, n;  
     double e,s,t;  
     printf("\nEnter the size of the array: ");  
     scanf("%d", &n);  
     srand(time(NULL));  
     for(i=1;i<=n;i++)  
         a[i] = rand()%50 +1;  
     printf("\nElements of the array are: ");  
     for(i=1;i<=n;i++)  
         printf("%d ", a[i]);  
     mergesort(a,1,n);  
     printf("\nThe sorted array is: ");  
     for(i=1;i<=n;i++)  
         printf("%d ", c[i]);  
 }  



Sample Output:



Monday, February 13, 2012

Binary Search recursive program.


Binary Search is a program where in the input array is sorted i.e., ascending order in this case. Every time the array is split into two parts and the middle element is compared with the key element to be searched.

Source Code:


 #include <stdio.h>  
 #include <stdlib.h>  
 int bin_srch(int a[], int n, int key, int low, int high)  
 {  
     int mid;  
     if(low <= high)  
    {  
         mid = (low + high)/2;  
         if(a[mid] == key)  
         {  
             return mid;  
          }  
          else if(key < a[mid])  
         {  
             return bin_srch(a, n, key, low, mid-1);  
          }  
          else if(key > a[mid])  
         {  
             return bin_srch(a, n, key, mid+1, high);  
          }  
     }  
     else  
     {  
          return -1;  
     }  
 }  
 int main()  
 {  
     int a[10], n, key, low, mid, high, i, indx;  
     printf("\nEnter size of array: ");  
     scanf("%d", &n);  
     printf("\nEnter elements of array: ");  
     for(i=0;i<n;i++)  
     {  
          scanf("%d", &a[i]);  
     }  
     printf("\nEnter the key element to be searched: ");  
     scanf("%d", &key);  
     low = 0;  
     high = n-1;  
     indx = bin_srch(a, n, key, low, high);  
     if(indx == -1)  
     {  
          printf("\nSearch unsuccessful");  
      }  
      else  
      {  
          printf("\nElement found at position %d\n\n", indx+1);  
      }  
 }  
Custom Search