Subject : Computer Alorithms

2) Again, considering the array A={36, 26, 12, 25, 22, 19, 11, 10, 14, 16, 21, 13, 17, 18, 15}:

a) Draw each step of PARTITION(A,1,15) (page 171). *Tip: Use Figure 7.1 as example.

b) Draw each step of QUICKSORT(A) (page 171). *Tip: In each iteration, use only steps (a) and (i) in Figure 7.1 as example.

c) Prove that QUICKSORT has quadratic running time when A has distinct values sorted in reverse order.

d) What is the asymptotic running time of QUICKSORT when all values in A are equal?

Reference book

Introduction to Algorithms 3rd edition

Ebook URL:

http://ce.bonabu.ac.ir/uploads/30/CMS/user/file/115/EBook/Introduction.to.Algorithms.3rd.Edition.Sep.2010.pdf

Figure 7.1 is available in the page number 193 in the ebook given above

Figure 7.1 is attached

i pj (a) p,i j (c) (d) 2 8 7 1 3 5 6 4 P 7 8 (e) 2 1 3 5 6 4 2 1 3 8 7 5 6 4 j r (g) 2 1 3 8 7 5 6 4 (h) 2 1 3 8 7 5 6 4 2 1 3 4 7 5 6 8 Figure 7.1 The operation of PARTITION on a sample amay. Array entry Alr becomes the pivot element x. Lightly shaded array clements are all in the first partition with values no grcater than x. Heavily shaded clements are in the second partition with values greater than x. The unshaded cl- cments have not yet been put in one of the first two partitions, and the final white clement is the pivot x. (a) The initial amay and variable settings. None of the clements have bcen placed in cither of the first two partitions. (b) The value 2 is with itself" and put in the partition of smaller "swappcd values. (c) The values 8 and 7 are added to the partition of larger values. (e)The values l and 8 are swapped, and the smaller partition grows. (r The values 3 and 7 are swapped, and the smaller partition grows. (g-Hh The larger partition grows to include 5and 6, and the loop terminales. (i In lines 7-8, the pivot element is swapped so that it lies between the two partitions