0

I'm learning the quicksort algorithm, but for some reason, the output of this python implementation is just partially sorted, and I get the 'maximum recursion depth reached' for larger inputs. I've been banging my head against this for the last couple of days and I know it's probably something really stupid, but I can't seem to figure it out, so I'll appreciate any help. 

def ChoosePivot(list):
    return list[0]  

def Partition(A,left,right):
    p = ChoosePivot(A)
    i = left + 1

    for j in range(left + 1,right + 1): #upto right + 1 because of range()
        if A[j] < p:
                A[j], A[i] = A[i], A[j] #swap
                i = i + 1
    A[left], A[i - 1] = A[i-1], A[left] #swap
    return i - 1

def QuickSort(list,left, right):
    if len(list) == 1: return   
    if left < right:
        pivot = Partition(list,left,right)              
        QuickSort(list,left, pivot - 1)
        QuickSort(list,pivot + 1, right)
        return list[:pivot] + [list[pivot]] + list[pivot+1:]

sample_array = [39,2,41,95,44,8,7,6,9,10,34,56,75,100] 
print "Unsorted list: " 
print sample_array
sample_array = QuickSort(sample_array,0,len(sample_array)-1)
print "Sorted list:"
print sample_array
Improve this question
1
  • You should be thinking of the algorithm at a much higher level. That's how you might write it in a language such as C. It would be better to think of it functionally. Commented Apr 6, 2012 at 6:19

4 Answers 4

Reset to default
2

Not entirley sure this is the issue, but you are chosing pivot wrongly:

def ChoosePivot(list):
    return list[0]  
def Partition(A,left,right):
    p = ChoosePivot(A)
    ....

You are always taking the head of the original list, and not the head of the modified list.

Assume at some point you reduced the range to left=5,right=10 - you chose list[0] as the pivot - that can't be good.
As a result, in each iteration where left>0 you ignore the first element in the list, and "miss" it - which can explain the partial sorting

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks, that was it. Cheers amit!
1 
def ChoosePivot(list):
    return list[0]

As amit said, this is wrong. You want p = A[left]. However, there is another issue:

if A[j] < p:
    A[j], A[i] = A[i], A[j] #swap
i = i + 1

The pivot index should only be incremented when you swap. Indent i = i + 1 to the same depth as the swap, as part of the if statement.

Bonus question: Why are you partitioning twice?

Improve this answer

Comments

0

also last swap;

A[left], A[i - 1] = A[i-1], A[left] #swap

should be done with pivot.

Besides that Quicksort works inplace. So you don't need following return;

return list[:pivot] + [list[pivot]] + list[pivot+1:]

Improve this answer

Comments

-1

Not exactly an answer to your question, but I believe it's still of most relevance.

Choosing a pivot always on the same position when implementing quicksort is a flaw on the algorithm. One can generate a sequence of numbers that makes your algorithm run in O(n^2) time, and absolute run time probably worse than bubblesort.

In your algorithm, choosing the leftmost item makes the algorithm run in worst-case time when the array is already sorted or nearly sorted.

The choice of the pivot should be performed randomly to avoid this issue.

Check the algorithms' Implementation issues in Wikipedia: http://en.wikipedia.org/wiki/Quicksort#Implementation_issues

Actually, check the hole article. It IS worth your time.

Improve this answer

1 Comment

Choosing a pivot randomly only reduces the likelihood of running in worst-case time since there is nothing to stop the computer from randomly choosing the worst pivot - so to say random selection will avoid the issue is incorrect. Another way to select the pivot to try and avoid having quicksort run in quadratic time is to use the median-of-three approach - take the first, last and middle values, and select the median value.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.