После запуска несколько раз с одним и тем же кодом с одинаковым размером ввода в Python 3.4 не будет выбрасывать IndexError: список индексов выходит за пределы диапазона

Question

Я новичок в Python. Я написал код для быстрой сортировки, чтобы сортировать целые числа в порядке возрастания. Использование - Ubuntu 16.10 и python3.5

Код -

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)

Когда я запускаю код, он выбрасывает IndexError: list index вне диапазона, но если я запускаю тот же код с тем же вводом, это дает правильный вывод. Например - Запуск кода в первый раз с 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

Запуск кода во второй раз с 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

Запуск кода в третий раз с 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]

Я не могу понять, почему это происходит. Я использую Ubuntu 16.10 и python3.5

Answer 1

Причина, по которой ваш код иногда работает, а иногда нет, состоит в том, что вы устанавливаете случайный массив чисел. Как показывает ваш пост, даже при одинаковых входных данных (длина списка) числа каждый раз разные. Ваш quick() Функция работает с некоторыми входными данными и не работает с другими входными данными. Это терпит неудачу, потому что a[i]<key предполагает, что есть i-1 элементы в aи, в зависимости от ваших данных, иногда нет.

Приведенное ниже исправление устраняет ошибку, выходящую за пределы допустимого диапазона. Я запускал его пару десятков раз, и результаты кажутся нормальными. Однако я не могу обещать, что код является правильной реализацией Quicksort.

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)

Answer 2

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)