使用中位数作为枢轴工作的快速排序(但显示不正确的比较计数)
Quick sort using median as pivot working (but shows incorrect count for comaprisons)
我在 python 中使用快速排序来对 numbers.This 的列表进行排序,必须使用中位数作为基准来完成。
我如何找到中位数?
它是第二大的数字。(在原始列表的第一个,中间和最后一个元素的3个数字列表中)
如果列表的长度为even(2j),中间的no就是第j个元素
如果列表的长度为奇数(比如5),中间的编号。将是第三个元素
我的代码有效successfully.However,总号。的比较不正确(使用变量 tot_comparisons)
我在做什么?
1.Finding 主元(第一个、中间和最后一个元素的中位数)
- 用第一个元素替换上面找到的主元(因为我已经准备好快速排序的代码,第一个元素作为主元)
我不需要code.I下面的帖子,它运行成功(除了比较部分的总数)。我只需要知道我代码中的错误
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
我相信我已经找到关键问题:find_median 抓取给定列表的左右元素,然后添加 原始列表。因此,如果您要对列表位置 5:7 进行排序,您可以获取元素 5、7 和 3。最后一个应该是元素 6。这可能会迫使您完成额外的排序工作。
中间元素有索引
(start+end) / 2
(整数除法;看起来您正在使用 Python 2.?)。对于奇数和偶数长度,您不需要单独的案例。位置取决于给定的列表,不是原来的长度,len(input_list).
只需列出所需的三个元素,对其进行排序,然后 return 中间元素。由于只有一个临时列表,这显然是一个列表,让我们缩短该名称。
temp = [
input_list[start],
input_list[end],
input_list[(start+end) / 2]
]
temp.sort()
return temp[1]
您可以将其简化为一个命令函数。我将 input list 重命名为 in 以提高可读性。
return sorted( [ in[start], in[end], in[(start+end) / 2] ] )[1]
我在 python 中使用快速排序来对 numbers.This 的列表进行排序,必须使用中位数作为基准来完成。 我如何找到中位数? 它是第二大的数字。(在原始列表的第一个,中间和最后一个元素的3个数字列表中)
如果列表的长度为even(2j),中间的no就是第j个元素
如果列表的长度为奇数(比如5),中间的编号。将是第三个元素
我的代码有效successfully.However,总号。的比较不正确(使用变量 tot_comparisons)
我在做什么?
1.Finding 主元(第一个、中间和最后一个元素的中位数)
- 用第一个元素替换上面找到的主元(因为我已经准备好快速排序的代码,第一个元素作为主元)
我不需要code.I下面的帖子,它运行成功(除了比较部分的总数)。我只需要知道我代码中的错误
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
我相信我已经找到关键问题:find_median 抓取给定列表的左右元素,然后添加 原始列表。因此,如果您要对列表位置 5:7 进行排序,您可以获取元素 5、7 和 3。最后一个应该是元素 6。这可能会迫使您完成额外的排序工作。
中间元素有索引
(start+end) / 2
(整数除法;看起来您正在使用 Python 2.?)。对于奇数和偶数长度,您不需要单独的案例。位置取决于给定的列表,不是原来的长度,len(input_list).
只需列出所需的三个元素,对其进行排序,然后 return 中间元素。由于只有一个临时列表,这显然是一个列表,让我们缩短该名称。
temp = [
input_list[start],
input_list[end],
input_list[(start+end) / 2]
]
temp.sort()
return temp[1]
您可以将其简化为一个命令函数。我将 input list 重命名为 in 以提高可读性。
return sorted( [ in[start], in[end], in[(start+end) / 2] ] )[1]