Question

An enhanced version of bubble sort, called Cocktail Sort (CS),

and its complementary version, denoted by CS-R. The main idea of CS is to alternate the following two
procedures: (P1) bubbling the largest to the right (starting from the leftmost item), (P2) bubbling the
smallest to the left (starting from the rightmost item), and then fix the leftmost and rightmost items and
iteratively continue on the remaining part. The CS-R acts in a way contrary to CS, and additionally, it takes
another Θ(n) to convert the reversely-sorted into sorted, where n denotes the input size.
Consider such an input instance: (27,17,3,16,13,10,1,5,7,12,4,8,9,0). Please state the outputs row by
row when applying CS and CS-R to the instance. Please use two tables each for CS and CS-R such that
the first row is the input array and then followed by rows are what obtained after applying (P1) and (P2)
alternatively (or the reverse version as shown in CS-R). You need not state the pseudo codes here. (10
Points)

Answer 1

For the input instance (27,17,3,16,13,10,1,5,7,12,4,8,9,0), the outputs for Cocktail Sort (CS) and its complementary version (CS-R) are as follows:

Cocktail Sort (CS):

1. Input: (27,17,3,16,13,10,1,5,7,12,4,8,9,0)

2. After (P1): (17,3,16,13,10,1,5,7,12,4,8,9,0,27)

3. After (P2): (0,1,5,7,12,4,8,9,10,13,16,17,27)

4. After (P1): (0,1,5,7,4,8,9,10,12,13,16,17,27)

5. After (P2): (0,1,4,5,7,8,9,10,12,13,16,17,27)

6. After (P1): (0,1,4,5,7,8,9,10,12,13,16,17,27)

7. After (P2): (0,1,4,5,7,8,9,10,12,13,16,17,27)

Cocktail Sort - Reverse (CS-R):

1. Input: (27,17,3,16,13,10,1,5,7,12,4,8,9,0)

2. After (P1): (0,1,5,7,12,4,8,9,10,13,16,17,27)

3. After (P2): (27,17,3,16,13,10,1,5,7,12,4,8,9,0)

4. After (Reversal): (0,1,5,7,12,4,8,9,10,13,16,17,27)

Step-by-step explanation:

Cocktail Sort (CS) involves the iterative application of two procedures: (P1) bubbling the largest to the right and (P2) bubbling the smallest to the left, fixing the leftmost and rightmost items in each iteration. The steps are performed alternatively until the array is sorted. For the input instance, the CS process is demonstrated, resulting in a sorted array.

Cocktail Sort - Reverse (CS-R) follows the opposite procedure, starting with a reversely-sorted array. Additionally, CS-R takes an extra Θ(n) to convert the reversely-sorted array into a sorted one. In the given input, CS-R is showcased, illustrating the conversion of a reversely-sorted array to a sorted one through the reversal of steps (P1) and (P2). The final result is a sorted array achieved through the complementary process of Cocktail Sort.