Cocktail Shaker Sort would like a drink.  A strong one, if you please.

The father of four rambunctious children and husband to the always-working Heap Sort, "Shaky" (a loving nickname for him which is never said to his face) is a stay-at-home dad who absolutely adores his children but just wants some alone time, is that so much to ask?

Photo by Helena Yankovska / Unsplash

The problem is that, when he gets his alone time (rare as it is), he would greatly prefer to curl up with his beloved Heapy, but failing that, he'll make a stiff drink that the rest of the family can't be in the same room as.

Not that he minds. Heapy is his best friend, his companion, his true love, but the rest of her family he could take or leave. Nevertheless, his kids love him, and the family has accepted him, even if he hasn't quite gotten around to feeling the same way.

The Rundown

  • Created By: Donald Knuth (1973)
  • AKA: Bidirectional Bubble Sort
  • Type: Exchange
  • Stable? Yes
  • Best-Case:  O(n)
  • Average-Case:  O(n2)
  • Worst-Case:  O(n2)
  • Space Complexity: O(1)
  • Sample Project: Over on GitHub
exceptionnotfound/SortExtravaganzaCSharp
Lots of example sorting algorithms, from a family reunion. - exceptionnotfound/SortExtravaganzaCSharp
GitHubexceptionnotfound
Project for this post: CocktailShakerSort

Algorithm

  1. PASS THROUGH the collection from left-to-right.
  2. DURING that pass, SELECT the highest encountered value.
  3. DEPOSIT that value at the end of the considered range.
  4. DECREASE the end of the considered range by 1.
  5. PASS THROUGH the collection from right-to-left.
  6. DURING that pass, SELECT the lowest encountered value.
  7. DEPOSIT that value at the beginning of the considered range.
  8. INCREASE the start of the considered range by 1.
  9. GO TO 1, CONTINUE until the range is 0.

Visualization

Lucky for us, Cocktail Shaker sort is an easy sort to understand.  On each pass through the collection, it either finds the highest or lowest encountered value (depending on pass direction) and deposits that value at the beginning or end of the considered range. In fact, Cocktail Shaker sort is really just Bubble Sort but in both directions.

The "audibilization" of this sort is particularly interesting, because it's simple to understand without knowing the underlying math and logic:

C# Implementation

class CocktailShakerSort
{

    static void Sort(int[] array)
    {
        bool isSwapped = true;
        int start = 0;
        int end = array.Length;

        while (isSwapped == true)
        {

            //Reset this flag.  
            //It is possible for this to be true from a prior iteration.
            isSwapped = false;

            //Do a bubble sort on this array, from low to high. 
            //If something changed, make isSwapped true.
            for (int i = start; i < end - 1; ++i)
            {
                if (array[i] > array[i + 1])
                {
                    int temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    isSwapped = true;
                }
            }

            //If no swaps are made, the array is sorted.
            if (isSwapped == false)
                break;

            //We need to reset the isSwapped flag for the high-to-low pass
            isSwapped = false;

            //The item we just moved is in its rightful place, 
            //so we no longer need to consider it unsorted.
            end = end - 1;

            //Now we bubble sort from high to low
            for (int i = end - 1; i >= start; i--)
            {
                if (array[i] > array[i + 1])
                {
                    int temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    isSwapped = true;
                }
            }

            //Finally, we need to increase the starting point 
            //for the next low-to-high pass.
            start = start + 1;
        }
    }

    public static void Main()
    {
        int[] array = { 15, 10, 83, 5, 7, 42, 65, 50, 58, 71, 61 };

        CommonFunctions.PrintInitial(array);

        Sort(array);

        CommonFunctions.PrintFinal(array);

        Console.ReadKey();
    }
}

Time and Space Complexity

You may have heard before that Bubble Sort's complexities for all cases are O(n2). Cocktail Shaker Sort, being a direct derivative of Bubble Sort, is not much better; the average and worst-case complexities do not improve, and only the best case scenario (where the list is already sorted) becomes O(n).

About the only good thing Cocktail Shaker Sort has going for it is a space complexity of constant value, O(1). But that's not very useful in the real world. In short, Cocktail Shaker Sort is not a valuable implementation of sorting for anything other than educational or theoretical problems. Sorry, bro.

Summary

Cocktail Shaker Sort is an easy-to-understand, simple-to-implement derivative of Bubble Sort. However, it's not a terribly useful sort in the real world, as it takes too long to do much of anything. Plus, he makes a drink that'll burn your eyeballs out. Don't say I didn't warn you.

Watch out for the little legs you hear pattering down the hall; they belong to Bogosort, and they're coming to steal your stuff.

Bogosort in C#
Bogosort is adorable, when he isn’t running away. The two-year-old son of Heap Sort and Cocktail Shaker Sort, he is possibly themost mischievous scamp this side of the Mississippi, or at least that’s what hisgrandfather would say. “Who, me?” Photo by Luke Brugger[https://unsplash.com/@lukebrugger?utm_source=ghost&utm_medium=referral&utm_campaign=api-credit…
Exception Not FoundMatthew Jones

Don't forget to check out the sample project over on GitHub!

Happy Coding!