C Programming Code Examples

C > Sorting Searching Code Examples

C Program to Implement Bitonic sort



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 w;

        printf("\nEnter the data");

        for (w = 0;w < MAX ;w++)

        {

            scanf("%d", &data[w]);

        }

        sort();

        for (w = 0;w < MAX;w++)

        {

            printf("%d ", data[w]);

        }

    }

    /* compare and swap based on dir    */

    void compare(int w, int j, int dir)

    {

        int t;

        if (dir == (data[w] > data[j]))

        {

            SWAP(data[w], 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, w;

        if (c > 1)

        {

             k = c / 2;

            for (w = low;w < low+k ;w++)

                compare(w, w+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);

    }