快速算法的实现进行排序非常小名单 [英] Fast algorithm implementation to sort very small list

问题描述

这是我以前碰到了很长一段时间的问题。 我想我可能会问你对你的想法。 假设我有一个数字非常小的列表（整数），4个或8个元素，需要进行排序，快速。 这将是最好的方法/算法？

This is the problem I ran into long time ago. I thought I may ask your for your ideas. assume I have very small list of numbers (integers), 4 or 8 elements, that need to be sorted, fast. what would be the best approach/algorithm?

我的方法是使用最大/最小功能（10用于4号进行排序，没有分支，IIRC）。

my approach was to use the max/min functions (10 functions to sort 4 numbers, no branches, iirc).

// s(i,j) == max(i,j), min(i,j)
i,j = s(i,j)
k,l = s(k,l)
i,k = s(i,k) // i on top
j,l = s(j,l) // l on bottom
j,k = s(j,k)

我想我的问题涉及更多的实现，而不是算法的类型。

I guess my question pertains more to implementation, rather than type of algorithm.

在这一点上变得有些依赖于硬件，所以让我们假设有SSE3指令集的英特尔64位处理器。

At this point it becomes somewhat hardware dependent , so let us assume Intel 64-bit processor with SSE3 .

感谢

推荐答案

对于这样的小数组，你应该看看排序网络。正如你可以在该网页上看到，插入排序可以pssed作为一个排序网络EX $ P $。但是，如果你知道数组的大小事前，你可以制定一个最佳的网络。看看本网站，可以做帮助您找到最佳的排序网络的阵列的给定尺寸（虽然最佳只保证最多16个的大小，我相信）。比较器甚至分组在操作可以并行进行。比较器在本质上是相同的S（X，Y）功能，但如果你真的希望这是快，你不应该使用的最小和最大，因为那时你正在做两次比较是必要的数量。

For small arrays like this, you should probably look into sorting networks. As you can see on that page, insertion sort can be expressed as a sorting network. However, if you know the size of the array beforehand, you can devise an optimal network. Take a look at this site that can do help you to find optimal sorting networks for a given size of array (though optimal is only guaranteed up to a size of 16 I believe). The comparators are even grouped together in operations that can be done in parallel. The comparators are essentially the same as your s(x,y) function though if you really want this to be fast, you shouldn't be using min and max because then you're doing twice the number of comparisons that are necessary.

如果你需要这个排序算法，工作在广泛的尺寸，那么你或许应该只是去用插入排序为其他建议。

If you need this sorting algorithm to work on a wide range of sizes, then you should probably just go with insertion sort as others have suggested.

这篇关于快速算法的实现进行排序非常小名单的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！