Получение медианы несортированного списка с алгоритмом выбора

Question

У меня есть список целых чисел, и я хочу использовать выделение, чтобы найти медиану этого несортированного списка. Это то, что у меня есть до сих пор, но я не получаю никакого вывода для своего тестового списка [140, 240, 180, 400, 340]. Может кто-нибудь объяснить, что нужно сделать, чтобы получить медиану?

Мой код

def fastSelect(aList, k): 

    count = 0 
    pivot = 0 
    smallerList = [] 
    largeList = [] 
    while aList != []: 
     pivot == len(aList)//2 
     for i in range(0,pivot): 
      smallerList.append(aList[i]) 
     for j in range(pivot + 1,len(aList)): 
      largeList.append(aList[j]) 
     for g in range(0,len(aList)): 
      if aList[g] == pivot: 
       count += 1 
     m = len(smallerList) 
     if k >= m and k < m + count: 
      return pivot 
     if m > k: 
      aList = smallerList 
     else: 
      k = k - m - count 
      aList = largeList 

Answer 1

Вы на самом деле не сравнивая с вашей pivot значения. У вас также есть ошибка, которую вы используете == вместо = для назначения с вашей инициализацией pivot.

def fastSelect(aList, k): 
    while aList: 
     smallerList = [] 
     largeList = [] 
     count = 0 
     pivot = aList[len(aList) // 2] 
     for i in aList: 
      if i < pivot: 
       smallerList.append(i) 
      elif i > pivot: 
       largeList.append(i) 
      else: 
       count += 1 
     m = len(smallerList) 
     if k >= m and k < m + count: 
      return pivot 
     if m > k: 
      aList = smallerList 
     else: 
      k = k - m - count 
      aList = largeList 

Чтобы понять, почему pivot становится медиану, вы должны думать о том, что определение медианы. Медиана - это значение в списке, которое меньше или равно половине других значений и больше или равно половине других значений.

Первый раз через цикл среднее значение выбирается как pivot. Затем он разбивает список на два списка: один, который содержит значения, которые меньше, чем pivot, и тот, который содержит значения, которые больше, чем pivot. Аналогичным образом поддерживается count значений, равных pivot. Затем он видит, сколько значений в каждом списке. Если оба списка имеют одинаковый размер или в пределах разницы count, то по определению мы нашли медиану, поэтому мы возвращаем pivot.

Итак, теперь мы должны поддерживать этот инвариант по всему циклу. Давайте посмотрим на каждый из случаев. Если размер smallerList (который представлен как m) больше k, то медиана должна быть внутри smallerList, и мы все еще ищем элемент kth внутри smallerList. Если k больше m то медианный должен быть внутри largeList, но мы больше не нужен kth элемента внутри largeList, потому что мы уже нашли m и count элементов, которые меньше или равны pivot, поэтому мы вычитаем те из k перед продолжением цикла.

И, наконец, вы можете улучшить этот код, используя случайный стержень. Если вы посмотрите статью Википедии на Quickselect algorithm, вы увидите, что случайный стержень гарантирует почти определенную линейную временную сложность, в то время как выбранная вами средняя позиция, которая вы выбрали, имеет более предсказуемый худший анализ.