I am writing a code for Quick Sort of a list in Python 3.6.
At every step I have printed out the values of i and j (the two variables that I have used) along with the list (also, the values that are being swapped). The code works fine until the last step i.e. the swapping of 40 and 50. After placing the 60, it doesn't move further to this last step (swapping 40, 50). I'm not sure why this happens. Until then, everything is good.
** I have tried to write the program on my own, so please ignore the efficiency of the algorithm for the time being (although, any suggestions are welcome)
L=[35, 10, 40, 20, 60, 30, 90, 70, 50]
l=0
h=9
def partition (L, l, h):
print("\n########## Partition() invoked: ",l,h)
pivot = L[l]
i = l
j = h
#print(i,j)
while i<j:
print(pivot, "***********", L)
while True:
i=i+1
print("i=",i, L[i])
if L[i]>pivot or i>=len(L):
break
while True:
j=j-1
print("j=",j, L[j])
if L[j]<=pivot or j<0:
break
print("Check greater", i, j)
if i>j:
break
print("Swapping: ",L[i],L[j])
L[i], L[j] = L[j], L[i]
print("l=", L[l], " j=", L[j], L)
j_val=L[j]
l_val=L[l]
L[l]=j_val
L[j]=l_val
print("l=", L[l], " j=", L[j] , l, j, L)
return i
def QuickSort( L, l, h):
print(l, h)
j = partition(L, l, h)
partition(L, l, j+1)
partition(L, j, h)
QuickSort(L,l,h)
print(L)
My final result : [10, 20, 30, 35,50, 40, 60, 70, 90] (after putting 60 in the right place, the program ended)
I have tried the following change to the QuickSort function (after referring to other answers), but the results are even more messed up...
def QuickSort( L, l, h):
print(l, h)
j = partition(L, l, h)
partition(L, l, j)
partition(L, j+1, h)
Your implementation of QuickSort is incorrect. It's not recursive, it just calls partition three times, which won't fully sort lists with more than a few elements. The later two calls should be recursive calls to QuickSort instead.
Of course, when you make the code recursive, you also need to add a base case so the recursion will end. Fortunately, it's easy to see when further sorting is not needed by looking at l and h. A portion of the list with fewer than two elements in it doesn't need any more sorting.
Here's how I'd do it:
def QuickSort(L, l, h):
if h - l < 2: # add a base case
return
j = partition(L, l, h)
QuickSort(L, l, j) # recurse
QuickSort(L, j+1, h) # here too
As a side note, using l (lowercase L) as a variable name is generally discouraged, as in some fonts it is very hard to tell the difference between it and a 1 (a one digit). I'd also avoid using variables that differ only in case (as l and L do). Better names are more descriptive. While i and j are sometimes OK for indexes, I would greatly prefer names with more letters for almost anything even slightly more complicated. In this case, low and high might be better names for the arguments.