Migliore funzione di ordinamento per array brevi

Question

Sto lavorando su un algoritmo che manipola le immagini. Fondamentalmente implementerò una diffusione (ogni pixel otterrà il valore mediano degli 8 pixel circostanti + il proprio valore).

quello che farò è creare una matrice di 9 numeri interi con il valore, ordinare l'array e ottenere il valore mediano dell'array [4].

Ancora non so cosa usare per il problema, qual è la migliore funzione di ordinamento da utilizzare per array relativamente piccoli? La funzione di ordinamento sarà chiamata approssimativamente x volte, x è il numero di pixel.

Heapsort sembra un po 'eccessivo. Quicksort non funzionerà così bene. E non voglio implementare cose davvero complesse.

Cosa ne pensate?

Answer 1

Se tutto ciò che serve è la mediana, non c'è bisogno di fare alcun ordinamento! (Per i lunghi array, vedere http://en.wikipedia.org/wiki/Selection_algorithm per un algoritmo O (n), ovviamente stiamo parlando solo di array brevi qui).

Per mediano 9 numeri, un po 'googling rivela l'articolo Fast median search: an ANSI C implementation da N. Devillard, che indica l'articolo Implementazione filtri mediani in XC4000E FPGA da JL Smith, che fornisce questa "rete sorting" autoesplicativi ottenere la mediana con 19 confronti:

In termini di 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; 
} 

---

Modifica: this file contiene anche il codice per ottenere la mediana di 3, 5, 6, 7, 9 e 25 numeri.

#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

Sapete che lo "standard" qsort della libreria c è normalmente abbastanza ottimizzato? Spesso è quicksort + insertion sort per piccoli sotto-array (quando si suddivide molto l'array di base). Ad esempio read the comments di questa versione presa dalla libreria gnu c

Answer 3

Teoricamente parlando, si vuole trovare una mediana, che è un caso particolare di un selection problem. Può essere fatto in tempo lineare.

Ma questo è in teoria. Praticamente userei "algoritmo di selezione generale basato sulla partizione" (menzionato nell'articolo). Funziona in tempo lineare in media, in più è praticamente semplice e veloce.

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