Quicksort - 選択した3つのピボットのメディア

Question

def quicksort(L, low, high): 
    total = 0 
    if low < high: 
     pivot_location, total = Partition(L, low, high) 
     total += quicksort(L,low,pivot_location) 
     total += quicksort(L,pivot_location + 1, high) 
    return total 

def Partition(L, low, high): 
    print(L) 
    #print(high) 
    total = 0 
    if (high - low) % 2 == 0: 
     middle = (high - low) // 2 - 1 
    else: 
     middle = ((high - low) // 2) + low 
    print(L[low]) 
    print(L[high - 1]) 
    print(L[middle]) 
    numbers = [] 
    numbers.append(L[low]) 
    numbers.append(L[middle]) 
    numbers.append(L[high - 1]) 
    if L[low] > L[middle] and L[low] < L[high - 1]: 
     pivot = L[low] 
    elif L[low] >L[high -1] and L[low] < L[middle]: 
     pivot = L[low] 
    elif L[middle] < L[low] and L[middle] > L[high -1]: 
     temp = L[low] 
     L[low] = L[middle] 
     L[middle] = temp 
     pivot = L[low] 
    elif L[middle] < L[high - 1] and L[middle] > L[low]: 
     temp = L[low] 
     L[low] = L[middle] 
     L[middle] = temp 
     pivot = L[low] 
    elif L[high - 1] < L[low] and L[high - 1] > L[middle]: 
     temp = L[low] 
     L[low] = L[high - 1] 
     L[high - 1] = temp 
     pivot = L[low] 
    else: 
     temp = L[low] 
     L[low] = L[high - 1] 
     L[high - 1] = temp 
     pivot = L[low] 
    print(pivot) 
    i = low + 1 
    for j in range(low + 1,high,1): 
     total += 1 
     if L[j] < pivot: 
      temp = L[j] 
      L[j] = L[i] 
      L[i] = temp 
      i += 1 
    temp = L[low] 
    L[low] = L[i -1] 
    L[i - 1] = temp 
    #print(L) 
    return i - 1,total 

c = [2148,9058,7742,3153,6324,609,7628,5469,7017,504] 
print(quicksort(c, 0, len(c))) 
print(c) 

私はクイックソートをこのように実装しました。最初の要素をピボットとして、最後の要素をピボットとして使用してみましたが、完全に機能しました。しかし、私は3つの要素の中央値をピボットとして選択する方法を理解することはできません：まず、中、最後。それぞれの再帰呼び出しで選択する方法に関するヘルプは、中間要素を呼び出します。私は余分なメモリを使いたくないので、配列全体の各再帰呼び出しに引数として渡したいと思います。

Answer 1

位置に3つの要素の中央値を配置する別の方法：代わりに大きなif-elif-elseブロックの

medianfirst(L,low,middle,high-1) 
    pivot = L[low] 

：

は

def compareswap(L,a,b): 
    L[a], L[b] = min(L[a],L[b]),max(L[a],L[b]) 

def medianfirst(L,a,b,c): 
    compareswap(L,b,a) # L[b]<=L[a] 
    compareswap(L,b,c) # L[b]<=L[c] i.e L[b] smallest 
    compareswap(L,a,c) # L[a]<=L[c] i.e L[c] largest 

今でPartitionにmedianfirstを使用しています。

---- UPDATE ----

改訂Partition、便宜上 （区間でも要素の最初の選択するmiddleを固定）：へ

def Partition(L, low, high): 
    print(L) 
    total = 0 
    middle = (low+high-1)//2 
    medianfirst(L,low,middle,high-1) 
    pivot = L[low] 
    i = low + 1 
    for j in range(low + 1,high,1): 
     total += 1 
     if L[j] < pivot: 
      L[i],L[j] = L[j],L[i] 
      i += 1 
    L[low],L[i-1] = L[i-1],L[low] 
    return i - 1,total 

Answer 2

def partition_median(L, low, high): 
    left = L[low] 
    right = L[high-1] 
    length = high - low 
    if length % 2 == 0: 
     middle = L[int(low + length/2 - 1)] 
    else: 
     middle = L[int(low + length/2)] 
    pivot = median(left, right, middle) 
    pivotindex = L.index(pivot) #works only for unique values 
    L[pivotindex] = L[low] 
    L[low] = pivot 
    i = low + 1 
    for j in range(low + 1, high): 
     if L[j] < pivot: 
      temp = L[j] 
      L[j] = L[i] 
      L[i] = temp 
      i += 1 
    leftend = L[low] 
    L[low] = L[i-1] 
    L[i-1] = leftend 
    return i - 1 

まあ、おかげで私が手に入れた助けと、上記のパーティションサブルーチンを使って私が望むものを実装することができたと思っています！