Reference no: EM132087326
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 = b-1 # 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)