Нахождение медианы без сортировки массива

Question

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

Я знаю несколько алгоритмов, таких как minHeap и Quick Select, но я стараюсь сделать вещи простыми, как бы человек невооруженным глазом просто подсчитывал большие и меньшие числа. До сих пор я реализовал функцию ниже, но проблема возникает, когда у меня есть повторяющиеся записи в массиве, а также с четной и нечетной длиной массива.

Я новичок в программировании на C и должен понимать, что происходит не так. Ниже приведен код, я написал функцию, которая возвращает случайный массив переменной длины для тестирования этой функции.

int med(int count, int *array)
{
int i, j, median = -1, smaller = 0, larger = 0;

for(i = 0; i < count; i++)
{
    for(j = 0; j < count; j++)
    {
        //larger++

        if(array[i] < array[j] && i!=j)
        {
            larger++;
        }
        //Smaller++
        if(array[i] >= array[j] && i!=j)
        {
            smaller++;
        }
    }
    printf("\nFor pivot: %d", array[i]);
    if(larger == smaller)
    {
        printf("\n Smaller: %d", smaller);
        printf(" Larger: %d", larger);
        median = array[i];
        break;
    }
    else
    {
        printf("\n Smaller: %d", smaller);
        printf(" Larger: %d", larger);

        larger = 0;
        smaller = 0;
    }
}
return median;
}

В некоторых случаях, таких как {3,5,0,2,3}, моя функция возвращает -1, но фактический результат должен быть равен 3.

EDIT Изначально я начинал со строго большего или меньшего, но это условие (больше == меньшее) никогда не срабатывало, когда у меня были повторяющиеся записи, поэтому я считал равные элементы меньшими. Я с трудом справляюсь с равенством

Answer 1

B. Шефтер нашла для вас ошибку. Однако я все еще хочу ответить на этот вопрос.

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

Делайте это только в том случае, если вы можете сделать это быстрее, чем O (nlog n), потому что это временная сложность qsort. Я бы порекомендовал попробовать алгоритм медианы медиан. Вы можете прочитать об этом здесь и вот код с этого сайта, но с удаленными комментариями:

int select(int *a, int s, int e, int k){
    if(e-s+1 <= 5){
        sort(a+s, a+e);
        return s+k-1;
    }

    for(int i=0; i<(e+1)/5; i++){
        int left = 5*i;
        int right = left + 4;
        if(right > e) right = e;
        int median = select(a, 5*i, 5*i+4, 3);
        swap(a[median], a[i]);
    }

    return select(a, 0, (e+1)/5, (e+1)/10);
}

Я знаю несколько алгоритмов, таких как minHeap и Quick Select, но я стараюсь упростить процесс, как невооруженным глазом, чтобы просто считать большие и меньшие числа.

Хотя хорошо, когда все упрощается, убедитесь, что это то, что вы делаете. Стандартная библиотека C имеет встроенную функцию быстрой сортировки. Если вы используете его, код может выглядеть так:

int int_cmp(const void *a, const void *b) 
{ 
    const int ia = *(const int *)a; 
    const int ib = *(const int *)b;

    if (ia > ib) return 1;
    else if(ia < ib) return -1;
    else return 0;
}

int med(int count, int *array)
{
    int tmp[count];

    memcpy(tmp, array, count * sizeof(*array));

    qsort(tmp, count, sizeof(tmp[0]), int_cmp);

    return tmp[count/2];
}

Это быстрее и проще для чтения. Ваш код O (n²), а это O (nlog n).

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

Вот пример того, как вы можете добиться того, чего хотите, довольно читабельным способом, сохраняя при этом свою идею. Я начну с добавления подзадачи, которая вместо «что является медианой в массиве» - это «х медиана массива». И затем мы задаем этот вопрос для каждого элемента в массиве, пока не найдем медиану.

int is_median(int x, int *array, int count) {
    int l=0, h=0;

    for(int i=0; i<count; i++) {
        if(array[i] < x) l++;
        else if(array[i] > x) h++;
    }

    if(h == l) return 1; // This is always a sufficient condition
    // Here you need to decide what to do. Just the above is not enough
    // for your purposes.
    else if(<condition>) return 1; 

    else return 0;
}

int med(int count, int *array) {
    for(int i = 0; i < count; i++) {
        if(is_median(array[i], array, count)) return array[i];
    }
    return 0; // This line should never be executed. It't only here
              // to suppress a warning.
}

Answer 2

Значение -1 исходит из следующего: Ваши коды инициализируют median до -1, и оно никогда не изменится, если larger == smaller. В случаях, когда это никогда не происходит после итерации по всему массиву, код возвращает -1.

Я думаю, что концептуальная ошибка в том, что вы произвольно решили увеличить smaller, когда два числа равны. Если вы пройдете по своему коду, вы поймете, почему вы получаете -1 в приведенном вами примере: в итоге вы получите larger=1 (5) и smaller=3 (0, 2 и 3). Таким образом, поскольку larger не равно smaller, median не равно 3 и остается -1.

Вот что не так. Как справиться с равенством, чтобы исправить концептуальную ошибку, зависит только от вас!