The C programs in this section demonstrates other special sorting algorithms. qSort is a function which performs quick sort. Pigeonhole Sort is a sorting technique that is used when the given range of keys is relatively small. An array of pigeonholes (buckets, chunks of memory) is reserved for each key value. The records from the unsorted list are scanned and copied into their respective pigeonholes based on their key values. Then, the contents of the pigeonholes are copied in sequence to the final destination. Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is optimal in view of the total number of writes to the original array. Odd-even sort is used for sorting on two-dimensional processor arrays. In Cocktail Sort, values “bubble” both directions through the array, because on each iteration the cocktail sort bubble sorts once forwards and once backwards. Bitonic sort is a comparison-based sorting algorithm that focuses on converting a random sequence of numbers into a bitonic sequence, one that monotonically increases, then decreases. Comb Sort is an in-place sort algorithm that repeatedly reorders different pairs of items. On each pass swaps pairs of items separated by the increment or gap, if needed, and reduce the gap. Stooge Sort is a recursive sorting algorithm.

This C Program implements qsort using function pointers.

Here is source code of the C Program implements qsort using function pointers. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/* 
```

 * C Program to Implement qsort using function pointers

```
 */
```
```
#include <stdio.h>
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
#include <string.h>
```
```
 
```
```
struct s
```
```
{
```
```
    char empname[5];
```
```
    int empid;
```
```
};
```
```
 
```
```
/* To sort array elemets */
```

int int_call(const void *a1,const void *b1)

```
{
```
```
    const int *a = (const int *)a1;
```
```
    const int *b = (const int *)b1;
```
```
 
```
```
    if (*a > *b)
```
```
        return 1;
```
```
    else
```
```
    {
```
```
        if (*a == *b) 
```
```
            return 0;
```
```
        else
```
```
            return -1;
```
```
    }
```
```
}
```
```
 
```
```
/* To sort structure elemets */
```

int string_call(const void *a1, const void *b1)

```
{
```
```
    const char *a = (const char *)a1;
```
```
    const char *b = (const char *)b1;
```
```
    return(strcmp(a, b));
```
```
}
```
```
 
```
```
void main()
```
```
{
```
```
    int array1[5]={20, 30, 50, 60, 10};
```
```
    struct s emprec[5];
```
```
    int i, j;
```
```
 
```
```
    strcpy(emprec[0].empname, "bbb");
```
```
    emprec[0].empid = 100;
```
```
    strcpy(emprec[1].empname, "ccc");
```
```
    emprec[1].empid = 200;
```
```
    strcpy(emprec[2].empname, "eee");
```
```
    emprec[2].empid = 300;
```
```
    strcpy(emprec[3].empname, "aaa");
```
```
    emprec[3].empid = 400;
```
```
    strcpy(emprec[4].empname,"ddd");
```
```
    emprec[4].empid = 500;
```

    qsort(array1, 5, sizeof(int), int_call);

    qsort(emprec, 5, sizeof(struct s), string_call);

```
    for (i = 0; i < 5; i++)
```
```
        printf("%d\t", array1[i]);
```

    printf("\nSorting of Structure elements ");

```
    for (i = 0; i < 5; i++)
```

        printf("\n%s\t%d", emprec[i].empname, emprec[i].empid);

```
    printf("\n");
```
```
}
```

$ cc qsort_fp.c
$ a.out
10    20    30    50    60    
Sorting of Structure elements 
aaa    400
bbb    100
ccc    200
ddd    500
eee    300

C Program to Implement Pigeonhole Sort

This C Program implement pigeonhole sort. Pigeonhole sorting, also known as count sort, is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the number of possible key values (N) are approximately the same.[1] It requires O(n + N) time

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

```
/*
```

 *  C Program to Implement Pigeonhole Sort

```
 */
```
```
#include <stdio.h>
```
```
 
```
```
#define MAX 7
```
```
 
