I am working on the QuickSort - Median Three Algorithm. I have no problem with the first and last element sorting. But, when comes to the Median-three, I am slightly confused. I hope someone could help me on this.
Would be appreciate if someone could provide me some pseudocode?
My understanding is to get the middle index by doing this. (start + end) / 2 , then swap the middle pivot value to the first value, after all these done it should goes well with the normal quick sort ( partitioning and sorting).
Somehow, I couldn't get it works. Please help!
#Array Swap function
def swap(A,i,k):
temp=A[i]
A[i]=A[k]
A[k]=temp
# Get Middle pivot function
def middle(lista):
if len(lista) % 2 == 0:
result= len(lista) // 2 - 1
else:
result = len(lista) // 2
return result
def median(lista):
if len(lista) % 2 == 0:
return sorted(lista)[len(lista) // 2 - 1]
else:
return sorted(lista)[len(lista) // 2]
# Create partition function
def partition(A,start,end):
m = middle(A[start:end+1])
medianThree = [ A[start], A[m], A[end] ]
if A[start] == median(medianThree):
pivot_pos = start
elif A[m] == median(medianThree):
tempList = A[start:end+1]
pivot_pos = middle(A[start:end+1])
swap(A,start,pivot_pos+start)
elif A[end] == median(medianThree):
pivot_pos = end
#pivot = A[pivot_pos]
pivot = pivot_pos
# swap(A,start,end) // This line of code is to switch the first and last element pivot
swap(A,pivot,end)
p = A[pivot]
i = pivot + 1
for j in range(pivot+1,end+1):
if A[j] < p:
swap(A,i,j)
i+=1
swap(A,start,i-1)
return i-1
count = 0
#Quick sort algorithm
def quickSort(A,start,end):
global tot_comparisons
if start < end:
# This to create the partition based on the
pivot_pos = partition(A,start,end)
tot_comparisons += len(A[start:pivot_pos-1]) + len(A[pivot_pos+1:end])
# This to sort the the left partition
quickSort(A,start,pivot_pos -1)
#This to sort the right partition
quickSort(A,pivot_pos+1,end)
