用最少的元素比较对5个元素进行排序 [英] Sorting 5 elements with minimum element comparison
问题描述
我必须使用最少的元素间比较数,在python中对5个元素的列表进行排序的执行计划建模.除此之外,复杂性无关紧要.
I have to model the execution plan of sorting a list of 5 elements, in python, using the minimum number of comparisons between elements. Other than that, the complexity is irrelevant.
结果是成对的列表,表示在另一时间对列表进行排序所需的比较.
The result is a list of pairs representing the comparisons needed to sort the list at another time.
我知道有一种算法可以在7个比较中做到这一点(在元素之间,总是,而不是在复杂度方面),但是我找不到可读的(对我来说)版本.
I know there's an algorithm that does this in 7 comparisons (between elements, always, not complexity-wise), but I can't find a readable (for me) version.
如何对7个比较中的5个元素进行排序,并为排序建立一个执行计划"?
How can I sort the 5 elements in 7 comparisons, and build an "execution plan" for the sort?
PD:不是作业.
推荐答案
这符合您对5 elements in 7 comparisons
排序的描述:
This fits your description of sorting 5 elements in 7 comparisons
:
import random
n=5
ran=[int(n*random.random()) for i in xrange(n)]
print ran
def selection_sort(li):
l=li[:]
sl=[]
i=1
while len(l):
lowest=l[0]
for x in l:
if x<lowest:
lowest=x
sl.append(lowest)
l.remove(lowest)
print i
i+=1
return sl
print selection_sort(ran)
这使用了选择排序,它不是最有效的方法,但使用的比较很少.
This uses a Selection Sort which is NOT the most efficient, but does use very few comparisons.
这可以简化为:
def ss(li):
l=li[:]
sl=[]
while len(l):
sl.append(l.pop(l.index(min(l))))
return sl
在任何一种情况下,都将打印以下内容:
In either case, prints something like this:
[0, 2, 1, 1, 4]
1
2
3
4
5
[0, 1, 1, 2, 4]
Perl有一个名为 Algorithm :: Networksort 的可爱模块,可让您玩用这些. Knuth引用了Bose-Nelson算法的几个比较器,您可以在此处看到它.
Perl has a lovely module called Algorithm::Networksort that allows you to play with these. The Bose-Nelson algorithm is cited by Knuth for few comparators and you can see it here.
修改
插入排序也可以很好地工作:
def InsertionSort(l):
""" sorts l in place using an insertion sort """
for j in range(1, len(l)):
key = l[j]
i = j - 1
while (i >=0) and (l[i] > key):
l[i+1] = l[i]
i = i - 1
l[i+1] = key
这篇关于用最少的元素比较对5个元素进行排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!