Cocktail Selection Sort Algorithm
The Cocktail Selection Sort Algorithm, also known as the bidirectional bubble sort, cocktail shaker sort, ripple sort, or shaker sort, is a variation of the traditional bubble sort algorithm. In this algorithm, the list is sorted by comparing and swapping adjacent elements, similar to bubble sort, but in both directions - from left to right and right to left, during each pass through the list. This bidirectional approach allows the algorithm to sort the list in less number of iterations compared to the traditional bubble sort, as the smaller and larger elements are moved to their correct positions in both directions simultaneously.
In the first pass, the algorithm starts by comparing the first two elements of the list, swapping them if they are in the wrong order, and continues this process until the end of the list, similar to bubble sort. Once the first pass is completed, the largest element is placed at the end of the list. In the second pass, the algorithm reverses direction and starts from the end of the list, comparing and swapping adjacent elements from right to left until it reaches the beginning of the list. After the second pass, the smallest element is placed at the beginning of the list. This process continues, alternating between left-to-right and right-to-left passes, until the entire list is sorted. Due to its bidirectional nature, the cocktail selection sort algorithm is more efficient than the traditional bubble sort, but still has an average and worst-case time complexity of O(n^2), making it inefficient for large datasets.
//Returns Sorted elements after performing Cocktail Selection Sort
//It is a Sorting algorithm which chooses the minimum and maximum element in an array simultaneously,
//and swaps it with the lowest and highest available position iteratively or recursively
#include <iostream>
using namespace std;
//Iterative Version
void CocktailSelectionSort(vector<int> &vec, int low, int high)
{
while (low <= high)
{
int minimum = vec[low];
int minimumindex = low;
int maximum = vec[high];
int maximumindex = high;
for (int i = low; i <= high; i++)
{
if (vec[i] >= maximum)
{
maximum = vec[i];
maximumindex = i;
}
if (vec[i] <= minimum)
{
minimum = vec[i];
minimumindex = i;
}
}
if (low != maximumindex || high != minimumindex)
{
swap(vec[low], vec[minimumindex]);
swap(vec[high], vec[maximumindex]);
}
else
{
swap(vec[low], vec[high]);
}
low++;
high--;
}
}
//Recursive Version
void CocktailSelectionSort(vector<int> &vec, int low, int high)
{
if (low >= high)
return;
int minimum = vec[low];
int minimumindex = low;
int maximum = vec[high];
int maximumindex = high;
for (int i = low; i <= high; i++)
{
if (vec[i] >= maximum)
{
maximum = vec[i];
maximumindex = i;
}
if (vec[i] <= minimum)
{
minimum = vec[i];
minimumindex = i;
}
}
if (low != maximumindex || high != minimumindex)
{
swap(vec[low], vec[minimumindex]);
swap(vec[high], vec[maximumindex]);
}
else
{
swap(vec[low], vec[high]);
}
CocktailSelectionSort(vec, low + 1, high - 1);
}
//main function, select any one of iterative or recursive version
int main()
{
int n;
cout << "Enter number of elements\n";
cin >> n;
std::vector<int> v(n);
cout << "Enter all the elements\n";
for (int i = 0; i < n; ++i)
{
cin >> v[i];
}
CocktailSelectionSort(v, 0, n - 1);
cout << "Sorted elements are\n";
for (int i = 0; i < n; ++i)
{
cout << v[i] << " ";
}
return 0;
}
