На месте quicksort - python

Question

Я пытаюсь реализовать quicksort в python на месте. Я следил за псевдокодом из статьи wikipedia здесь, но это не приводит к сортировке списка. Что-нибудь кажется невероятно неправильным?

# Perform QuickSort in place 
def partition(arr,low,high): 
    pivotIndex = random.randint(0,high) 
    pivotValue = arr[pivotIndex] 

    currentIndex = low 

    t = arr[high] 
    arr[high] = pivotValue 
    arr[pivotIndex] = t 

    for i in range(low,high-1): 
     if arr[i] < pivotValue: 
      t = arr[i] 
      arr[i] = arr[currentIndex] 
      arr[currentIndex] = t 
      currentIndex += 1 
    t = arr[currentIndex] 
    arr[currentIndex] = arr[high] 
    arr[high] = t 
    return currentIndex 

def quickSort(arr,low,high): 
    # pick partition 
    if low < high: 
     part = partition(arr,low,high) 
     quickSort(arr,low,part-1) 
     quickSort(arr,part+1,high) 

arr = [1,3,6,7,9,10] 
quickSort(arr,0,len(arr)-1) 
print arr 

Answer 1

Ну, первая строка функции partition явно не так:

pivotIndex = random.randint(0, high) 

Это, очевидно, должно быть low вместо 0.

Ваши range значения могут быть выключены ... Я не думаю, что вам нужно вычесть 1 из high.

Answer 2

Кроме того, в Python вам не нужно использовать временную переменную для обмена.

Вместо:

t = x 
x = y 
y = t 

Вы можете сделать:

x, y = y, x 

Answer 3

Вы не забыли import random? Кроме того, чтобы увидеть разницу, ваш массив должен быть несортированным. Если элементы уже в правильном порядке, как вы можете найти разницу?

Кроме того, перечисляя все массивы как arr, это может запутать. Я заметил, что все функции с arr в них используют arr в качестве соответствующего параметра. Почему бы не сделать что-то, чтобы отличить их?