Cocktail Sort Algorithm
The Cocktail Sort Algorithm, also known as the Shaker Sort or the Bidirectional Bubble Sort, is a variation of the Bubble Sort Algorithm. Just like the Bubble Sort, it is a simple comparison-based sorting algorithm, best suited for small datasets or lists that are already partially sorted. The main idea behind Cocktail Sort is to improve the efficiency of the Bubble Sort by sorting the list in both directions - left to right and right to left, during each pass through the list. This bidirectional approach allows the algorithm to move smaller values to the beginning of the list and larger values to the end of the list more quickly and in fewer iterations.
The algorithm starts by comparing adjacent elements of the list, swapping them if they are in the incorrect order, and continues in this manner from the beginning to the end of the list. Once the first pass from left to right is completed, the algorithm then starts from the end of the list, comparing and swapping adjacent elements as it moves from right to left. This two-pass approach constitutes a single iteration of the Cocktail Sort. The algorithm repeats these iterations until no swaps are made during an entire iteration, indicating that the list is now sorted. Although the Cocktail Sort can be slightly more efficient than the Bubble Sort in some cases, it still has an average and worst-case time complexity of O(n^2), making it inefficient for sorting larger datasets.
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
void cocktailSort(int arr[], int size)
{
int i, changed = TRUE, temp, start = 0, end = size - 1;
while (changed)
{
changed = FALSE;
for (i=start; i<end; i++)
{
if (arr[i] > arr[i+1])
{
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
changed = TRUE;
}
}
end--;
if (changed == FALSE)
{
break;
}
changed = FALSE;
for (i=end-1; i>=start; i--)
{
if (arr[i+1] < arr[i])
{
temp = arr[i+1];
arr[i+1] = arr[i];
arr[i] = temp;
changed = TRUE;
}
}
start++;
}
}
int main()
{
int i, n;
printf("Enter the size of the array: ");
scanf("%d", &n);
int* arr = (int*)malloc(sizeof(int) * n);
for (i = 0; i < n; i++)
{
printf("Number #%d: ", i + 1);
scanf("%d", &arr[i]);
}
printf("You entered: ");
for (i=0; i<n; i++)
{
printf("%d ", arr[i]);
}
cocktailSort(arr, n);
printf("\nSorted array: ");
for (i=0; i<n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
free(arr);
return 0;
}
