hanreev

Sorting and Searching using Recursion

Jul 24th, 2017
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.91 KB | None | 0 0
  1. /*
  2.  * C Program to Perform Binary Search using Recursion
  3.  */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7.  
  8. void binary_search(int [], int, int, int);
  9. void quicksort (int [], int, int);
  10.  
  11. int main()
  12. {
  13.     int key, size, i;
  14.     int list[50];
  15.  
  16.     printf("Enter size of a list: ");
  17.     scanf("%d", &size);
  18.  
  19.     printf("Generating random numbers\n");
  20.     for(i = 0; i < size; i++)
  21.     {
  22.         list[i] = rand() % 100;
  23.         printf("%d  ", list[i]);
  24.     }
  25.  
  26.     quicksort(list, 0, size - 1);
  27.  
  28.     printf("\n\nSorted random numbers\n");
  29.     for(i = 0; i < size; i++)
  30.     {
  31.         printf("%d  ", list[i]);
  32.     }
  33.  
  34.     printf("\n\nEnter key to search\n");
  35.     scanf("%d", &key);
  36.     binary_search(list, 0, size, key);
  37. }
  38.  
  39. void quicksort(int list[], int low, int high)
  40. {
  41.     int pivot, i, j, temp;
  42.     if (low < high)
  43.     {
  44.         pivot = low;
  45.         i = low;
  46.         j = high;
  47.         while (i < j)
  48.         {
  49.             while (list[i] <= list[pivot] && i <= high)
  50.             {
  51.                 i++;
  52.             }
  53.             while (list[j] > list[pivot] && j >= low)
  54.             {
  55.                 j--;
  56.             }
  57.             if (i < j)
  58.             {
  59.                 temp = list[i];
  60.                 list[i] = list[j];
  61.                 list[j] = temp;
  62.             }
  63.         }
  64.         temp = list[j];
  65.         list[j] = list[pivot];
  66.         list[pivot] = temp;
  67.         quicksort(list, low, j - 1);
  68.         quicksort(list, j + 1, high);
  69.     }
  70. }
  71.  
  72. void binary_search(int list[], int lo, int hi, int key)
  73. {
  74.     int mid;
  75.  
  76.     if (lo > hi)
  77.     {
  78.         printf("Key not found\n");
  79.         return;
  80.     }
  81.     mid = (lo + hi) / 2;
  82.     if (list[mid] == key)
  83.     {
  84.         printf("Key found\n");
  85.     }
  86.     else if (list[mid] > key)
  87.     {
  88.         binary_search(list, lo, mid - 1, key);
  89.     }
  90.     else if (list[mid] < key)
  91.     {
  92.         binary_search(list, mid + 1, hi, key);
  93.     }
  94. }
Advertisement
Add Comment
Please, Sign In to add comment