Несортированные списки с четным количеством элементов создают IndexError

Question

Я пытаюсь создать программу, которая реализует алгоритм быстрого выбора, чтобы найти медиану списка;Затем эта медиана используется для расчета разницы между каждым другим элементом в списке.

Например,

lst = [1,3,2] sortedList = [1,2,3]

будетreturn

lstMedian = 2

сумма sumDifference тогда равна

x = 2 - sortedList [0]

y= 2- sortedList [2]

sumDifference = x + y

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

Трассировка с использованием случайно сгенерированного списка несортированной длины:

Traceback (most recent call last):
[26, 66, 43, 47, 73, 75, 52, 81, 21, 73, 32, 92]
  File "~store_location.py", line 102, in <module>
    main()
X:  63
  File "~store_location.py", line 96, in main
    y = quickSelect(lst, x)
  File "~store_location.py", line 77, in quickSelect
    return quickSelect(largerList, k - m - count)
  File "~store_location.py", line 77, in quickSelect
    return quickSelect(largerList, k - m - count)
  File "~store_location.py", line 77, in quickSelect
    return quickSelect(largerList, k - m - count)
  File "~store_location.py", line 79, in quickSelect
    return aList[0]
IndexError: list index out of range

Я использую 3 основных функции для вычисления этого:

sumDistance:

def sumDistance(lst, median):
    """
    Find the total distance from each building to the optimal store location
    :param lst: Given list
    :param median: Calculated median of give list
    :return: sum of distances
    """
    total = 0

    for location in range(0, len(lst) - 1):
        total += abs(median - lst[location])

    return total

Найти медианный индекс:

def quickSelectHelper(L):
    """
    Find the index of the correct median depending on the length of the list (odd or even)
    :param L: Given list
    :return: the Median the needs to be translated (k'th element)
    """
    if len(L) % 2 == 0 and len(L) >= 2:
        idx1 = int((0.5 * len(L)) - 1)
        idx2 = (len(L) // 2)
        calculatedMedian = (L[idx1] + L[idx2]) // 2
    elif len(L) % 2 != 0 and len(L) >= 1:
        calculatedMedian = (0.5 * len(L)) - 0.5

    return calculatedMedian

Найти медианное значение:

def quickSelect(aList, k):
    """
    Sort the list until the k'th element is found
    :param aList: given list
    :param k: the element to find (k'th)
    :return: The median value of the given list
    """
    # print("qS at it again: ", aList, "with a length of: ", len(aList))
    if len(aList) != 0:
        pivot = aList[len(aList) // 2]
        smallerList = []
        largerList = []
        count = 0

        for dist in range(len(aList)):
            if aList[dist] > pivot:
                largerList.append(aList[dist])
            elif aList[dist] < pivot:
                smallerList.append(aList[dist])
            else:
                count += 1

        m = len(smallerList)

        if m <= k < m + count:
            return pivot
        elif m > k:
            return quickSelect(smallerList, k)
        else:
            return quickSelect(largerList, k - m - count)

    return aList[0]

Если моего контекста не хватает, не стесняйтесь смотреть на весь мой код (~ 100 строк)

Answer 1

Неверный возврат для вашего рекурсивного базового случая.Когда quickSelect вызывается с aList=[], вы return aList[0], даже если aList пусто (а [][0] всегда является IndexError).Не уверен, что имеет смысл в качестве базового варианта (None?), Но вам также, возможно, придется обрабатывать его при любых вызовах quickSelect.