Prove that the quicksort algorithm on page 371 is correct with the following cha

Question

Prove that the quicksort algorithm on page 371 is correct with the following change: Do not place a1back into the first list. Instead, place a1 between the result of calling quicksort on the elements less than a1 (or less than equal if you want to allow duplicates) and the result of calling quicksort on elements greater than a1.

Page 371 Algorithm:

The quick sort is an efficient algorithm. To sort
a1, a2, . . . , an, this algorithm begins by taking the first
element a1 and forming two sublists, the first containing
those elements that are less than a1, in the order they
arise, and the second containing those elements greater
than a1, in the order they arise. Then a1 is put at the end
of the first sublist. This procedure is repeated recursively
for each sublist, until all sublists contain one item. The ordered
list of n items is obtained by combining the sublists
of one item in the order they occur.

Explanation / Answer

Answer:

Quicksort is an efficient sorting algorithm,and it is based on partitioning of array of data into smaller arrays.

Divide And Conquer is sorting algorithm and it is a type of quicksort algorithm.

QuickSort is having three steps.

Step1: Divide

One array is divided into two arrays. Assume that subarray A[p .. r] needs to be sorted into increasing order.

One of which holds values smaller than the specified value is called pivot. And another array holds values greater than the pivot value.

Partition the array into two subarrays A1 = A[p .. q 1] and A2 = A[q +1 .. r] .

Index q is computed as part of this step.

Each element in A1 is A[q] and A[q] is each element in A2.

Step2.Conquer

Sort the subarrays A1 and A2 recursively. (Recursion stops when each subarray has size 1.)

Quicksort partitions an array and then calls itself recursively twice to sort the two subarrays or sublists.

Step3: Combine

Nothing needs to be done.

Conceptual view of Partition:

Array A is:

Array A is:

P                                                                                                                         r

x(pivot)

        Partition(A,p,r)                                                                                                          

                     p                       q-1                                  q             q-1                              r     

x

<=x >x

p r

X(pivot)

keys<=x keys   >x    unrestricted      

• Initially,

– The “Keys x” region is empty.

– The “Keys > x” region is empty.

– The “Unrestricted” region extends from index p to index r 1.

– The pivot element is at index r.

• Each iteration of the loop shrinks the “Unrestricted” region by one element.

• At the end of the loop, the “Unrestricted” region is empty.

Algorithm:

Quicksort(A, n) 1: Quicksort (A, 1, n)

Quicksort (A, p, r)

1: if p r then return

2: q = Partition(A, p, r)

3: Quicksort (A, p, q 1)

4: Quicksort(A, q + 1, r).

Partition(A, p, r)

1: x = A[r]

2: i p – 1

3: for j p to r 1 do

4: if A[j] x then {

5: i i + 1

6: Exchange A[i] and A[j] }

7: Exchange A[i + 1] and A[r]

8: return i + 1

During the for-loop i + 1 is the position at which the next key that is greater than or equal to the pivot should go to.

p r

0 1 2 3 4 5 6 7 8 9

p q r

p q r p q r

p,r p,r p q,r p,q,r

p q,r p,r

p,r

x(pivot)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.