Cocktail sort
Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort, ripple sort, or shuttle sort, is a stable sorting algorithm that varies from bubble sort in that instead of repeatedly passing through the list from top to bottom, it passes alternately from top to bottom and then from bottom to top. It can achieve slightly better performance than a standard bubble sort.
Complexity in Big O notation is O(n²) for a worst case, but becomes closer to O(n) if the list is mostly ordered at the beginning.
| Contents |
Implementation
Python
def cocktail_sort (aList, n):
aList = aList[:]
left = 0
right = n
while True:
if finished:
break
finished = True
right -= 1
for index in range(left, right):
if aList[index] > aList[index+1]:
aList[index], aList[index+1] = aList[index+1], aList[index]
finished = False
if finished:
return aList
finished = True
for index in range(right, left, -1)
if aList[index] < aList[index-1]:
aList[index], aList[index-1] = aList[index-1], aList[index]
finished = False
left+= 1
C++
void cocktail_sort (int A[], int n)
{
int left = 0, right = n;
bool finished;
do
{
finished = true;
--right;
for (int i = left; i < right; i++)
if (A[i] > A[i+1]) {
std::swap(A[i], A[i+1]);
finished = false;
}
if (finished) return; finished = true;
for (int i = right; i > left; i--)
if (A[i] < A[i-1]) {
std::swap(A[i], A[i-1]);
finished = false;
}
++left;
} while (!finished);
}
Perl
sub cocktail_sort(@)
{
my @a = @_;
my ($left,$right) = (0,$#_);
while ($left < $right) {
foreach $i ($left..$right-1) {
($a[$i],$a[$i+1]) = ($a[$i+1],$a[$i]) if ($a[$i] > $a[$i+1]);
}
$right--;
foreach $i (reverse $left+1..$right) {
($a[$i],$a[$i-1]) = ($a[$i-1],$a[$i]) if ($a[$i] < $a[$i-1]);
}
$left++;
}
return @a;
}
FORTRAN 77
SUBROUTINE cocktail_sort (A,LEN)
INTEGER A, LEN, COUNTR, TEMP
LOGICAL FLIP
DIMENSION A(LEN)
FLIP = .TRUE.
WHILE (FLIP) DO
COUNTR = 1
FLIP = .FALSE.
DO 16 COUNTR = 1, LEN - 1, 1
IF (A(COUNTR) .GT. A(COUNTR+1)) THEN
TEMP = A(COUNTR)
A(COUNTR) = A(COUNTR+1)
A(COUNTR+1) = TEMP
FLIP = .TRUE.
END IF
16 CONTINUE
COUNTR = LEN
DO 25 COUNTR = LEN, 2, -1
IF(A(COUNTR) .LT. A(COUNTR-1)) THEN
TEMP = A(COUNTR)
A(COUNTR) = A(COUNTR-1)
A(COUNTR-1) = TEMP
FLIP = .TRUE.
END IF
25 CONTINUE
END WHILE
END