Делаю QuickSort для удовольствия, но есть кое-что, чего я не понимаю

Question

Просто хочу убедиться, что это , а не домашнее задание.Я делаю это просто для развлечения и, возможно, для блога.

Я использую версию быстрой сортировки на месте в соответствии с этой вики-страницей .

Вот код, который я написал:

# solution 2

def swap(arr, left, right):
    try:
        tmp = arr[left]
        arr[left] = arr[right]
        arr[right] = tmp
    except IndexError:
        print "!IndexError: left, right", left, right
        raise

def partition(arr, left, right, pindex):
    pivot = arr[pindex]
    swap(arr, right, pindex)
    npindex = left
    for i in range(left, right+1): # +1 so the last item is included
        if arr[i] < pivot:
            swap(arr, i, npindex)   
            npindex += 1
    swap(arr, npindex, right)
    return npindex

def qs(arr):
    qs2(arr, 0, len(arr)-1)
    return arr

def qs2(arr, left, right):
    if left < right:
        # midpoint = (right - left) / 2
        midpoint = left # this works.
        nindex = partition(arr, left, right, midpoint)
        qs2(arr, left, nindex-1)
        qs2(arr, nindex+1, right)

def test():
    test = [23, 45, 12, 1, 3, -9, 67, 122, 8, 2, 0]
    res = qs(list(test))
    print "start\t", test
    print "end\t", res

if __name__ == "__main__":
    test() 

Что я не понимаю, так это, согласно википедии, выбор точки поворота (переменная средняя точка внутри функции qs2) может быть случайным, если он находится в пределах границ.

Однако, если я просто возьму среднюю точку (т.е. (влево + вправо) / 2), быстрая сортировка не будет работать.Используя значение left , оно работает.

Я что-то упустил из-за понимания алгоритма?

EDIT : я только что понял, что есть тег'быстрой сортировки' в стеке потокаЕсли этот вопрос уже задавался, прошу прощения и сообщите мне.Я закрою этот вопрос.Тем временем я прохожу эти вопросы с тегом быстрой сортировки

Answer 1

Выбор элемента сводки также осложняется наличием целочисленного переполнения.Если граничные индексы сортируемого подмассива достаточно велики, наивное выражение для среднего индекса (влево + вправо) / 2 вызовет переполнение и предоставит недопустимый сводный индекс.Это можно преодолеть, используя, например, left + (right-left) / 2 для индексации среднего элемента, за счет более сложной арифметики.Аналогичные проблемы возникают в некоторых других методах выбора элемента поворота.

Это должно быть (left + right) / 2, а не (right - left) / 2.Википедия объясняет, что использование left + (right - left) / 2 позволяет избежать целочисленного переполнения.

Answer 2

у вас есть midpoint = (right - left) / 2.Я думаю, что вы имеете в виду (right + left) / 2, в противном случае ваша средняя точка находится за пределами указанных границ.