C Exercises: Sort numbers using Cocktail Sort method

C Programming Searching and Sorting Algorithm: Exercise-14 with Solution

Write a C program that sorts numbers using the Cocktail Sort method.

Cocktail shaker sort (also known as bidirectional bubble sort, cocktail sort, shaker sort, ripple sort, shuffle sort, or shuttle 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. It provides only marginal performance improvements, and does not improve asymptotic performance; like the bubble sort, it is not of practical interest, though it finds some use in education.

Visualization of shaker sort:

Sample Solution:

Sample C Code:

// CocktailSort Implementation
// Source: https://bit.ly/2rcvXK5
#include <stdio.h>

// Function to swap two elements in an array
// This swap function is optimized for numbers.
void swap(int *x, int *y) {
    if (x == y)
        return;
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
}

// CocktailSort function to sort an array
void cocktailsort(int *a, size_t n) {
    while (1) {
        // Packing two similar loops into one
        char flag;
        int it, i;
        size_t start[2] = {1, n - 1},
               end[2] = {n, 0},
               inc[2] = {1, -1};

        for (it = 0; it < 2; ++it) {
            flag = 1;
            for (i = start[it]; i != end[it]; i += inc[it])
                if (a[i - 1] > a[i]) {
                    swap(a + i - 1, a + i);
                    flag = 0;
                }
            if (flag)
                return;
        }
    }
}

// Main function
int main(void) {
    int a[] = {5, -1, 101, -4, 0, 1, 8, 6, 2, 3};
    int i;
    size_t n = sizeof(a) / sizeof(a[0]);

    // Display original array
    printf("Original Array:\n");
    for (i = 0; i < n; i++)
        printf("%d%s", a[i], i == n - 1 ? "\n" : " ");

    // Sort the array using CocktailSort
    printf("\nSorted Array:\n");
    cocktailsort(a, n);
    for (i = 0; i < n; ++i)
        printf("%d ", a[i]);

    return 0;
}

Sample Output:

Original Array:
5 -1 101 -4 0 1 8 6 2 3

Sorted Array:
-4 -1 0 1 2 3 5 6 8 101 

Flowchart:

C Programming Code Editor:

Previous: Write a C program that sort numbers using Bogo Sort method.
Next: Write a C program that sort numbers using Cycle Sort method.