Bitonic Sort in C - Sanfoundry

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.

```
/*
```

 *  C Program to Implement Bitonic sort

```
 */
```
```
#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);
```
```
}
```

$ 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.

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.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Odd Even Sort

» Next - C Program to Implement CockTail Sort

Related Posts:

Recommended Articles: