Cocktail Shaker Sort Algorithm
The Cocktail Shaker Sort Algorithm, also known as bidirectional bubble sort, ripple sort, shaker sort, or comparison-sort, is a variation of the well-known Bubble Sort algorithm. It is an efficient comparison-based sorting algorithm that works by comparing adjacent elements in a list and swapping them if they are in the wrong order. The primary difference between the Cocktail Shaker Sort and the Bubble Sort is that the former sorts the list in both directions - left to right and right to left, in a single pass. This bidirectional approach results in a more efficient sorting process, as it can detect whether the list is already sorted, and can also move multiple misplaced elements in a single pass.
In the Cocktail Shaker Sort Algorithm, the sorting process consists of iterating through the list multiple times until it is completely sorted. During each iteration, the algorithm first sorts the list from left to right, comparing adjacent elements and swapping them if they are not in the correct order. Once the end of the list is reached, the algorithm then reverses direction and sorts the list from right to left, performing the same comparison and swapping process. This bidirectional sorting process continues until no more swaps are required, indicating that the list is sorted. Although the Cocktail Shaker Sort Algorithm is generally considered more efficient than the Bubble Sort, it still has an average-case time complexity of O(n^2), making it less efficient than other sorting algorithms, such as Quick Sort or Merge Sort, for large datasets.
package Sorts;
/**
* @author Mateus Bizzo (https://github.com/MattBizzo)
* @author Podshivalov Nikita (https://github.com/nikitap492)
*/
class CocktailShakerSort implements SortAlgorithm {
/**
* This method implements the Generic Cocktail Shaker Sort
*
* @param array The array to be sorted
* Sorts the array in increasing order
**/
@Override
public <T extends Comparable<T>> T[] sort(T[] array) {
int length = array.length;
int left = 0;
int right = length - 1;
int swappedLeft, swappedRight;
while (left < right) {
// front
swappedRight = 0;
for (int i = left; i < right; i++) {
if (SortUtils.less(array[i + 1], array[i])) {
SortUtils.swap(array, i, i + 1);
swappedRight = i;
}
}
// back
right = swappedRight;
swappedLeft = length - 1;
for (int j = right; j > left; j--) {
if (SortUtils.less(array[j], array[j - 1])) {
SortUtils.swap(array, j - 1, j);
swappedLeft = j;
}
}
left = swappedLeft;
}
return array;
}
// Driver Program
public static void main(String[] args) {
// Integer Input
Integer[] integers = {4, 23, 6, 78, 1, 54, 231, 9, 12};
CocktailShakerSort shakerSort = new CocktailShakerSort();
// Output => 1 4 6 9 12 23 54 78 231
SortUtils.print(shakerSort.sort(integers));
// String Input
String[] strings = {"c", "a", "e", "b", "d"};
SortUtils.print(shakerSort.sort(strings));
}
}
