Minimalne nie. porównań, aby znaleźć medianę 3 liczb

Question

Wdrażałem quicksort i chciałem ustawić przestawność na medianę lub trzy liczby. Te trzy liczby to pierwszy element, środkowy element i ostatni element.

Czy mogę znaleźć medianę w mniejszej ilości? porównań?

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

Answer 1

Nie możesz tego zrobić w jednym, a używasz tylko dwóch lub trzech, więc powiedziałbym, że masz już minimalną liczbę porównań.

Answer 2

Zamiast tylko obliczać medianę, równie dobrze można je zastosować. Wtedy możesz uciec tylko trzema porównaniami przez cały czas, a twój pivot jest bliżej, aby być na miejscu.

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

Answer 3

Jeśli nie boisz się zabrudzić sobie rąk kompilatorami, możesz zrobić to z dokładnie 0 gałęziami.

To samo pytanie zostało omówione wcześniej na:
Fastest way of finding the middle value of a triple?

Chociaż, muszę dodać, że w kontekście naiwnej realizacji quicksort, z dużą ilością elementów, zmniejszenie ilości oddziałów kiedy znalezienie medianę nie jest tak ważny, ponieważ predykator gałęzi dusi się tak czy inaczej, gdy zaczniesz rzucać elementami wokół osi obrotu. Bardziej zaawansowane implementacje (które nie rozgałęziają się na operacji partycji i unikają zagrożeń związanych z WAW) będą z tego czerpać wiele korzyści.

Answer 4

Istnieje rzeczywiście sprytny sposób na odizolowanie elementu medianowego od trzech przy użyciu dokładnej analizy 6 możliwych permutacji (niskiej, medianowej, wysokiej). W pytonie:

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] 

Połowa razy masz dwa porównania, w przeciwnym razie masz 3 (średnio 2,5). A ty wymieniasz element mediany tylko raz w razie potrzeby (2/3 czasu).

Pełna pyton quicksort przy użyciu tego:

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

Answer 5

można napisać wszystkie permutacje:

1 0 2 
    1 2 0 
    0 1 2 
    2 1 0 
    0 2 1 
    2 0 1 

Następnie chcemy znaleźć pozycję 1. Moglibyśmy to zrobić za pomocą dwóch porównań, gdyby nasze pierwsze porównanie mogło podzielić grupę równych pozycji, takich jak pierwsze dwie linie.

Problem wydaje się taki, że pierwsze dwie linie różnią się w zależności od dostępnych porównań: a<b, a<c, b<c. Dlatego musimy w pełni zidentyfikować permutację, która wymaga 3 porównań w najgorszym przypadku.

Answer 6

Jeśli problem dotyczy tylko porównań, należy go użyć.

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

Answer 7

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

Answer 8

wiem, że jest to stary wątek, ale musiałem dokładnie rozwiązać ten problem na mikrokontrolera, który ma bardzo mało pamięci RAM i nie ma H/W urządzeniu mnożenia (:)).Na końcu znalazłem następujące dobrze:

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