(2) (20 pts) Cocktail-shaker sort is a variant of bubblesort. On odd num- bered
ID: 3584978 • Letter: #
Question
(2) (20 pts) Cocktail-shaker sort is a variant of bubblesort. On odd num- bered passes through the list, you run a standard pass of bubblesort (as in bubble the smallest from right to the left). On even numbered passes through the list, you run a "left to right" version of bubblesort, carrying the largest element you have seen from the left side of the list down and inverting it with the next element examined if it is out of order. For example, consider the input 2 9 1 7 8 3. After the first pass the list is 1 2937 8 , exactly like bubblesort. After the second pass, the list is 12 378 9. Also, we stop if no changes were made during the previous pass (a) Write pseudo-code for cocktail-shaker-sort (A, n) where A is the array A1 through A[n] (b) Even though bubblesort and cocktail-shaker sort are very similar, their running times can be quite different on specific inputs. Give an input (of size n) on which cocktail-shaker sort runs significantly faster than bubble-sort, i.e., on that input, the time taken by cocktail-shaker sort is big-oh of the time taken by bubble-sort but not the other way (c) Show that cocktail-shaker sort runs in O(n2) time (d) Show that cocktail-shaker sort runs in (n2) time, i.e., present an input and show that on that input the algorithm does (n2) work Note: Use 1 through n as input for this problem. So, 1 2 3 would be an input of size n. If the input are really integers in the range 1 through n, there are better sorting algorithms to use. But, that is not the point here TmExplanation / Answer
a.) Pseudo code for cocktail-shaker sort:-
Cocktail_ShakeSort(var A : ArrayType; N : integer);
.var
L,R,K,.J : integer;
.begin
.L := 2;
R := N;
.K := N;
.repeat
.for J := R downto L do
.if (A[J] < A[J - 1]) then
.begin
.Swap(A[J], A[J - 1]);
.K := J
.end;
L := K + 1;
.for J := L to R do
if (A[J] < A[J - 1]) then
.begin
.Swap(A[J], A[J - 1]);
.K := J
.end;
.R := K - 1;
.until L >= R
.end;
.
.procedure Swap(var X, Y : integer);
.var
.Temp : integer;
.begin
.Temp := X;
.X := Y;
Y := Temp
.end;
b.) Consider the example (2,3,4,5,1). Bubble sort requires four traversals of array for this example, while Cocktail sort requires only two traversals
c.)To analyze the complexity of ShakerSort, we can count the number of comparisons between pairs of elements, do a step-count analaysis, or proceed directly to do an asymptotic analysis. The number of element compares in the first phase is (n-1) + (n-2), in the second phase it is (n-3) + (n-4), and so on. Summing over all phases, we obtain (sum from i=1 to n-1)i = n(n-1)/2 as the number of comparisons.Hence, cocktail shaker sort os O(n*n).
d.)Suppose we start with an array a[0:n-1] of elements to be sorted. After the left to right bubbling pass of phase 1, the largest element is in the rightmost position. So the right to left pass needs to be concerned only with elements in positions 0 through n-2 of the array. Following the right to left pass, the smallest element is in position 0 of the array. Consequently, the next phase need be concerned only with the elements in positions 1 through n-2.
In general, the left to right pass of phase p of shaker sort needs to be concerned only with elements in positions p-1 through n-p, and the right to left pass of this phase needs to be concerned only with elements in positions n-p-1 through p.
To do a direct asymptotic analysis, we observe that phase p takes Theta(n-p) time. So the time for all phases is (sum from p=1 to n/2)(n-p) = (sum from q=n/2 to n-1)q = Theta(n2). The complexity of shaker sort is Theta(n2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.