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.