Функция медианы 3 быстрой сортировки не работает - PullRequest
Новая
       9

Функция медианы 3 быстрой сортировки не работает

0 голосов
/ 23 апреля 2020

Я пытаюсь получить алгоритм средней быстрой сортировки, реализованный в python, но не могу понять, что не так и почему он не работает 

from statistics import median

def Swap(arr, posA, posB):
    arr[posA], arr[posB] = arr[posB], arr[posA]

def Median(array):
    medianValue = median([array[0], array[int(len(array)/2)], array[-1]])
    return array.index(medianValue)

def Partition(array, start, end):
    pivot = array[end]
    i = start-1
    for j in range(start, end):
            if array[j] <= pivot:
                i += 1
                Swap(array, i, j)
    Swap(array, i+1, end)
    return i + 1

def Quicksort(array, startInd, endInd):
    if startInd < endInd:
        medianIndex = Median(array)
        Swap(array, medianIndex, endInd)
        pivot  = Partition(array, startInd, endInd)
        Quicksort(array, startInd, pivot  - 1)
        Quicksort(array, pivot  + 1, endInd)

Спасибо за любую помощь:)

1 Ответ

0 голосов
/ 23 апреля 2020

проблема в том, что вы получаете медиану из трех на основе всего массива, а не подсекции, над которой вы работаете. Возможное исправление:

Измените медиану на: 

def Median(array, firstVal, middleVal, endVal):
    if (firstVal - middleVal) * (endVal - firstVal) >= 0:
        medianValue =  firstVal

    elif (middleVal - firstVal) * (endVal - middleVal) >= 0:
        medianValue = middleVal

    else:
        medianValue = endVal

    return array.index(medianValue)

, а затем измените функцию быстрой сортировки на 

def Quicksort(array, startInd, endInd):
    if startInd < endInd:
        # get median
        middleVal = (endInd + startInd) // 2
        medianIndex = Median(array, array[startInd], array[middleVal],
            array[endInd])
        #
        Swap(array, medianIndex, endInd)
        pivot  = Partition(array, startInd, endInd)
        Quicksort(array, startInd, pivot  - 1)
        Quicksort(array, pivot  + 1, endInd)
...