Question

TO BE DONE IN C LANGUAGE

BEFORE READING THE QUESTION PLEASE NOTE THAT YOUR FUNCTION SHOULD EXACTLY PRODUCE THE GIVEN OUTPUT AND THE TIME COMPLEXITY SHOULD BE O(N^2)

YOU NEED TO KNOW ABOUT COCKTAIL SHAKER SORT ALGORITHM:

Cocktail-shaker sort is a modification of Bubble sort. Cocktail-shaker sort traverses the data structure in one direction, pushing the largest element ahead towards one end of the data structure, and then in the opposite direction, pushing the smallest element towards the other end, until all elements are sorted.

Implement cocktailshaker_sort that sorts the array data with length data_len. It also prints out data right at the beginning, i.e., before any sorting has occurred, and every time one element has reached its correct location SEE SAMPLE OUTPUT! (this means likely after moving one element all the way up or down respectively).

DO NOT CHANGE THE PARAMETER NAMES

TIME COMPLEXITY: O(N^2) , SEE THE GIVEN OUTPUT!

void cocktailshaker_sort(int *data, const int data_len) {
// your implementation goes here
}

INPUT:

1 10 8 20 5 4

OUTPUT:

[1, 10, 8, 20, 5, 4]
[1, 8, 10, 5, 4, 20]
[1, 4, 8, 10, 5, 20]
[1, 4, 8, 5, 10, 20]
[1, 4, 5, 8, 10, 20]

PLEASE MAKE SURE TO IMPLEMENT IN A WAY SO THAT THE DESIRED OUTPUT IS PRINTED

Answer 1

Answer:

C program to Implement cocktailshaker_sort that sorts the array data to get output value as per your requirment:

#include <stdio.h>

void Swap(int* a, int* b)
{
   *a ^= *b;
   *b ^= *a;
   *a ^= *b;
}

void CocktailSort(int* data, const int data_len)
{
   while (1)
   {
       char flag;
       int start[2] = { 1, data_len - 1 };
       int end[2] = { data_len, 0 };
       int inc[2] = { 1, -1 };

       for (int it = 0; it < 2; ++it)
       {
           flag = 1;

           for (int i = start[it]; i != end[it]; i += inc[it])
           {
               if (data[i - 1] > data[i])
               {
                   Swap(data + i - 1, data + i);
                   flag = 0;
               }
           }
          
           for (int i = 0; i < data_len; ++i)
           printf("%d%s", data[i], i == data_len - 1 ? "\n" : " "); // code to get output value as per your requirment
           if (flag)
           return;
       }
   }
}

int main(void) {
   int b[] = { 1, 10, 8, 20, 5, 4 };
   int i;
   size_t len = sizeof(b)/sizeof(b[0]);
printf("\nINPUT:\n");
for (i = 0; i < len; i++)
printf("%d%s", b[i], i == len - 1 ? "\n" : " ");
printf("\nOUTPUT:\n");
for ( i = 0; i < len; ++i)
printf("%d%s", b[i], i == len - 1 ? "\n" : " ");
CocktailSort(b, len);
   return 0;
}

Snapshot of the program execution: