COCKTAIL SORT
What are sorting algorithms?
An algorithm is a sequence of steps to solve a problem efficiently. It is a structured method that can be expressed within finite amount of time and space.
The sorting algorithms problem is perhaps one in every of the foremost famous problems that employed in abroad variety of application. There are several techniques to resolve the sorting problems. For example: Merge sort, heap sort, insertion sort, radix sort, selection sort, cocktail sort etc.
This blog focuses on the cocktail sort and its algorithm.
Cocktail Sorting algorithm
Cocktail sort is a modification of bubble sort and hence is a sorting algorithm. It is also known as ripple sort, shuffle sort, or shuttle sort. However both are comparison-based sorting algorithms but cocktail sorting algorithm sorts in both directions alternatively while bubble sort algorithm always traverses elements in unidirectional i.e. from left to right. Both the sorts compare the two adjacent elements.
· Pseudo code
A: array of sortable items
do
swapped ← false
if A[i]> A[i+1] then
swap (A[ i], A[i+1])
swapped ← true
end if
end for
if swapped=false then
break do-while loop
end if
swapped ← false
for each i = length(A)- 1 to 0 do:
if A[i] > A[i+1] then
swap (A[i] , A[i+1])
swapped : = true
end if
end for
while swapped // if no elements have been swapped, then the list is sorted
end procedure
· Algorithm:
The first rightward pass shifts the greatest number to its correct place at the end, and therefore the following leftward pass shifts the smallest number to its correct place at the starting. The second complete pass shifts the second greatest and second smallest elements to their correct places, and so on.
To elaborate,
Break each iteration of the algorithm into 2 stages:
1) Just like the bubble sort, the first stage iterates through the array from left to right. During this iteration, a comparison takes place between the adjacent elements. If the element on the left is greater than the element on the right, then the elements are swapped. Therefore, at the end of the first iteration, largest element resides at the end of the array.
2) In the second stage also bubble sort takes place but from right to left i.e. second stage iterates through the array in opposite direction starting from the element just before the most recently sorted element and moves straight back to the starting of the array. Here also while iteration goes on, comparison takes place between adjacent elements and if required, they are swapped.
This is how the cocktail sorting algorithm sorts the array in bidirectional way.
Let us illustrate cocktail sort using an example of unsorted array.
Consider array A=[7,1,2,0,8]
1)First Forward pass
[7,1,2,0,8] → [1,7,2,0,8] (swap, since 7>1)
[1,7,2,0,8] → [1,2,7,0,8] (swap, since 7>2)
[1,2,7,0,8] → [1,2,0,7,8] (swap, since 7>0)
At the end of the first forward pass, we can see that the largest element is placed at the end of the array.
2)First Backward pass
[1,2,0,7,8] → [1,2,0,7,8] (no swap, since 0<7)
[1,2,0,7,8] → [1,0,2,7,8] (swap, since 2>0)
[1,0,2,7,8] → [0,1,2,7,8] (swap, since 1>0)
At the end of the first backward pass, we can see that the smallest element is placed t the beginning of the array.
Here, In this case we can also see that the array is now sorted.
Therefore, the array A:[7,1,2,0,8] was sorted in 1 iteration using the cocktail sort.
https://upload.wikimedia.org/wikipedia/commons/e/ef/Sorting_shaker_sort_anim.gif [visual representation (in form of gif) of how cocktail sort works]
· Time and space complexity
Worst case time complexity: O(n*n)
Average case time complexity: O(n*n)
Best case time complexity: O(n) [It occurs only when the array is sorted]
Space Complexity: O(1)
· Comparison from bubble sort
Bubble sort sorts the array in one direction only i.e. from left to right. It compares the two adjacent elements , if the left element is greater then the right element it swaps the elements.
Though time complexities for both the algorithms are same, but cocktail sort performs better than bubble sort. However one cocktail sort pass should be counted as two bubble sort passes. Cocktail sort is less than two times faster than bubble sort. [source: https://en.wikipedia.org/wiki/Cocktail_shaker_sort ]
To prove the above statement , lets take an example of sorting the same array A:[ 7,1,2,0,8] using the bubble sort.
1)First Iteration
[7,1,2,0,8] → [1,7,2,0,8] → [1,2,7,0,8] → [1,2,0,7,8] (final array after first iteration)
2)Second Iteration
[1,2,0,7,8] → [1,2,0,7,8] → [1,0,2,7,8] → [1,0,2,7,8] (final array after second iteration)
3)Third Iteration
[1,0,2,7,8] → [0,1,2,7,8](final array after the third iteration)
We can see that using bubble sort the array was sorted in three iterations.
Conclusion: bubble sort took 3 iterations to sort the array while cocktail sort took 1 iteration only. Hence, we can say cocktail sort is less than two times faster than the bubble sort.This is as a result of it’s an analogous comparison-count. It compares more elements per iteration than regular Bubble sort does and hence double the swaps per iteration. One more reason why cocktail sort is quicker than bubble sort is because the number of possible swaps per iteration gets smaller and smaller, giving it a rather higher performance.
One of the major use of cocktail sort is in the computer science classroom to help students think algorithmically.