Code:
#include stdio.h
#include stdlib.h
#define MAX 8
#define SWAP(x,y) t = x; x = y; y = t;
void compare();
void bitonicmerge(int, int, int);
void recbitonic(int, int, int);
void sort();
int data[MAX];
int up = 1;
int down = 0;
int main()
{
int i;
printf("\nEnter the data");
for (i = 0;i < MAX ;i++)
{
scanf("%d", &data[i]);
}
sort();
for (i = 0;i < MAX;i++)
{
printf("%d ", data[i]);
}
}
/*
* compare and swap based on dir
*/
void compare(int i, int j, int dir)
{
int t;
if (dir == (data[i] > data[j]))
{
SWAP(data[i], data[j]);
}
}
/*
* Sorts a bitonic sequence in ascending order if dir=1
* otherwise in descending order
*/
void bitonicmerge(int low, int c, int dir)
{
int k, i;
if (c > 1)
{
k = c / 2;
for (i = low;i < low+k ;i++)
compare(i, i+k, dir);
bitonicmerge(low, k, dir);
bitonicmerge(low+k, k, dir);
}
}
/*
* Generates bitonic sequence by sorting recursively
* two halves of the array in opposite sorting orders
* bitonicmerge will merge the resultant data
*/
void recbitonic(int low, int c, int dir)
{
int k;
if (c > 1)
{
k = c / 2;
recbitonic(low, k, up);
recbitonic(low + k, k, down);
bitonicmerge(low, c, dir);
}
}
/*
* Sorts the entire array
*/
void sort()
{
recbitonic(0, MAX, up);
}
Output:
$ 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
More C Programs:
