CODEWITHSUNDEEP
pythonsortinginfinite-loopquicksort
Shubham Chandel
Shubham Chandel

Reputation: 3191

Quicksort: Infinite Loop

The following implementation of QuickSort runs into infinite loop

def partition(arr, lo, hi):
    pivot = lo
    for i in range(lo+1, hi+1):
        if arr[i] <= arr[lo]:
            pivot += 1
            arr[i], arr[pivot] = arr[pivot], arr[i]
    arr[lo], arr[pivot] = arr[pivot], arr[lo]
    return pivot

def quickSort(arr, lo=0, hi=None):
    if not hi: hi = len(arr) - 1
    if lo >= hi: return

    pivot = partition(arr, lo, hi)
    quickSort(arr, lo, pivot-1)
    quickSort(arr, pivot+1, hi)


arr = [5,3,2,-9,1,6,0,-1,9,6,2,5]
quickSort(arr)
print(arr)

I presume the partition function is the culprit. Not able to figure out the mistake.

Thanks

Upvotes: 0

Views: 379

Answers (2)

prabodhprakash
prabodhprakash

Reputation: 3927

At one point, your loop never works in partition def. See below

[5, 3, 2, -9, 1, 6, 0, -1, 9, 6, 2, 5]
lo 0 hi 11
pivot 8
[5, 3, 2, -9, 1, 0, -1, 2, 5, 6, 6, 9]
lo 0 hi 7
pivot 7
[2, 3, 2, -9, 1, 0, -1, 5, 5, 6, 6, 9]
lo 0 hi 6
pivot 5
[-1, 2, -9, 1, 0, 2, 3, 5, 5, 6, 6, 9]
lo 0 hi 4
pivot 1
[-9, -1, 2, 1, 0, 2, 3, 5, 5, 6, 6, 9]
lo 0 hi 11
pivot 0
[-9, -1, 2, 1, 0, 2, 3, 5, 5, 6, 6, 9]
lo 1 hi 11

partition doesn't seem to be doing the entire job and correctly, it is a two step process. See a sample partition def below. Also, you can refer to original source here: 

 def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

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

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

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

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark

Upvotes: 3

Blckknght
Blckknght

Reputation: 104712

The problem is with your initialization code for hi:

if not hi: hi = len(arr) - 1

The condition not hi is True if hi is zero.

This causes quicksort(arr, 0, 0) and quicksort(arr, 1, 0) (one of which will almost always occur in the process of sorting) to try to sort most of the list again, rather than being an end to the recursion.

You should use the more specific test if hi is None instead of if not hi. This way you'll never incorrect reinitialize hi if it's zero, and the initialization code will only run if hi is None because it was not passed in to the function by the user.

Upvotes: 1

Related Questions