Quicksort - Media of Three chosen pivot

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)

I have implemented quicksort this way. I tried using first element as pivot and last element as pivot and it worked perfectly. However I can't figure out how to choose as a pivot the median of the three elements: first, middle, last. Any help on how to choose in each recursive call the middle element. Note that I want to pass as an argument to each recursive call the whole array because I don't want to use any extra memory.

Yes, I am doing this but the problem is that I can't figure out how to choose the middle item in each subarray of each recursive call. The borders of each subarray in each recursive call are set from the values of low and high variables. — user6420403
No, using the code I posted below p, the middle element of race partitioned subarray isn't being selected properly. I need a way to choose the right middle element of each partitioned subarray. — user6420403
There is also another bug: Calculation of middle middle = (high - low) // 2 - 1 should probably have had a high+low and no -1. In any case: middle = (low + high) // 2 should be good for both odd and even high-low — Dan Getz

Dan Getz Dan Getz · Accepted Answer · 2017-03-21T15:34:22

Another way to put median of 3 elements into position:

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

Now use medianfirst in Partition with:

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

instead of the big if-elif-else block.

---- UPDATE ----

(fixed middle to choose first in even elements interval) For convenience, a revised Partition:

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

Quicksort - Media of Three chosen pivot

2 Answers