deterministic quickselect pour la statistique de l'ordre python (médianes de l'approche médiane)

Question

dselect trouver la ième commande d'une statistique dans une liste donnée d'entiers non triés (sans doublons) en temps O (n), greffer sur le principe du tri rapide. La statistique d'ordre est définie comme le plus petit élément de la version triée de la liste donnée. Donc, 1ère statistique d'ordre serait l'élément le plus petit et n-ième statistique d'ordre serait le plus grand élément et ainsi de suite ...

En cours d'exécution, je reçois IndexError: list index out of range sur return arr[l] à la fin de la fonction dselect. Je pense que l'erreur se produit en raison de moi codant en dur l comme 0 dans l'appel récursif sur la liste medians sur la fonction dselect. (ligne 4)

Que dois-je faire pour éviter cette erreur? Comment dois-je mettre la valeur de l dans cet appel récursif? Est-ce même la source de cette erreur? Si c'est une question stupide, n'hésitez pas à le signaler et je vais supprimer cette question. Je devais juste demander cela parce que je suis coincé là-dessus depuis un bon moment maintenant. Merci.

def dselect(arr, l, r, i): 
    if l < r: 
     #finding pivot deterministically 
     medians = createMedianList(arr, l, r) 
     pivot = dselect(medians, 0, len(medians) - 1, len(medians) // 2) #line4 

     pivot = partition(arr, l, r, pivot) 
     if pivot + 1 == i: 
      return arr[pivot] 
     elif pivot + 1 > i: 
      return dselect(arr, l, pivot - 1, i) 
     else: 
      return dselect(arr, pivot + 1, r, i) 

    return arr[l] 

def partition(arr, l, r, pivot): 
    pivotIndex, i = arr.index(pivot), l 
    arr[l], arr[pivotIndex] = arr[pivotIndex], arr[l] 

    for j in range(l + 1, r + 1): 
     if arr[j] < arr[l]: 
      i += 1 
      arr[i], arr[j] = arr[j], arr[i] 
    arr[l], arr[i] = arr[i], arr[l] 

    return i 

def createMedianList(arr, l, r): 
    medians = [] 
    for i in range(l, (r + 1) - 5 + 1): 
     temp = sorted(arr[i:i + min(5, (r - l + 1) - i)]) 
     medians.append(temp[len(temp) // 2]) 

    return medians 

if __name__ == '__main__': 
    arr = [5, 2, 4, 3, 1, -1] 
    #arr = list(map(int, open('select.txt').read().splitlines())) 
    print(dselect(arr, 0, len(arr) - 1, int(input('Which order 
    statistic to find? ')))) 

Answer 1

Le problème est que createMedianList retourne parfois une liste vide: Cela se produit si l >= r-3 qui finira par arriver. Je suggère que vous ajoutiez quelque chose à createMedianList pour vous assurer qu'il ne retourne pas une liste vide. E.g .: if medians==[]:medians=[arr[0]] ou quelque chose de similaire (en fonction de quelles propriétés voulez-vous avoir pour les médianes).