If the outermost while loop of our implementation of inplace quick sort (line 7
ID: 3830255 • Letter: I
Question
If the outermost while loop of our implementation of inplace quick sort
(line 7 of Code Fragment 12.6) were changed to use condition left < right
(rather than left <= right), there would be a flaw. Explain the flaw and
give a specific input sequence on which such an implementation fails.
Code Fragment 12.6:
1 def inplace quick sort(S, a, b):
2 ”””Sort the list from S[a] to S[b] inclusive using the quick-sort algorithm.”””
3 if a >= b: return # range is trivially sorted
4 pivot = S[b] # last element of range is pivot
5 left = a # will scan rightward
6 right = b1 # will scan leftward
7 while left <= right:
8 # scan until reaching value equal or larger than pivot (or right marker)
9 while left <= right and S[left] < pivot:
10 left += 1
11 # scan until reaching value equal or smaller than pivot (or left marker)
12 while left <= right and pivot < S[right]:
13 right = 1
14 if left <= right: # scans did not strictly cross
15 S[left], S[right] = S[right], S[left] # swap values
16 left, right = left + 1, right 1 # shrink range
17
18 # put pivot into its final place (currently marked by left index)
19 S[left], S[b] = S[b], S[left]
20 # make recursive calls
21 inplace quick sort(S, a, left 1)
22 inplace quick sort(S, left + 1, b)
Explanation / Answer
If the condition in the outer while loop is made left < right, then: a. If the size of the array from left to right (including both) is a multiple of 2, it would yield the correct result since left = right will never happen.
b. If the size of the array from left to right (including both) is odd, it will lead to a flaw if the element at position (left + right)/2 is lesser than the pivot element. In this case, the element at (left + right)/2 will not be compared to the pivot. For eg. for array 5,5,1,1,1,3 where the last element 3 is the pivot. Using left < right would give the result: 1,1,3,1,5,5. As the pivot would get swapped with the value of left index, before exiting the loop, which would be the position of the first 1 in the original array. This is flawed since the correct answer should be 1,1,1,3,5,5. Ensuring left <= right ensures that this middle element (left + right)/2 is also compared with the pivot.