短期数组排序最佳功能 [英] Best Sort function for short arrays

问题描述

我的工作是操纵图片的算法。
基本上我将实施扩散（每个像素将得到的8个周围像素+它自己的值的中间值）。

I'm working on an algorithm that manipulates pictures. Basically I will implement a diffusion (each pixel will get the median value of the 8 surrounding pixels + its own value).

我会做什么是创造的9整数的阵列的价值，对数组进行排序，并获得数组中值[4]。

what I will do is to create a array of 9 integers with the value, sort the array and get the median value at array[4].

我还是不知道要用什么问题，什么是使用相对较小的阵列最好的排序功能？分拣功能将大致被称为x次，x为像素的数量。

I still don't know what to use for the problem, what is the best sorting function to use for relatively small arrays? The sorting function will roughly be called x times, x being the number of pixels.

堆排序似乎有点矫枉过正。快速排序将不执行好。我不想要实现非常复杂的事情。

Heapsort seems a bit overkill. Quicksort will not perform that well. And I don't want to implement really complex things.

你们觉得呢？

推荐答案

如果你需要的是中位数，有没有必要做任何排序在所有！ （对于长阵列，请参阅http://en.wikipedia.org/wiki/Selection_algorithm为O（n）的算法;当然我们在这里只讨论短阵）

If all you need is the median, there's no need to do any sorting at all! (For long arrays, see http://en.wikipedia.org/wiki/Selection_algorithm for an O(n) algorithm; of course we're talking only about short arrays here).

有关9号位，一点谷歌搜索显示的文章的快速搜索中位数：一个ANSI C实现的通过N. Devillard，它指向相应的在XC4000E FPGA的实施中值滤波的由JL史密斯，它提供了这种不言自明的排序网络的使用以获得中值19比较：

For median of 9 numbers, a little googling reveals the article Fast median search: an ANSI C implementation by N. Devillard, which points to the article Implementing median filters in XC4000E FPGAs by J. L. Smith, which provides this self-explanatory "sorting network" to get the median using 19 comparisons:

在C方面：

typedef int T;

void sort2(T* a, T* b);
void sort3(T* a, T* b, T* c);
T min3(T a, T b, T c);
T max3(T a, T b, T c);

T median9(T p1, T p2, T p3, T p4, T p5, T p6, T p7, T p8, T p9)
{
    sort3(&p1, &p2, &p3);
    sort3(&p4, &p5, &p6);
    sort3(&p7, &p8, &p9);

    p7 = max3(p1, p4, p7);
    p3 = min3(p3, p6, p9);

    sort3(&p2, &p5, &p8);
    sort3(&p3, &p5, &p7);

    return p5;
}

void sort2(T* a, T* b)
{
    if (*a > *b)
    {
        T tmp = *b;
        *b = *a;
        *a = tmp;
    }
}

void sort3(T* a, T* b, T* c)
{
    sort2(b, c);
    sort2(a, b);
    sort2(b, c);
}

T min3(T a, T b, T c)
{
    if (a < b)
        return a < c ? a : c;
    else
        return b < c ? b : c;
}

T max3(T a, T b, T c)
{
    if (a > b)
        return a > c ? a : c;
    else
        return b > c ? b : c;
}

---

编辑：这个文件还包含code获取的3位数，5，6，7，9和25号。

---

this file also contains the code for getting the median of 3, 5, 6, 7, 9 and 25 numbers.

#define PIX_SORT(a,b) { if ((a)>(b)) PIX_SWAP((a),(b)); }
#define PIX_SWAP(a,b) { pixelvalue temp=(a);(a)=(b);(b)=temp; }

/*----------------------------------------------------------------------------
   Function :   opt_med9()
   In       :   pointer to an array of 9 pixelvalues
   Out      :   a pixelvalue
   Job      :   optimized search of the median of 9 pixelvalues
   Notice   :   in theory, cannot go faster without assumptions on the
                signal.
                Formula from:
                XILINX XCELL magazine, vol. 23 by John L. Smith

                The input array is modified in the process
                The result array is guaranteed to contain the median
                value
                in middle position, but other elements are NOT sorted.
 ---------------------------------------------------------------------------*/

pixelvalue opt_med9(pixelvalue * p)
{
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;
    PIX_SORT(p[0], p[1]) ; PIX_SORT(p[3], p[4]) ; PIX_SORT(p[6], p[7]) ;
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;
    PIX_SORT(p[0], p[3]) ; PIX_SORT(p[5], p[8]) ; PIX_SORT(p[4], p[7]) ;
    PIX_SORT(p[3], p[6]) ; PIX_SORT(p[1], p[4]) ; PIX_SORT(p[2], p[5]) ;
    PIX_SORT(p[4], p[7]) ; PIX_SORT(p[4], p[2]) ; PIX_SORT(p[6], p[4]) ;
    PIX_SORT(p[4], p[2]) ; return(p[4]) ;
}

这篇关于短期数组排序最佳功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！