quicksort code in Python

Question

I am trying to code quicksort in Python but wasn't able to correct the errors? How do I fix all these errors? Is there anything wrong with the logic?

Traceback (most recent call last):  
  line 35, in module  
  line 5, in quicksort  
  line 3, in quicksort  
  line 30, in partition  
IndexError: list index out of range

Here is my code:

def quicksort(a, beg, end):
   if beg < end:
     split = partition(a, beg, end)
     quicksort(a, beg, split-1)
     quicksort(a, split+1, end)

def partition(a, beg, end):
    left = beg
    right = end
    pivot = left
    done = True
    while done:
        while a[pivot] <= a[right] and pivot != right:
            right = right - 1
        if pivot == right:
           done = False
        elif a[pivot] > a[right] :
           temp = a[right]
           a[right] = a[pivot]
           a[pivot] = a[temp]
           pivot = right 

        while a[pivot] >= a[left] and pivot != left:
            left = left + 1
        if pivot == left:
            done = False
        elif a[pivot] < a[left] :
           temp = a[left]
           a[left] = a[pivot]
           a[pivot] = a[temp]
           pivot = left
    return pivot             

a = [4, 5, 7, 3, 6, 22, 45, 82]
quicksort(a, 0, len(a)-1)
print(a)

add the full traceback to your question. It will show you where your code is failing — joel goldstick
– joel goldstick, Commented Jul 31, 2016 at 16:07

joel goldstick · Accepted Answer · 2016-07-31 17:34:05Z

1

    elif a[pivot] > a[right] :
       temp = a[right]
       a[right] = a[pivot]
       a[pivot] = a[temp]
       pivot = right

Notice you set a[pivot] to a[temp]. You need to set it to temp.

and here:

   elif a[pivot] < a[left] :
       temp = a[left]
       a[left] = a[pivot]
       # a[pivot] = a[temp]
       a[pivot] = temp
       pivot = left

Even better, use tuple unpacking -- you don't need temp:

    elif a[pivot] > a[right] :
       a[pivot], a[right] = a[right], a[pivot]
       """
       temp = a[right]
       a[right] = a[pivot]
       a[pivot] = a[temp]
       """

answered Jul 31, 2016 at 17:34

joel goldstick

4,5136 gold badges34 silver badges46 bronze badges

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

2 Comments

Pygirl Over a year ago

so that's where i was getting the out of the index list error .thanks mr joel .it's working now

joel goldstick Over a year ago

I know its working. I tested it. You can check my answer if it solved your problem @KritiSahu

Collectives™ on Stack Overflow

quicksort code in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related