Data Structures, Algorithms, & Applications in Java
Shaker Sort
Copyright 1999 Sartaj Sahni

In Chapter 2 we have considered most of the simple sorting methods. Shaker sort is a variant of the bubble sort method. In shaker sort, n elements are sorted in n/2 phases. Each phase of shaker sort consists of a left to right bubbling pass followed by a right to left bubbling pass. In a bubbling pass pairs of adjacent elements are compared and swapped if they are out of order.

Suppose we are to sort the elements [6,5,2,8,3,1]. The number of phases is 3. In the left to right pass of the first phase, the pair (6,5) is compared and swapped to get the array [5,6,2,8,3,1]. Next the pair (6,2) is compared and swapped to get [5,2,6,8,3,1]. The next compare (6,8) causes no swap. When 8 and 3 are compared, a swap is done to get [5,2,6,3,8,1]. The final compare of this pass is (8,1). Following the swap we get [5,2,6,3,1,8]. Now the right to left pass begins. The pair (3,1) is compared first, a swap is done, and we get the array [5,2,6,1,3,8]. Next the pair (6,1) is compared and we get [5,2,1,6,3,8]. At the end of the right to left pass we have [1,5,2,6,3,8]. Phase 2 works on the segment [5,2,6,3]. After the left to right pass, we have [2,5,3,6]; and after the right to left pass, we have [2,3,5,6]. The third phase works on the segment [3,5].

Suppose we start with an array a[0:n-1] of elements to be sorted. After the left to right bubbling pass of phase 1, the largest element is in the rightmost position. So the right to left pass needs to be concerned only with elements in positions 0 through n-2 of the array. Following the right to left pass, the smallest element is in position 0 of the array. Consequently, the next phase need be concerned only with the elements in positions 1 through n-2.

In general, the left to right pass of phase p of shaker sort needs to be concerned only with elements in positions p-1 through n-p, and the right to left pass of this phase needs to be concerned only with elements in positions n-p-1 through p.

The code given below implements the shaker sort method. Note that when n is odd, the right to left pass of the last phase accomplishes nothing. 
public class ShakerSort
{
   /** sort the elements a[0 : a.length - 1] using
     * the shaker sort method */
   public static void shakerSort(Comparable [] a)
   {
      for (int p = 1; p <= a.length / 2; p++)
      {// phase p of shaker sort
         // first do left to right bubbling pass
         for (int i = p - 1; i < a.length - p; i++)
            if (a[i].compareTo(a[i+1]) > 0)
               MyMath.swap(a, i, i + 1);
        
         // now do right to left bubbling pass
         for (int i = a.length - p - 1; i >= p; i--)
            if (a[i].compareTo(a[i-1]) < 0)
               MyMath.swap(a, i, i - 1);
      }
   }
}


To analyze the complexity of ShakerSort, we can count the number of comparisons between pairs of elements, do a step-count analaysis, or proceed directly to do an asymptotic analysis. The number of element compares in the first phase is (n-1) + (n-2), in the second phase it is (n-3) + (n-4), and so on. Summing over all phases, we obtain (sum from i=1 to n-1)i = n(n-1)/2 as the number of comparisons.

To do a direct asymptotic analysis, we observe that phase p takes Theta(n-p) time. So the time for all phases is (sum from p=1 to n/2)(n-p) = (sum from q=n/2 to n-1)q = Theta(n2). The complexity of shaker sort is Theta(n2). See the solution to Exercise 19.46 to understand why sort methods such as bubble, insert, selction, and shaker must take O(n2) time.