Shaker sort (cocktail sort, shake sort) is a stable sorting algorithm with quadratic asymptotic complexity . Shakersort is a bidirectional version of bubble sort.
Description
Shaker sort unlike bubble sort orders the array in both directions. Hence every iteration of the algorithm consists of two phases. In the first one the lightest bubble ascends to the end of the array, in the second phase the heaviest bubble descends to the beginning of the array.
This way an imperfection of bubble sort – the problem of rabbits and turtles – is mitigated. The problem of rabbits and turtles is a situation in bubble sort, when a heavy bubble is placed at the end of the array. While the light bubbles (rabbits) are ascending rapidly, the heavy bubble (turtle) descends only one position per each iteration.
Visualization
Code
01.
/**
02.
* Shaker sort (bidirectional bubble sort)
03.
* Orders in descending order
04.
* @param array array to be sorted
05.
*/
06.
public
static
void
shakerSort(
int
[] array) {
07.
for
(
int
i =
0
; i < array.length/
2
; i++) {
08.
boolean
swapped =
false
;
09.
for
(
int
j = i; j < array.length - i -
1
; j++) {
10.
if
(array[j] < array[j+
1
]) {
11.
int
tmp = array[j];
12.
array[j] = array[j+
1
];
13.
array[j+
1
] = tmp;
14.
swapped =
true
;
15.
}
16.
}
17.
for
(
int
j = array.length -
2
- i; j > i; j--) {
18.
if
(array[j] > array[j-
1
]) {
19.
int
tmp = array[j];
20.
array[j] = array[j-
1
];
21.
array[j-
1
] = tmp;
22.
swapped =
true
;
23.
}
24.
}
25.
if
(!swapped)
break
;
26.
}
27.
}
01.
/**
02.
* Shaker sort (bidirectional bubble sort)
03.
* Orders in descending order
04.
* @param array array to be sorted
05.
* @param size length of the array
06.
*/
07.
void
shakerSort(
int
array[],
int
size) {
08.
for
(
int
i = 0; i < size/2; i++) {
09.
bool
swapped =
false
;
10.
for
(
int
j = i; j < size - i - 1; j++) {
//one way
11.
if
(array[j] < array[j+1]) {
12.
int
tmp = array[j];
13.
array[j] = array[j+1];
14.
array[j+1] = tmp;
15.
swapped =
true
;
16.
}
17.
}
18.
for
(
int
j = size - 2 - i; j > i; j--) {
//and back
19.
if
(array[j] > array[j-1]) {
20.
int
tmp = array[j];
21.
array[j] = array[j-1];
22.
array[j-1] = tmp;
23.
swapped =
true
;
24.
}
25.
}
26.
if
(!swapped)
break
;
//block (break if no element was swapped - the array is sorted)
27.
}
28.
}
01.
/**
02.
* Shaker sort (bidirectional bubble sort)
03.
* Orders in descending order
04.
* @param array array to be sorted
05.
*/
06.
public
static
void
ShakerSort(
int
[] array)
07.
{
08.
for
(
int
i = 0; i < array.Length / 2; i++)
09.
{
10.
bool
swapped =
false
;
11.
for
(
int
j = i; j < array.Length - i - 1; j++)
12.
{
13.
if
(array[j] < array[j + 1])
14.
{
15.
int
tmp = array[j];
16.
array[j] = array[j + 1];
17.
array[j + 1] = tmp;
18.
swapped =
true
;
19.
}
20.
}
21.
for
(
int
j = array.Length - 2 - i; j > i; j--)
22.
{
23.
if
(array[j] > array[j - 1])
24.
{
25.
int
tmp = array[j];
26.
array[j] = array[j - 1];
27.
array[j - 1] = tmp;
28.
swapped =
true
;
29.
}
30.
}
31.
if
(!swapped)
break
;
32.
}
33.
}
01.
procedure
ShakeSort(
var
X : ArrayType; N :
integer
);
02.
var
03.
L,
04.
R,
05.
K,
06.
J :
integer
;
07.
begin
08.
L :=
2
;
09.
R := N;
10.
K := N;
11.
repeat
12.
for
J := R
downto
L
do
13.
if
(X[J] < X[J -
1
])
then
14.
begin
15.
Swap(X[J], X[J -
1
]);
16.
K := J
17.
end
;
18.
L := K +
1
;
19.
for
J := L
to
R
do
20.
if
(X[J] < X[J -
1
])
then
21.
begin
22.
Swap(X[J], X[J -
1
]);
23.
K := J
24.
end
;
25.
R := K -
1
;
26.
until
L >= R
27.
end
;
28.
29.
procedure
Swap(
var
X, Y :
integer
);
30.
var
31.
Temp :
integer
;
32.
begin
33.
Temp := X;
34.
X := Y;
35.
Y := Temp
36.
end
;