If the conditional at line 14 of our inplace quick sort implementation of Code F

Question

If the conditional at line 14 of our inplace quick sort implementation 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)

This is a screenshot of code fragement they gave me to work with. This is from my book. I hope this helps.

l def inplace quick sort(S, a, b) 2 """Sort the list from Slal to S bl inclusive using the quick-sort algorithm. if a b: return range is trivially sorted 4 pivot S[b] last element of range is pivot 5 eft 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 SIleft

Explanation / Answer

QuickSort is mainly works based on Divide and Conquer algorithm.As like it picks an element as pivot and partitions the given array around the picked pivot.There are several ways we can pick pivot:

pick first element as pivot.
pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.
The main key process in it is partition.First given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements before x, and put all greater elements after x. All this should be done until sorted in right way.

As per question by replasing left <= right with left < right,the code would be as follows

def inplace_quick_sort(S,A,B):
if A<B:

splitpoint = partition(S,A,B)

inplace_quick_sort(S,A,splitpoint-1)
inplace_quick_sort(S,splitpoint+1,B)

def partition(S,A,B):
pivotvalue = S[A]

leftmark = A+1
rightmark = B

done = False
while not done:

while leftmark <= rightmark and S[leftmark] <= pivotvalue:
leftmark = leftmark + 1

while S[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1

if rightmark < leftmark:
done = True
else:
temp = S[leftmark]
S[leftmark] = S[rightmark]
S[rightmark] = temp

temp = S[A]
S[A] = S[rightmark]
S[rightmark] = temp

return rightmark

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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