```
```
void pigeonhole_sort(int, int, int *);
```
```
void main()
```
```
{
```
```
    int a[MAX], i, min, max;
```

    printf("enter the values into the matrix :");

```
    for (i = 0; i < MAX; i++)
```
```
    {
```
```
        scanf("%d", &a[i]);
```
```
    }
```
```
    min = a[0];
```
```
    max = a[0];
```
```
    for (i = 1; i < MAX; i++)
```
```
    {
```
```
        if (a[i] < min)
```
```
        {
```
```
            min = a[i];
```
```
        }
```
```
        if (a[i] > max)
```
```
        {
```
```
            max = a[i];
```
```
        }
```
```
    }
```
```
    pigeonhole_sort(min, max, a);
```
```
    printf("Sorted order is :\n");
```
```
    for (i = 0; i < MAX; i++)
```
```
    {
```
```
        printf("%d", a[i]);
```
```
    }
```
```
}
```
```
 
```

/* sorts the array using pigeonhole algorithm */

void pigeonhole_sort(int mi, int ma, int * a)

```
{
```
```
 
```
```
    int size, count = 0, i;
```
```
    int *current;
```
```
    current = a;
```
```
    size = ma - mi + 1;
```
```
    int holes[size];
```
```
    for (i = 0; i < size; i++)
```
```
    {
```
```
        holes[i] = 0;
```
```
    }
```

    for (i = 0; i < size; i++, current++)

```
    {
```
```
        holes[*current-mi] += 1;
```
```
    }
```

    for (count = 0, current = &a[0]; count < size; count++)

```
    {
```
```
        while (holes[count]--> 0)
```
```
        {
```
```
            *current++ = count + mi;
```
```
        }
```
```
    }
```
```
}
```

 
$cc pigeonholesort.c
 
/* average case */
$ a.out
enter the values into the matrix :7 3 8 2 5 4 9
Sorted order is :
2345789
 
/* best case */
$ a.out
enter the values into the matrix :1 2 3 4 5 6 7
Sorted order is :
1234567
 
/* worst case */
$ a.out
enter the values into the matrix :7 6 5 4 3 2 1
Sorted order is :
1234567

C Program to Implement Cyclesort
This C Program implements cyclesort. Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm.
It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.
 
Here is source code of the C Program to implement cyclesort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C Program to Implement Cyclesort
 */
#include <stdio.h>
 
#define MAX 8
 
void cycle_sort(int *);
 
void main()
{
    int a[MAX],i;
 
    printf("enter the elements into array :");
    for (i = 0;i < MAX; i++)
    {
        scanf("%d", &a[i]);
    }
    cycle_sort(a);
    printf("sorted elements are :\n");
    for (i = 0;i < MAX; i++)
    {
        printf("%d", a[i]);
    }
}
 
/* sorts elements using cycle sort algorithm */
void cycle_sort(int * a)
{
    int temp, item, pos, i, j, k;
 
    for (i = 0;i < MAX; i++)
    {
        item = a[i];
        pos = i;
        do
        {
            k = 0;
            for (j = 0;j < MAX;j++)
            {
                if (pos != j && a[j] < item)
                {
                    k++;
                }
            }
            if (pos != k)
            {
                while (pos != k && item == a[k])
                {
                    k++;
                }
                temp = a[k];
                a[k] = item;
                item = temp;
                pos = k;
            }
        }while (pos != i);
    }
}
 
 
 
$ cc cyclesort.c
$ a.out
enter the elements into array :7 3 2 5 4 8 9 6
sorted elements are :
23456789
$ a.out
enter the elements into array :7 3 2 4 5 4 6 3
sorted elements are :
23344567




C Program to Implement Oddeven Sort
This C Program implement oddeven sort.
Here is source code of the C Program to implement oddeven sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
 
/*
 * C Program to Implement Oddeven Sort
 */
#include <stdio.h>
#define MAX 7
 
void swap(int *,int *);
void oddeven_sort(int *);
 
void main()
{
    int a[MAX], i;
 
    printf("enter the elements in to the matrix :");
    for (i = 0;i < MAX;i++)
    {
        scanf("%d", &a[i]);
    }
    printf("sorted elements are :\n");
    oddeven_sort(a);
    for (i = 0;i < MAX;i++)
    {
        printf(" %d", a[i]);
    }
}
 
/* swaps the elements */
void swap(int * x, int * y)
{
    int temp;
 
    temp = *x;
    *x = *y;
    *y = temp;
}
 
/* sorts the array using oddeven algorithm */
void oddeven_sort(int * x)
{
    int sort = 0, i;
 
    while (!sort)
    {
        sort = 1;
        for (i = 1;i < MAX;i += 2)
        {
            if (x[i] > x[i+1])
            {
                swap(&x[i], &x[i+1]);
                sort = 0;
            }
        }
        for (i = 0;i < MAX - 1;i += 2)
        {
            if (x[i] > x[i + 1])
            {
                swap(&x[i], &x[i + 1]);
                sort = 0;
            }
        }
    }
}
$ cc oddevensort.c
/* average case */
$ a.out
enter the elements in to the matrix :7 8 3 2 5 4 9
sorted elements are :
 2 3 4 5 7 8 9
 
/* best case */
$ a.out
enter the elements in to the matrix :1 2 3 4 5 6 7
sorted elements are :
 1 2 3 4 5 6 7
 
/* worst case */
$ a.out
enter the elements in to the matrix :7 6 5 4 3 2 1
sorted elements are :
 1 2 3 4 5 6 7





C Program to Implement CockTail Sort
This C Program implements cocktail sort. Cocktail sort is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort. The algorithm differs from a bubble sort in that it sorts in both directions on each pass through the list. This sorting algorithm is only marginally more difficult to implement than a bubble sort, and solves the problem of turtles in bubble sorts.
The various names of cocktail sort are bidirectional bubble sort, cocktail shaker sort, shaker sort , ripple sort, shuffle sort, shuttle sort or happy hour sort
Here is source code of the C Program to implement cocktail sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
 
/*
 * C Program to Implement CockTail Sort
 */
#include <stdio.h>
#define MAX 8
 
int main()
{
    int data[MAX];
    int i, j, n, c;
 
    printf("\nEnter the data");
    for (i = 0; i < MAX; i++)
    {
        scanf("%d", &data[i]);
    }
    n = MAX;   
    do
    {
        /*
          * Rightward pass will shift the largest element to its correct place at the end
         */
        for (i = 0;  i < n - 1; i++)
        {
            if (data[i] > data[i + 1])
            {
                data[i] = data[i] + data[i + 1];
                data[i + 1] = data[i] - data[i + 1];
                data[i] = data[i] - data[i + 1];
 
            }
 
        }
        n = n - 1;
        /*
          * Leftward pass will shift the smallest element to its correct place at the beginning
          */
        for (i= MAX - 1, c = 0; i >= c; i--)
        {
            if(data[i] < data[i - 1])
            {
                data[i] = data[i] + data[i - 1];
                data[i - 1] = data[i] - data[i - 1];
                data[i] = data[i] - data[i - 1];
            }
        }
        c = c + 1;
 
    } while (n != 0 && c != 0);
    printf("The sorted elements are:");
    for (i = 0; i < MAX; i++)
    {
        printf("%d\t", data[i]);
    }
}
$ gcc cocktailsort.c
$ a.out
/*
 * Average case
 */
Enter the data
9 6 2 12 11 9 3 7
The sorted elements are:2       3       6       7       9       9       11      12 
/*
 * Worst case
 */
 Enter the data
 8 7 6 5 4 3 2 1
 The sorted elements are:1         2        3        4        5        6        7        8
 /*
  *Best case
  */
  Enter the data
  1 2 3 4 5 6 7 8
  The sorted elements are:1     2        3        4        5        6        7        8




 


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.
 
/*
 *  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

C Program to Perform Comb Sort on Array of Integers
This C Program performs Comb sort on array of integers. Comb sort is a comparison sorting algorithm. It is an exchange sort, similar to bubble sort.
Here is source code of the C Program to perform Comb sort on array of integers. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
 
/*
 * C Program to Perform Comb Sort on Array of Integers
 */
#include <stdio.h>
#include <stdlib.h>
 
/*Function to find the new gap between the elements*/
int newgap(int gap)
{
    gap = (gap * 10) / 13;
    if (gap == 9 || gap == 10)
        gap = 11;
    if (gap < 1)
        gap = 1;
    return gap;
}
 
/*Function to implement the combsort*/
void combsort(int a[], int aSize)
{
    int gap = aSize;
    int temp, i;
    for (;;)
    {
        gap = newgap(gap);
        int swapped = 0;
        for (i = 0; i < aSize - gap; i++)
        {
            int j = i + gap;
            if (a[i] > a[j])
            {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                swapped  =  1;
            }
        }
        if (gap  ==  1 && !swapped)
            break;
    }
}
int main ()
{
    int n, i;
    int *a;
    printf("Please insert the number of elements to be sorted: ");
    scanf("%d", &n);       // The total number of elements
    a  =  (int *)calloc(n, sizeof(int));
    for (i = 0;i< n;i++)
    {
        printf("Input element %d :", i);
        scanf("%d", &a[i]); // Adding the elements to the array
    }
    printf("unsorted list");       // Displaying the unsorted array
    for(i = 0;i < n;i++)
    {
         printf("%d", a[i]);
    }
    combsort(a, n);
    printf("Sorted list:\n");        // Display the sorted array
    for(i = 0;i < n;i++)
    {
        printf("%d ", (a[i]));
    }
    return 0;
}
$ cc combsort.c
$ a.out
Please insert the number of elements to be sorted: 10
Input element 0 :5
Input element 1 :6
Input element 2 :1
Input element 3 :3
Input element 4 :4
Input element 5 :7
Input element 6 :8
Input element 7 :9
Input element 8 :0
Input element 9 :6
unsorted list5613478906Sorted list:
0 1 3 4 5 6 6 7 8 9
$ ./a.out
Please insert the number of elements to be sorted: 10
Input element 0 :1
Input element 1 :2
Input element 2 :3
Input element 3 :4
Input element 4 :5
Input element 5 :6
Input element 6 :7
Input element 7 :8
Input element 8 :9
Input element 9 :10
unsorted list12345678910Sorted list:
1 2 3 4 5 6 7 8 9 10
$ ./a.out
Please insert the number of elements to be sorted: 10
Input element 0 :10
Input element 1 :9
Input element 2 :8
Input element 3 :7
Input element 4 :6
Input element 5 :5
Input element 6 :4
Input element 7 :3
Input element 8 :2
Input element 9 :1
unsorted list10987654321Sorted list:
1 2 3 4 5 6 7 8 9 10
 
 



 
 
C Program to Implement Stooge Sort
This C Program Implements Stooge Sort.
Here is source code of the C Program to Implement Stooge Sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
 
/*
 * C Program to Implement Stooge Sort
 */
#include <stdio.h>
 
// Function Prototype
void stoogesort(int [], int, int);
 
void main()
{
    int b[7], i;
 
    printf("Enter the values you want to sort using STOOGE SORT!!!:\n");
    for (i = 0;i < 7;i++)
        scanf(" %d", &b[i]);
    stoogesort(b, 0, 6);
    printf("sorted by stooge sort \n");
    for (i = 0;i < 7;i++)
    {
        printf("%d ", b[i]);
    }
    printf("\n");
}
 
// Function to implement STOOGE SORT
void stoogesort(int a[], int i, int j)
{
    int temp, k;
 
    if (a[i] > a[j])
    {
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;       
    }
    if ((i + 1) >= j)
        return;
    k = (int)((j - i + 1) / 3);
    stoogesort(a, i, j - k);
    stoogesort(a, i + k, j);
    stoogesort(a, i, j - k);
}
$ gcc stoogesort.c
$ a.out
Enter the values you want to sort using STOOGE SORT!!!:
6
1
5
3
8
7
2
sorted by stooge sort
1 2 3 5 6 7 8
$ a.out
Enter the values you want to sort using STOOGE SORT!!!:
7
6
5
4
3
2
1
sorted by stooge sort
1 2 3 4 5 6 7
$ a.out
Enter the values you want to sort using STOOGE SORT!!!:
1
2
3
4
5
6
7
sorted by stooge sort
1 2 3 4 5 6 7