Shaker Sort, also called Cocktail Shaker Sort, is an extension of the Bubble Sort. Unlike the Bubble Sort, which puts the bigger element to the end of the non-ordered sublist at each cycle, the Shaker Sort alternates between bringing the bigger element of the unsorted sublist to the end of the ordered part and leading the smaller elements of the unsorted sublist at the beginning of the sorted sublist.
Shaker Sort alternates two Bubble Sorts, the first one that sorts the structure starting from the largest element ordering the elements down to the smallest, and the second one, that starts from the smallest element and sorts the elements up to the largest.
Although this algorithm is an extension of the Bubble Sort and at first glance it might seem much more efficient, the performance increase is minimal and the complexity is the same.
Average Complexity | O(n^{2}) |
---|---|
Best Case | O(n) |
Worst Case | O(n^{2}) |
Space Complexity | O(1) |