Vwwxrf

The goal is to compute the number of comparisons, using the
"median-of-three" pivot rule.

In more detail, you should choose the pivot as follows. 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. As discussed in the first and second parts of
this programming assignment, be sure to implement Partition exactly as
described in the video lectures (including exchanging the pivot
element with the first element just before the main Partition
subroutine).

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.

SUBTLE POINT: A careful analysis would keep track of the comparisons
made in identifying the median of the three candidate elements. You
should NOT do this. That is, as in the previous two problems, you
should simply add m−1 to your running total of comparisons every time
you recurse on a subarray with length m.

Let A[1... n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.

Here is my code:

def quick_sort(A,begin,end):
 count = 0
 if end - begin <= 1:
 return 0
 else:
 #print('Array start:',A[begin:end]) 
 if len(A[begin:end]) %2 == 0:
 mid = len(A[begin:end])//2 - 1
 #print('Mid:',mid)
 pivot = [A[begin] , A[mid], A[end - 1]]
 index = [begin,mid,end-1]
 med_ind = sorted(list(zip(pivot,index)),key = lambda x: x[0])[1][1]
 A[med_ind], A[begin] = A[begin], A[med_ind]
 else:
 mid = len(A[begin:end])//2 
 #print('Mid:',mid)
 pivot = [A[begin] , A[mid], A[end - 1]]
 index = [begin,mid,end-1]
 med_ind = sorted(list(zip(pivot,index)),key = lambda x: x[0])[1][1]
 A[med_ind], A[begin] = A[begin], A[med_ind]

 q = partition(A,begin,end)
 count = end - begin - 1
 #print('Count:',count)
 left = quick_sort(A,begin,q)
 right = quick_sort(A,q+1,end)
 return count + left + right



def partition(A,begin,end):
 pivot = A[begin]

 #print('Begin:',begin)
 #print('End:',end)
 #print('Pivot:',pivot)
 i = begin + 1
 for j in range(begin+1,end):
 if A[j] < pivot:
 A[i], A[j] = A[j], A[i]
 i +=1
 A[i-1], A[begin] = A[begin], A[i-1]
 #print('Array:',A[begin:end])
 #print('-----------------------------------')
 return i - 1

Array for the test:

a = [2, 20, 1, 15, 3, 11, 13, 6, 16, 10, 19, 5, 4, 9, 8, 14, 18, 17, 7, 12]
quick_sort(a,0,len(a))

Here how the results should look like:

#a = [2, 20, 1, 15, 3, 11, 13, 6, 16, 10, 19, 5, 4, 9, 8, 14, 18, 17, 7, 12]# left: 2 right: 12 middle: 10 median: 10 count: 19

# input array: [7, 1, 3, 6, 2, 5, 4, 9, 8] #left: 7 right: 8 middle: 2 median: 7 count: 8

# input array: [4, 1, 3, 6, 2, 5] #left: 4 right: 5 middle: 3 median: 4 count: 5

# input array: [2, 1, 3] #left: 2 right: 3 middle: 1 median: 2 count: 2

# input array: [6, 5]# left: 6 right: 5 middle: 6 median: 6 count: 1

# input array: [9, 8] #left: 9 right: 8 middle: 9 median: 9 count: 1

# input array: [19, 11, 13, 15, 16, 14, 18, 17, 20, 12] #left: 19 right: 12 middle: 16 median: 16 count: 9

# input array: [12, 11, 13, 15, 14]# left: 12 right: 14 middle: 13 median: 13 count: 4

# input array: [12, 11]# left: 12 right: 11 middle: 12 median: 12 count: 1

# input array: [15, 14] #left: 15 right: 14 middle: 15 median: 15 count: 1

# input array: [18, 17, 20, 19] #left: 18 right: 19 middle: 17 median: 18 count: 3

# input array: [20, 19]# left: 20 right: 19 middle: 20 median: 20 count: 1

# sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

# total count: 55

Based on the test array, my sorting algorithm works correct, but the number of inversions is incorrect(I get 66 instead of 55). Can you help me to find my mistake?