Минимальный номер. сравнений, чтобы найти медиану из 3 чисел

Я реализовал quicksort, и я хотел установить опорную точку в качестве медианного или трех чисел. Три числа - это первый элемент, средний элемент и последний элемент.

Могу ли я найти медиана меньше, чем нет. сравнений?

median(int a[], int p, int r)
{
    int m = (p+r)/2;
    if(a[p] < a[m])
    {
        if(a[p] >= a[r])
            return a[p];
        else if(a[m] < a[r])
            return a[m];
    }
    else
    {
        if(a[p] < a[r])
            return a[p];
        else if(a[m] >= a[r])
            return a[m];
    }
    return a[r];
}

Ответ 1

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

Ответ 2

Если проблема связана только с сравнениями, то это необходимо использовать.

int getMedian(int a, int b , int c) {
    int x = a-b;
    int y = b-c;
    int z = a-c;
    if(x*y > 0) return b;
    if(x*z > 0) return c;
    return a;
}

Ответ 3

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

T median(T a[], int low, int high)
{
    int middle = ( low + high ) / 2;
    if( a[ middle ].compareTo( a[ low ] ) < 0 )
        swap( a, low, middle );
    if( a[ high ].compareTo( a[ low ] ) < 0 )
        swap( a, low, high );
    if( a[ high ].compareTo( a[ middle ] ) < 0 )
        swap( a, middle, high );

    return a[middle];
}

Ответ 4

Если вы не боитесь, что ваши руки немного грязны с внутренними функциями компилятора, вы можете сделать это ровно с 0 ветвями.

Тот же вопрос обсуждался ранее:
Самый быстрый способ найти среднее значение тройки?

Хотя, я должен добавить, что в контексте наивной реализации quicksort с большим количеством элементов сокращение количества ветвей при поиске медианы не так важно, потому что предсказатель ветвления будет задыхаться в любом случае, когда вы будете начать бросать элементы вокруг стержня. Более сложные реализации (которые не ветвятся на операцию раздела и не избегают опасностей WAW) выиграют от этого значительно.

Ответ 5

Существует действительно умный способ изолировать медианный элемент из трех, используя тщательный анализ 6 возможных перестановок (низкого, среднего, высокого). В python:

def med(a, start, mid, last):
    # put the median of a[start], a[mid], a[last] in the a[start] position
    SM = a[start] < a[mid]
    SL = a[start] < a[last]
    if SM != SL:
        return
    ML = a[mid] < a[last]
    m = mid if SM == ML else last
    a[start], a[m] = a[m], a[start]

Половина времени, когда у вас есть два сравнения, в противном случае у вас есть 3 (avg 2.5). И вы только обмениваете срединный элемент один раз, когда это необходимо (2/3 времени).

Полная быстрая сортировка python с помощью этого:

https://github.com/mckoss/labs/blob/master/qs.py

Ответ 6

int32_t FindMedian(const int n1, const int n2, const int n3) {
    auto _min = min(n1, min(n2, n3));
    auto _max = max(n1, max(n2, n3));
    return (n1 + n2 + n3) - _min - _max;
}

Ответ 7

Вы можете написать все перестановки:

Затем мы хотим найти положение 1. Мы могли бы сделать это с помощью двух сравнений, если бы наше первое сравнение могло разделить группу равных позиций, таких как первые две строки.

Проблема заключается в том, что первые две строки различаются при любом сравнении, которое у нас имеется: a<b, a<c, b<c. Следовательно, мы должны полностью идентифицировать перестановку, которая требует 3 сравнений в худшем случае.

Ответ 8

Я знаю, что это старый поток, но мне пришлось решить именно эту проблему на микроконтроллере, который имеет очень мало оперативной памяти и не имеет единицы умножения h/w (:)). В конце концов я нашел следующие работы хорошо:

static char medianIndex[] = { 1, 1, 2, 0, 0, 2, 1, 1 };

signed short getMedian(const signed short num[])
{
    return num[medianIndex[(num[0] > num[1]) << 2 | (num[1] > num[2]) << 1 | (num[0] > num[2])]];
}