V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Cocktail Shaker Sort

Alternate forward and backward Bubble Sort passes so both large and small misplaced values move quickly.

Core idea

Alternate a left-to-right bubble pass with a right-to-left pass. The forward scan fixes a large value at the right boundary, while the backward scan fixes a small value at the left boundary.

Read the visualization

The active direction changes at each boundary. Adjacent pointers mark each comparison, swaps move stable bars, and the completed prefix and suffix close around the unsorted center.

4
2
6
3
8
5
7
1

Start a forward pass that moves the largest remaining value to the right.

1function cocktailSort(a: number[]): number[] {
2 let left = 0, right = a.length - 1;
3 while (left < right) {
4 let swapped = false;
5 for (let j = left; j < right; j++) {
6 if (a[j] > a[j + 1]) {
7 [a[j], a[j + 1]] = [a[j + 1], a[j]];
8 swapped = true;
9 }
10 }
11 right--;
12 if (!swapped) break;
13 swapped = false;
14 for (let j = right; j > left; j--) {
15 if (a[j - 1] > a[j]) {
16 [a[j - 1], a[j]] = [a[j], a[j - 1]];
17 swapped = true;
18 }
19 }
20 left++;
21 if (!swapped) break;
22 }
23 return a;
24}
n8
left0
right7
direction→
j0
left / right value4 / 2
swappedInPassfalse
swapCount0
1 / 49

Complexity and tradeoffs

Time: O(n^2). Space: O(1). Stable and in-place; bidirectional passes help some inputs but do not change the quadratic bound.

Invariant: After every forward pass the right boundary is final, and after every backward pass the left boundary is final.

Where it fits

Cocktail Shaker Sort is mainly educational. It can improve over one-way Bubble Sort when small values begin near the right edge, but efficient general sorting still favors n log n methods.