Функция Best Sort для коротких массивов

Question

Я работаю над алгоритмом, который манипулирует картинками.По сути, я буду реализовывать диффузию (каждый пиксель получит среднее значение 8 окружающих пикселей + свое собственное значение).

что я сделаю, это создам массив из 9 целых чисел со значением, отсортирую массив и получу среднее значение в массиве [4].используйте для этой проблемы, какую функцию сортировки лучше всего использовать для относительно небольших массивов?Функция сортировки будет приблизительно вызвана x раз, x это количество пикселей.

Heapsort кажется немного излишним.Быстрая сортировка не будет работать так хорошо.И я не хочу реализовывать действительно сложные вещи.

Что вы, ребята, думаете?

Answer 1

Если все, что вам нужно, это медиана, то нет никакой необходимости делать сортировку вообще! (Для длинных массивов см. http://en.wikipedia.org/wiki/Selection_algorithm для алгоритма O (n); конечно, здесь мы говорим только о коротких массивах).

Для медианы из 9 чисел, небольшой поиск в Google показывает статью Быстрый поиск по медиане: реализация ANSI C от N. Devillard, которая указывает на статью Реализация медианы фильтры в ПЛИС XC4000E от JL Smith, которые обеспечивают эту самоочевидную "сеть сортировки", чтобы получить медиану, используя 19 сравнений:

В пересчете на 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;
}

---

Редактировать: этот файл также содержит код для получения медианы из 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

Вы знаете, что "стандартный" qsort библиотеки c обычно довольно оптимизирован? Часто это быстрая сортировка + сортировка вставки для небольших подмассивов (когда вы очень сильно подразделяете базовый массив). Например, прочитайте комментарии этой версии, взятые из библиотеки gnu c

Answer 3

Теоретически, вы хотите найти медиану, которая является частным случаем проблемы выбора .Это может быть сделано за линейное время.

Но это в теории.Практически я бы использовал «общий алгоритм выбора на основе разделов» (упомянутый в статье).В среднем он работает за линейное время, плюс он практически простой и быстрый.

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