Index out of range - Quicksort in Python

Question

I'm trying to implement the quicksort algorithm, but I keep getting list index out of range.

What exactly is out of range at quicksort(array, left, Pi vot-1)?

def partition(array,left,right):
    #If pivot is not on leftmost, swap to make it leftmost
    Pivot = array[0]
    i = left+1
    for j in range(i,right):
        if array[j] < Pivot:
            #Swap array[j] and array[i]
            array[j], array[i] = array[i], array[j]
            i += 1;
    #Swap pivot and A[i-1]        
    array[Pivot], array[i-1] = array[i-1], array[Pivot]
    return Pivot

def quicksort(array,left,right):
    # Base case
    if len(array) <= 1:
        return array
    #Choose pivot
    Pivot = partition(array,left,right);
    #Partition array around a pivot
    #Recursive call
    quicksort(array, left, Pivot-1)
    quicksort(array, Pivot + 1, right)

print quicksort([1,5,3,4,9,10],0,5)

Error messages:

File "quicksort.py", line 25, in <module>
print quicksort([1,5,3,4,9,10],0,5)

File "quicksort.py", line 22, in quicksort
quicksort(array, left, Pivot-1)

File "quicksort.py", line 22, in quicksort
quicksort(array, left, Pivot-1)

File "quicksort.py", line 19, in quicksort
Pivot = partition(array,left,right);

File "quicksort.py", line 11, in partition
array[Pivot], array[i-1] = array[i-1], array[Pivot]

IndexError: list index out of range

Post the Error message..

Iron Fist
– Iron Fist

2015-07-14 06:19:45 +00:00
Commented Jul 14, 2015 at 6:19 — Iron Fist
– Iron Fist, Commented Jul 14, 2015 at 6:19
@KhalilAmmour-خليلعمورError messages added

Juanvulcano
– Juanvulcano

2015-07-14 06:23:35 +00:00
Commented Jul 14, 2015 at 6:23 — Juanvulcano
– Juanvulcano, Commented Jul 14, 2015 at 6:23

timrau · Accepted Answer · 2015-07-14 06:25:56Z

3

In partition(),

Pivot = array[0]

Here Pivot looks like the value of pivot element. However,

#Swap pivot and A[i-1]        
array[Pivot], array[i-1] = array[i-1], array[Pivot]

Here you use it as index to array. Thus it's very likely to be out of legal array index range.

answered Jul 14, 2015 at 6:25

timrau

23.1k4 gold badges55 silver badges67 bronze badges

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

Comments

The6thSense · Accepted Answer · 2015-07-14 06:28:42Z

2

During third iteration the value of pivot and array are as below

[10, 1, 3, 4, 9, 5] 10

In which you try to get array[Pivot]

Since it has only six elements ,So only the index out of range error is thrown

answered Jul 14, 2015 at 6:28

The6thSense

8,3459 gold badges38 silver badges67 bronze badges

Comments

Navneet · Accepted Answer · 2015-07-14 06:29:01Z

2

May be this may help.

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot


def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    if begin >= end:
        return
    pivot = partition(array, begin, end)
    quicksort(array, begin, pivot-1)
    quicksort(array, pivot+1, end)

answered Jul 14, 2015 at 6:29

Navneet

4,9431 gold badge21 silver badges29 bronze badges

1 Comment

The6thSense Over a year ago

add return in quicksort()

Collectives™ on Stack Overflow

Index out of range - Quicksort in Python

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related