1.3 Quick Sort (median of three numbers as pivot).py

""" Consider the first, middle, and final elements of the given array. (If the array has odd length it should be clear what the "middle" element is; for an array with even length 2k, use the k^{th} element as the "middle" element. So for the array 4 5 6 7, the "middle" element is the second one ---- 5 and not 6!) Identify which of these three elements is the median (i.e., the one whose value is in between the other two), and use this as your pivot. EXAMPLE: For the input array 8 2 4 5 7 1 you would consider the first (8), middle (4), and last (1) elements; since 4 is the median of the set {1,4,8}, you would use 4 as your pivot element. """ def QuickSort(A, l, r): """ Arguments: A -- total number list l -- left index of input list r -- right index of input list Returns: ASorted -- sorted list cpNum -- Number of comparisons """ # Number of comparisons cpNum = r - l # Base case if cpNum == 0: return [A[l]], 0 elif cpNum < 0: return [], 0 # Preprocessing of median-of-three # ------Way 1------ # n = r - l + 1 # c1 = A[l] > A[(l+r)//2] # c2 = A[l] > A[r] # c3 = A[(l+r)//2] > A[r] # if (c1 and c2 and c3) or (not (c1 or c2 or c3)): # A[l], A[(l+r)//2] = A[(l+r)//2], A[l] # elif (c1 and c2 and (not c3)) or (not (c1 or c2 or (not c3))): # A[l], A[r] = A[r], A[l] # ------Way 2------ # middelNum = sorted([A[l], A[(l+r)//2], A[r]])[1] # if A[(l+r)//2] == middelNum: # A[l], A[(l+r)//2] = A[(l+r)//2], A[l] # elif A[r] == middelNum: # A[l], A[r] = A[r], A[l] # ------Way 3------ middelNum = sum([A[l], A[(l+r)//2], A[r]]) - max([A[l], A[(l+r)//2], A[r]]) - min([A[l], A[(l+r)//2], A[r]]) if A[(l+r)//2] == middelNum: A[l], A[(l+r)//2] = A[(l+r)//2], A[l] elif A[r] == middelNum: A[l], A[r] = A[r], A[l] # Partition part p = A[l] i = l + 1 for j in range(l + 1, r + 1): if A[j] < p: A[j], A[i] = A[i], A[j] i += 1 A[l], A[i-1] = A[i-1], A[l] # print("middel:", A) # Recursion call ALeft, cpNumLeft = QuickSort(A, l, i-2) ARight, cpNumRight = QuickSort(A, i, r) ASorted = ALeft + [p] + ARight cpNum = cpNum + cpNumLeft + cpNumRight return ASorted, cpNum def main(): numList = [] with open('data/QuickSort.txt', 'r') as f: while True: line = f.readline().strip() if not line: break numList.append(int(line)) numList, cpNum = QuickSort(numList, 0, len(numList)-1) # print("The sorted number list is:\n", numList) print("The number of comparisons is:\n", cpNum) print("(Using median of three numbers as pivot)") if __name__ == "__main__": main()