Số lượng tối thiểu so sánh để tìm trung bình của 3 số

Question

Tôi đã triển khai quicksort và tôi muốn đặt trục xoay là số trung vị hoặc ba số. Ba số là phần tử đầu tiên, phần tử ở giữa và phần tử cuối cùng.

Tôi có thể tìm thấy trung vị ở mức thấp hơn không. so sánh?

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

Bạn không thể làm điều đó trong một và bạn chỉ sử dụng hai hoặc ba, vì vậy tôi cho rằng bạn đã có số lượng so sánh tối thiểu.

Answer 2

Thay vì chỉ tính trung bình, bạn cũng có thể đặt chúng vào vị trí. Sau đó, bạn có thể lấy đi chỉ với 3 so sánh tất cả các thời gian, và bạn đã có trục của bạn gần hơn để được tại chỗ.

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

Nếu bạn không ngại bị bẩn một chút với trình biên dịch nội tại, bạn có thể thực hiện với 0 nhánh chính xác.

Cùng một câu hỏi đã được thảo luận trước khi về:
Fastest way of finding the middle value of a triple?

Mặc dù, tôi phải nói thêm rằng trong bối cảnh thực hiện ngây thơ của quicksort, với rất nhiều yếu tố, làm giảm số lượng các chi nhánh khi tìm kiếm trung bình không quá quan trọng bởi vì người dự đoán nhánh sẽ bị nghẹt thở theo cả hai cách khi bạn bắt đầu tung các phần tử xung quanh trục. Các triển khai phức tạp hơn (không phân nhánh trên hoạt động phân vùng và tránh các nguy cơ WAW) sẽ được hưởng lợi từ điều này rất nhiều.

Answer 4

Thực sự là một cách thông minh để cô lập phần tử trung bình từ ba bằng cách sử dụng phân tích cẩn thận 6 hoán vị có thể (thấp, trung bình, cao). Trong 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] 

Một nửa thời gian bạn có hai so sánh nếu không bạn có 3 (trung bình 2,5). Và bạn chỉ trao đổi phần tử trung bình một lần khi cần (2/3 thời gian).

Full python quicksort sử dụng này tại địa chỉ:

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

Answer 5

Bạn có thể viết lên tất cả các hoán vị:

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

Sau đó, chúng tôi muốn tìm ra vị trí của 1. Chúng tôi có thể làm điều này với hai so sánh, nếu so sánh đầu tiên của chúng tôi có thể tách ra một nhóm các vị trí ngang nhau, chẳng hạn như hai dòng đầu tiên.

Vấn đề có vẻ là hai dòng đầu tiên khác nhau trên bất kỳ so sánh nào chúng tôi có sẵn: a<b, a<c, b<c. Do đó chúng ta phải xác định đầy đủ hoán vị, đòi hỏi 3 sự so sánh trong trường hợp xấu nhất.

Answer 6

Nếu mối quan tâm chỉ là so sánh, thì điều này nên được sử dụng.

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

Tôi biết rằng đây là một chủ đề cũ, nhưng tôi đã phải giải quyết chính xác vấn đề này trên một vi điều khiển có rất ít RAM và không có h/w đơn vị nhân (:)).Cuối cùng, tôi thấy các công trình sau hoạt động tốt:

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