I was trying to write the QuickSort algorithm using the Hoare Partition Scheme. I'm pretty sure my Partition function is correct. I use a variable 'Swaps' to indicate the movement of the left pivot towards the right and the movement of the right pivot towards the left. The Sort function works with the other Partition algorithm so I think that's fine as well. Yet I get the error.
inp=[2,3,6,3,9,7,8,0,5]
#Swap Function
def Swap(List, i, j):
temp=List[i]
List[i]=List[j]
List[j]=temp
#QuickSort Function
def QSort(List, Start, End):
if Start < End:
PIEnd=Partition(List, Start, End)
QSort(List,Start,PIEnd)
QSort(List,PIEnd+1,End)
return List
#Partition Function
def Partition (List, Start, End):
Swaps=0
PIStart=Start #PI = Pivot Index
PIEnd=End
for i in range(Start, End):
if List[PIStart] > List[PIEnd]:
Swap(List, PIStart, PIEnd)
Swaps=Swaps+1
if Swaps % 2 ==0:
PIStart=PIStart+1
else:
PIEnd=PIEnd-1
return PIEnd
print(QSort(inp, 0, 8))
Look in these two places ...
# QSort ...
PIEnd=Partition(List, Start, End)
QSort(List,Start,PIEnd)
QSort(List,PIEnd+1,End)
# Partition
if Swaps % 2 ==0:
PIStart=PIStart+1
else:
PIEnd=PIEnd-1
If you have an even quantity of swaps in any partition, then PIEnd
will not change, and your indirect recursion in QSort will stick on the same arguments. Your first low-half recursion does this. Revisit your logic. For starters, you should not depend on global variables for a solution.
Here's how I instrumented your code for a recursion trace:
call_count = 0
indent = ""
#QuickSort Function
def QSort(List, Start, End):
global call_count, indent
indent += " "
call_count += 1
print(indent, "ENTER QSort", Start, End, List)
if call_count > 2 * len(inp):
print(indent, "Too many calls")
exit(1)
if Start < End:
PIEnd=Partition(List, Start, End)
QSort(List,Start,PIEnd)
QSort(List,PIEnd+1,End)
print(indent, "ENTER QSort", Start, End, List)
indent = indent[2:]
return List
Output:
ENTER QSort 0 8 [2, 3, 6, 3, 9, 7, 8, 0, 5]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
Too many calls