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 <stdio.h>
void swap(int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void shakersort(int a[], int n)
{
int p, i;
for (p = 1; p <= n / 2; p++)
{
for (i = p - 1; i < n - p; i++)
if (a[i] > a[i+1]){
swap(&a[i], &a[i + 1]);
}
for (i = n - p - 1; i >= p; i--)
if (a[i] < a[i-1]){
swap(&a[i], &a[i - 1]);
}
}
}
int main()
{
int n;
scanf("%d",&n);
int arr[n] ,i;
for (i = 0 ; i < n; i++)
scanf("%d ", &arr[i]);
shakersort(arr, n);
for (i = 0 ; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
