Как бы quickselectg действовал иначе, если бы пивот не был среднесрочным

Question

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

k = len(aList)//2 and the list is aList = [1,2,3,4,5]

Итак, как бы программа действовала по-другому, если бы pivot начинался с первого элемента списка каждый раз. Должен ли я сделать это в центре? Также, где я должен начать time.clock(), чтобы найти истекшее время функции. Вот код

def quickSelect(aList, k)

   if len(aList)!=0:
   pivot=aList[(len(aList)//2)]
   smallerList = []
   for i in aList:
       if i<pivot:
            smallerList.append(i)
   largerList=[]
   for i in aList:
       if i>pivot:
            largerList.append(i)
   m=len(smallerList)
   count=len(aList)-len(smallerList)-len(largerList)
   if k >= m and k<m + count:
      return pivot
   elif m > k:
      return quickSelect(smallerList,k)
   else:
      return quickSelect(largerList, k - m - count)

Answer 1

Я не вижу никакой проблемы в размещении оси в начале. Но это было бы просто для инициализации оси. Вся идея поворота обычно состоит в том, чтобы найти средний элемент.

Пожалуйста, попробуйте это для расчета времени:

import time

start_time = 0
aList = [1,2,3,4,5]
k = len(aList)//2  

def quickSelect(aList, k):
    start_time = time.time()
#     print "%10.6f"%start_time
#     pivot = aList[0]
    if len(aList) != 0:
        pivot = aList[(len(aList) // 2)]
        smallerList = []
        for i in aList:
            if i < pivot:
                smallerList.append(i)
                largerList = []
        for i in aList:
            if i > pivot:
                largerList.append(i)
        m = len(smallerList)
        count = len(aList) - len(smallerList) - len(largerList)
        if k >= m and k < m + count:
            print "Pivot", pivot
#             print "%10.6f"%time.time()
            print "time: ", time.time() -start_time
            return pivot
        elif m > k:
            return quickSelect(smallerList, k)
        else:
            return quickSelect(largerList, k - m - count)


quickSelect(aList, k)

В этом случае время становится нулевым, потому что ваш список очень мал. Пожалуйста, дайте мне знать, если я неверно истолковал ваш вопрос.

ВЫХОД:

Pivot 3
time:  0.0