After running multiple time with same code with same input size in Python 3.4 throw IndexError: list index out of range

Question

I am new to Python. I wrote a code for quick sort to sort integer numbers in ascending order. Using - Ubuntu 16.10 and python3.5

Code -

import random

a=[]
n=int(input("Enter size :\n"))
for i in range(0,n):
        a.append(int(random.randrange(0,100)))
print("Before Sorting:",a)

def quick(a,low,high):
        if(low<high):
                i=low
                j=high
                key=a[low]
                flag=1
                while (flag==1):
                        i += 1
                        while(a[i]<key):
                                i += 1
                        while (a[j]>key):
                                j -= 1
                        if (i<j):
                                a[i],a[j]=a[j],a[i]
                        else:
                                flag=0
                a[low],a[j]=a[j],a[low]
                quick(a,low,j-1)
                quick(a,j+1,high)

# Calling function quick where a = List, 0 = Start Index ,n-1 = Last Index
quick(a,0,n-1)
print("After Sorting:",a)

When i run the code it throws IndexError: list index out of range but if i run the same code with same input it gives correct output. For example - Running the code for 1st time with n = 5

linux@linux-Lenovo-G50-30:~/PYTHON/practice/run1$ python3 quick.py
Enter size :
5
Before Sorting : [55, 23, 57, 86, 20]
Traceback (most recent call last):
  File "quick.py", line 30, in <module>
   quick(a,0,n-1)
  File "quick.py", line 27, in quick
   quick(a,j+1,high)
  File "quick.py", line 17, in quick
   while(a[i]<key):
  IndexError: list index out of range

Running the code for 2nd time with n = 5

Enter size :
5
Before Sorting : [6, 5, 93, 84, 32]
Traceback (most recent call last):
  File "quick.py", line 30, in <module>
    quick(a,0,n-1)
  File "quick.py", line 27, in quick
    quick(a,j+1,high)
  File "quick.py", line 17, in quick
    while(a[i]<key):
  IndexError: list index out of range

Running the code for 3rd time with n = 5

linux@linux-Lenovo-G50-30:~/PYTHON/practice/run1$ python3 quick.py
Enter size :
5
Before Sorting : [87, 18, 94, 1, 64]
After Sorting : [1, 18, 64, 87, 94]

I am not able to figure out why this happens. I am using Ubuntu 16.10 and python3.5

Answer 1

import random

a=[]
n=int(input("Enter size :\n"))
for i in range(0,n):
    a.append(int(random.randrange(0,100)))
print("Before Sorting:",a)    

def sort(a):
    less = []
    equal = []
    greater = []

    if len(a) > 1:
        pivot = a[0]
        for x in a:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
        return sort(less)+equal+sort(greater)
    else: 
        return a

a = sort(a)
print("After Sorting:",a)

Answer 2

The reason your code sometimes works and sometimes doesn't is that you are setting up a random array of numbers. As your post shows, even with the same input data (length of list) the numbers are different every time. Your quick() function works with some input data and fails with other input data. It is failing because a[i]<key assumes that there are i-1 elements in a, and depending on your data, sometimes there aren't.

The fix below makes your out-of-range error go away. I've run it a couple of dozen times and the results seem okay. I can't promise that the code is a correct implementation of Quicksort, though.

def quick(a,low,high):
        if(low<high):
                i=low
                j=high
                key=a[low]
                flag=1
                while (flag==1):
                        i += 1
                        while(i < len(a) and a[i]<key):
                                i += 1
                        while (j < len(a) and a[j]>key):
                                j -= 1
                        if (i<j):
                                a[i],a[j]=a[j],a[i]
                        else:
                                flag=0
                a[low],a[j]=a[j],a[low]
                quick(a,low,j-1)
                quick(a,j+1,high)