短い配列のベストソート関数

Question

私は画像を操作するアルゴリズムを開発中です。 基本的には拡散を実装します（各ピクセルは周囲の8ピクセルの中央値+独自の値を取得します）。

私が行うことは、値を持つ9個の整数の配列を作成し、配列をソートし、配列[4]で中央値を取得することです。

私はまだ何を問題に使用するのか分からない、比較的小さな配列に使用するのに最適な並べ替え関数は何ですか？ソート関数はおおまかにx回と呼ばれ、xはピクセル数です。

Heapsortは少し残虐であるようです。 Quicksortはそれをうまく実行しません。そして、私は本当に複雑なものを実装したくありません。

あなたはどう思いますか？

Answer 1

必要なのは中央値であれば、並べ替えを一切行う必要はありません。 （長い配列については、O（n）アルゴリズムについてはhttp://en.wikipedia.org/wiki/Selection_algorithmを参照してください;もちろん、ここでは短い配列についてのみ説明しています）。 9つの数字の中央値

、少しグーグルでは「ネットワークをソートする」この自己説明を提供JLスミスによってXC4000EのFPGAにおける中央値フィルタを実装する記事を指すN. Devillard、で記事Fast median search: an ANSI C implementationを明らかに

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; 
} 

---

：Cの面では

：19回の比較を使用して中央値を取得します

編集：this fileには、3,5,6,7,9,25の中央値を取得するためのコードも含まれています。

#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]) ; 
} 

Answer 2

cライブラリの "標準" qsortは、通常、非常に最適化されています。しばしば、小さなサブアレイのためのクイックソート+挿入ソートです（ベース配列を非常に細かく分割する場合）。たとえば、このバージョンのread the commentsをgnu cライブラリから取り出した場合

Answer 3

理論的に言えば、あなたはselection problemの特定の場合である中央値を、見つけたいです。これは、の線形時に実行されます。

しかしこれは理論上のものです。実際には、私は "パーティションベースの一般的な選択アルゴリズム"（記事で言及）を使用したいと思います。これは平均して線形時間で動作しますが、実用上シンプルで高速です。

template <typename T> 
T* SubDivide(T* pB, T* pE) 
{ 
    ASSERT(pB < pE); 

    T* pPivot = --pE; 
    const T pivot = *pPivot; 

    while (pB < pE) 
    { 
     if (*pB > pivot) 
     { 
      --pE; 
      std::swap(*pB, *pE); 
     } else 
      ++pB; 
    } 

    std::swap(*pE, *pPivot); 
    return pE; 
} 

template <typename T> 
void SelectElement(T* pB, T* pE, size_t k) 
{ 
    ASSERT((pE > pB) && (k < unsigned(pE - pB))); 

    while (true) 
    { 
     T* pPivot = SubDivide(pB, pE); 
     size_t n = pPivot - pB; 

     if (n == k) 
      break; 

     if (n > k) 
      pE = pPivot; 
     else 
     { 
      pB = pPivot + 1; 
      k -= (n + 1); 
     } 
    } 
} 

// Usage example 
int pArr[9] = { /* fill with values*/ }; 

// Select the 4th element (which is a median) 
SelectElement(pArr, pArr + 9, 4); 

// pArr[4] now holds the median value