I am using Quick sort in python to sort a list of numbers.This has to be done using the median as the pivot. How am i finding the median ? It is the second largest no.(out of a list of 3 numbers which are first,middle and last element of the original list)
If the list is of length even(2j),the middle no will be the jth element.
If the list is of length odd(say 5),the middle no. will be the 3rd element
My code works successfully.However, the total no. of comparisons made are incorrect(found using the variable tot_comparisons)
What am i doing?
1.Finding the pivot (which is the median of first,middle and last element)
I do not need the code.I have my posted below which is working successfully(except for the total no. of comparisons part). I only need to know the mistake in my code
def swap(A,i,k):
temp=A[i]
print "temp is "
print temp
A[i]=A[k]
A[k]=temp
def find_median(input_list,start,end):
#print 'input list is'
#print input_list
temp_list1=[]
temp_list1.append(input_list[start])
if len(input_list) % 2 ==0:
middle_element_index=(len(input_list) / 2)-1
middle_element=input_list[middle_element_index]
temp_list1.append(middle_element)
else:
middle_element_index=len(input_list)/2
middle_element=input_list[middle_element_index]
temp_list1.append(middle_element)
temp_list1.append(input_list[end])
temp_list1.sort()
#print temp_list1
if len(temp_list1)==3:
print temp_list1[1]
return temp_list1[1]
elif len(temp_list1)==2:
print temp_list1[1]
return temp_list1[1]
else:
print temp_list1[0]
return temp_list1[0]
def partition(A,start,end,median_index):
swap(A,start,median_index)
pivot=A[start]
pivot_index=start + 1
for i in range(start+1,end+1):
if A[i] < pivot:
swap(A,i,pivot_index)
pivot_index+=1
swap(A,pivot_index-1,start)
return pivot_index-1
def quicksort(A,start,end):
global tot_comparisons
if start<end:
median=find_median(A, start, end)
median_index=A.index(median)
pivot_index=partition(A,start,end,median_index)
tot_comparisons+=end-start
print "pivot_index"
print pivot_index
print "ENDS"
quicksort(A, start,pivot_index-1)
#tot_comparisons+=end-pivot_index
#quicksort(A, pivot_index, end)
quicksort(A, pivot_index+1, end)
#A=[45,21,23,4,65]
#A=[21,23,19,22,1,3,7,88,110]
#A=[1,22,3,4,66,7]
#A=[1, 3, 7, 19, 21, 22, 23, 88, 110]
#A=[7,2,1,6,8,5,3,4]
temp_list=[]
f=open('temp_list.txt','r')
for line in f:
temp_list.append(int(line.strip()))
f.close()
print 'list is '
#print temp_list
print 'list ends'
tot_comparisons=0
#quicksort(A, 0, 7)
quicksort(temp_list, 0, 9999)
#quicksort(temp_list, 0, len(temp_list))
print 'hhh'
print temp_list
print tot_comparisons
#print A
I believe I've found the critical problem: find_median grabs the left and right elements of the given list, but then adds the middle element of the original list. Thus, if you're looking to sort list positions 5:7, you grab elements 5, 7, and 3. The last should be element 6. This is likely to force your through extra sorting work.
The middle element has index
(start+end) / 2
(integer division; it looks like you're using Python 2.? ). You don't need separate cases for odd and even lengths. The position depends on the given list, not the original length, len(input_list).
Just make a list of the three needed elements, sort it, and return the middle element. Since there's only one temp list, which is obviously a list, let's shorten that name.
temp = [
input_list[start],
input_list[end],
input_list[(start+end) / 2]
]
temp.sort()
return temp[1]
You can reduce this to a one-command function. I'll rename input list as simply in to help readability.
return sorted( [ in[start], in[end], in[(start+end) / 2] ] )[1]