shaker sort Algorithm
Shaker sort, also known as bidirectional bubble sort, cocktail sort, ripple sort, or shuttle sort, is a variation of the bubble sort algorithm in which the list is sorted by comparing and swapping adjacent elements, first from left to right and then from right to left. This two-pass approach helps to minimize the number of iterations needed to sort the list and improves the performance of the algorithm. Shaker sort is a comparison-based, unstable, and in-place sorting algorithm that has an average and worst-case time complexity of O(n^2), making it inefficient for large datasets.
In the first pass (left to right), the algorithm starts by comparing the first two elements of the list. If the first element is greater than the second one, they are swapped. This process continues with the next pair of elements until the end of the list is reached. During this pass, the largest unsorted element "bubbles up" to its correct position at the end of the list. In the second pass (right to left), the algorithm repeats the same process but in reverse order, starting from the last unsorted element and moving towards the beginning of the list. This time, the smallest unsorted element "bubbles down" to its correct position at the beginning of the list. These two passes are alternated until no more swaps are needed, indicating that the list is sorted.
#include<iostream>
using namespace std;
// A function to swap values using call by reference.
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// A function implementing shaker sort.
void ShakerSort(int a[], int n)
{
int i, j, k;
for(i = 0; i < n;)
{
// First phase for ascending highest value to the highest unsorted index.
for(j = i+1; j < n; j++)
{
if(a[j] < a[j-1])
swap(&a[j], &a[j-1]);
}
// Decrementing highest index.
n--;
// Second phase for descending lowest value to the lowest unsorted index.
for(k = n-1; k > i; k--)
{
if(a[k] < a[k-1])
swap(&a[k], &a[k-1]);
}
// Incrementing lowest index.
i++;
}
}
int main()
{
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}
ShakerSort(arr, n);
// Printing the sorted data.
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}
