Объединить алгоритм быстрой сортировки и выбора медианы

Я хочу изменить QuickSort (в Java) так, чтобы каждый раз, когда вызывался Partition, медиана пропорционального массива использовалась как опорная точка.

У меня есть алгоритм выбора медианы в Java, который возвращает k-й наименьший элемент, в данном случае медиану. У меня есть тонны алгоритмов быстрой сортировки в Java, которые все работают сами по себе и сортируют массив. К сожалению, я не могу объединить эти два параметра для достижения вышеизложенного ... Каждый раз, когда я пытаюсь это сделать, я обычно получаю ошибки stackoverflow.

Кто-нибудь может показать мне код, чтобы увидеть, как это можно сделать?

Спасибо

РЕДАКТИРОВАТЬ: Например, это алгоритм выбора медианы, который я пытался использовать.

public int quickSelect(int[] A, int p, int r, int k) {
    if (p==r) return A[p];
    int q = Partition(A,p,r);
    int len = q-p+1;

    if (k == len) return A[q];
    else if (k<len) return Select(A,p,q-1,k);
    else return Select(A,q+1,r,k-len);
}

public int partition(int[]A, int p, int r) {
    int x = A[r];
    int i = p-1;
    for (int j = p; j<=r-1; j++) {
        if (A[j] <= x) {
            i++;
            swap(A,i,j);
        }
    }
    swap(A,i+1,r);
    return i+1;
}

Он работает сам по себе, но когда я пытаюсь вызвать quickSelect через функцию секционирования быстрой сортировки, чтобы вернуть используемую сводку, он не работает. Очевидно, что я делаю что-то не так, но я не знаю что. К сожалению, в Интернете я не нашел ни одного алгоритма, даже в псевдокоде, который бы сочетал медианный выбор с быстрой сортировкой.

 user139730917 мая 2012 г., 13:55
Кто угодно? Я не осознавал, что это было так сложно ... А может, я не совсем понимаю, что я ищу?
 James Montagne16 мая 2012 г., 00:22
Было бы полезно увидеть код, который вы используете. В идеале только соответствующие биты.

Ответы на вопрос(4)

Отметьте это вPARTITION thepivot являетсяA[r].

public int QUICKSORT2(int[] A, int p, int r) {
    if (p<r) {
        int median=Math.floor((p + r) /2) - p + 1
        int q=SELECT(A, p, r, median)
        q=PARTITION2(A, p, r, q)
        QUICKSORT2(A, p, q-1)
        QUICKSORT2(A, q+1, r)
    }
}

public int PARTITION2(int[]A, int p, int r, int q) {
    int temp = A[r];
    A[r]=A[q];
    A[q]=temp;
    return PARTITION(A, p, r)
}

ссылка с псевдокодом.

По ссылке:

В информатике алгоритм выбора - это алгоритм для поиска k-го наименьшего числа в списк

Чтобы найти медиану, которую вы хотите найти, наименьшее число k = floor ((n + 1) / 2) в списке, где n - это размер списка.

 user139730916 мая 2012 г., 01:56
Спасибо, я знаю. Это то, что я использую (я думаю). Я хочу объединить этот алгоритм выбора с быстрой сортировкой, но я не могу этого сделать.

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

Не могли бы вы рассказать, почему вы хотите разделить / развернуть медиану?

 Frantisek Kossuth16 мая 2012 г., 13:17
@ user1397309 Вы не ответили на вопрос - зачем вы это делаете? Знаете ли вы, что повышение эффективности алгоритма (разделение по медиане) путем выполнения чрезмерной работы (поиск медианы) может быть медленнее, чем (например) случайное разделение?
 user139730916 мая 2012 г., 13:51
@ FrantisekKossuth да, я в курсе того, что ты говоришь. Я экспериментирую.
 user139730916 мая 2012 г., 01:37
Я знаю, что могу найти медиану, отсортировав данные, но в этом весь смысл, я хочу найти это, не делая этого. Я хочу, чтобы медиана использовалась как опорная точка каждый раз, когда вызывается функция разбиения быстрой сортировки, потому что медиана - это идеальная опорная точка.

Ты можешь использовать это ...

int Select(int array[],int start, int end,int k){

if(start==end){
    return start;
}

int x=array[end];
int i=start-1;
for(int j=start;j<=end-1;j++){
    if(array[j]<x){
        i++;
        Swap(array+i,array+j);
    }
}
i++;
Swap(array+i,array+end);

if(i==k){
    return i;
}
else if(i>k){
    return Select(array,start,i-1,k);
}
else{
    return Select(array,i+1,end,k);
}

}

Select разделит массив на k-й наименьший элемент в массиве;

Ваш ответ на вопрос