C Program to Implement Bitonic Sort

This C Program implements bitonic sort.

Here is source code of the C Program to implement bitonic sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  *  C Program to Implement Bitonic sort
  3.  */
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #define MAX 8
  7. #define SWAP(x,y) t = x; x = y; y = t;
  8.  
  9. void compare();
  10. void bitonicmerge(int, int, int);
  11. void recbitonic(int, int, int);
  12. void sort();
  13.  
  14. int data[MAX];
  15. int up = 1;
  16. int down = 0;
  17.  
  18. int main()
  19. {
  20.     int i;
  21.  
  22.     printf("\nEnter the data");
  23.     for (i = 0;i < MAX ;i++)
  24.     {
  25.         scanf("%d", &data[i]);
  26.     }
  27.     sort();
  28.     for (i = 0;i < MAX;i++)
  29.     {
  30.         printf("%d ", data[i]);
  31.     }
  32. }
  33. /*
  34.  * compare and swap based on dir
  35.  */
  36. void compare(int i, int j, int dir)
  37. {
  38.     int t;
  39.  
  40.     if (dir == (data[i] > data[j]))
  41.     {
  42.         SWAP(data[i], data[j]);
  43.     }
  44. }
  45. /*
  46.  * Sorts a bitonic sequence in ascending order if dir=1
  47.  * otherwise in descending order
  48.  */
  49. void bitonicmerge(int low, int c, int dir)
  50. {
  51.     int k, i;
  52.  
  53.     if (c > 1)
  54.     {
  55.          k = c / 2;
  56.         for (i = low;i < low+k ;i++)
  57.             compare(i, i+k, dir);    
  58.         bitonicmerge(low, k, dir);
  59.         bitonicmerge(low+k, k, dir);    
  60.     }
  61. }
  62. /*
  63.  * Generates bitonic sequence by sorting recursively
  64.  * two halves of the array in opposite sorting orders
  65.  * bitonicmerge will merge the resultant data
  66.  */
  67. void recbitonic(int low, int c, int dir)
  68. {
  69.     int k;
  70.  
  71.     if (c > 1)
  72.     {
  73.         k = c / 2;
  74.         recbitonic(low, k, up);
  75.         recbitonic(low + k, k, down);
  76.         bitonicmerge(low, c, dir);
  77.     }
  78. }
  79.  
  80. /*
  81.  * Sorts the entire array
  82.  */
  83. void sort()
  84. {
  85.     recbitonic(0, MAX, up);
  86. }

$ gcc bitonicsort.c
$ a.out
/*
 * Average case
 */
Enter the data
3 5 8 9 7 4 2 1
1  2  3  4  5  7  8  9
$  a.out
/*
 *Worst case
 */
Enter the data
100 99 98 97 96 95 94 93
93  94  95  96  97  98  99  100
 
$  a.out
/*
 *Best case
 */
Enter the data
1111 2222 3333 4444 5555 6666 7777 8888
1111  2222  3333  4444  5555  6666  7777  8888

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.