Алгоритм медианы трех чисел Печать
Добавил(а) microsin    
int median3(int a, int b, int c)
{
    return (a < b) ? ((b < c) ? b : ((c < a) ? a : c)) : ((a < c) ? a : ((c < b) ? b : c));
}

Это алгоритм поиска медианы трех чисел (median of three). Он находит среднее по значению число среди трех целых чисел, не сортируя их полностью. Алгоритм особенно полезен, когда важна производительность и нужно часто находить медиану трех чисел.

Медиана это значение, которое делит упорядоченный набор данных на две равные части: половина значений меньше или равна медиане, половина — больше или равна.

[Формальное определение]

Для набора чисел, упорядоченных по возрастанию:

- Если количество чисел нечетное (n = 2k+1):
  Медиана = значение под номером (k+1), то есть центральный элемент из упорядоченного набора значений.

- Если количество чисел четное (n = 2k):
  Медиана = среднее арифметическое двух центральных элементов упорядоченного набора значений: (xₖ + xₖ₊₁) / 2

[Примеры]

Нечетное количество:

Набор: 3, 5, 1, 9, 2
Упорядочим: 1, 2, 3, 5, 9
Медиана = 3 (третий элемент)

Четное количество:

Набор: 4, 7, 1, 9, 3, 8
Упорядочим: 1, 3, 4, 7, 8, 9
Медиана = (4 + 7) / 2 = 5.5

[Свойства медианы]

1. Устойчивость к выбросам — в отличие от среднего арифметического, медиана мало чувствительна к экстремальным значениям.

Набор: 1, 2, 3, 4, 100
Среднее = 22
Медиана = 3 (лучше представляет "типичное" значение)

2. Всегда существует — для любого набора данных.

3. Минимизирует сумму абсолютных отклонений:

∑|xᵢ - медиана| → min

[Медианный фильтр в обработке сигналов]

Функция median3 может использоваться для подавления импульсных помех:

Вход:   10, 10, 20, 10, 10
Выход:  10, 10, 10, 10, 10 (выброс 20 отфильтрован)

Это классическое применение — медианный фильтр отлично убирает "битые пиксели", импульсные шумы, выбросы данных, сохраняя при этом перепады сигнала (ступеньки).

Функция median3 возвращает число, которое находится посередине при сортировке трех чисел по возрастанию.

Например:

- median3(5, 2, 8) вернет `5`
- median3(1, 3, 2) вернет `2`
- median3(7, 7, 3) вернет `7`

Разберем логику:

1. Сначала сравниваем `a` и `b`

2. Если `a < b`, то:

   - Если `b < c`, то `b` — медиана
   - Иначе если `c < a`, то `a` — медиана
   - Иначе `c` — медиана

3. Если `a >= b`, то:

   - Если `a < c`, то `a` — медиана
   - Иначе если `c < b`, то `b` — медиана
   - Иначе `c` — медиана

Пример простого использования:

int main() {
    int x = 10, y = 5, z = 7;
    int med = median3(x, y, z);
    printf("Медиана: %d\n", med); // Выведет: Медиана: 7
    return 0;
}

[Типичные сценарии применения]

1. В алгоритмах сортировки (например, для выбора опорного элемента в QuickSort):

int pivot = median3(arr[left], arr[mid], arr[right]);

2. Обработка сигналов - для сглаживания значений (медианный фильтр). Он может сгладить короткий выброс сигнала, длительностью не более одной выборки:

int smooth_value = median3(prev_value, current_value, next_value);

Примечание: median3 относится к фильтрам с конечной импульсной характеристикой (FIR, или КИХ-фильтр).

3. Поиск среднего значения без переполнения:

// Вместо (a + b + c)/3 (может переполнится):
int middle = median3(a, b, c);

Преимущества median3:

- Очень быстрый (без циклов, просто сравнение).
- Компактный код.
- Не требует дополнительной памяти.

Минусы:

- Сложно читать из-за вложенных тернарных операторов.
- Работает только с тремя числами.
- В качестве фильтра может отбрасывать только очень короткие импульсы сигнала.
- Для других типов данных нужно модифицировать.

Более читаемая альтернатива:

int median3(int a, int b, int c) {
    if ((a < = b && b < = c) || (c < = b && b < = a))
        return b;
    if ((b < = a && a < = c) || (c < = a && a < = b))
        return a;
    return c;
}

uint32_t. Алгоритм можно легко переделать на беззнаковые типы, при этом все сравнения будут работать корректно (нет риска неожиданного поведения с отрицательными числами).

Более читаемая версия:

#include < stdint.h>

uint32_t median3(uint32_t a, uint32_t b, uint32_t c) {
    if (a < = b && b < = c) return b;
    if (c < = b && b < = a) return b;
    if (b < = a && a < = c) return a;
    if (c < = a && a < = b) return a;
    return c;
}

С использованием сортировки (максимально понятно):

uint32_t median3(uint32_t a, uint32_t b, uint32_t c) {
    // Сортируем три числа:
    if (a > b) { uint32_t t = a; a = b; b = t; }
    if (b > c) { uint32_t t = b; b = c; c = t; }
    if (a > b) { uint32_t t = a; a = b; b = t; }
    // Теперь a < = b < = c, возвращаем среднее
    return b;
}

Вариант, оптимизированный для микроконтроллеров:

uint32_t median3(uint32_t a, uint32_t b, uint32_t c) {
    // Находим min и max, медиана = сумма - min - max
    uint32_t min_val = a;
    uint32_t max_val = a;

    if (b < min_val) min_val = b;
    if (b > max_val) max_val = b;
    if (c < min_val) min_val = c;
    if (c > max_val) max_val = c;

    return a + b + c - min_val - max_val;
}

Какой вариант выбрать?

Вариант 1 — если нужна максимальная производительность и компактность (сохраняет логику оригинала).
Вариант 2 — если код читают другие разработчики.
Вариант 3 — если важна надежность и простота отладки.
Вариант 4 — если нужно минимизировать количество ветвлений (хорошо для DSP/микроконтроллеров).

Все варианты корректно работают с полным диапазоном uint32_t от 0 до 4294967295.

[Ссылки]

1. Image Filtering, Median Filtering site:cs.auckland.ac.nz.
2. Простой цифровой фильтр EMA.