Вот псевдокод для реализации медианы путем деления массива на 5 групп

select(int A[],int first, int last, int i) {
    n = last - first + 1; /* n is the number elements to select from */
    if (i > n) {return ERROR;} /* there is no ith smallest element */
    if( n < = 100 ) {
        /********************* For Small n *********************/
        Run selection on A[first..last] taking at most n(n-1)/2 < 50n comparisons;
        swap A[first+i-1] with A[first] /* put ith smallest in A[first] */
    }
    else /* n > 100 */ {
        /********** main recursion *************************/
        numGroups = n / 5; /* integer division, round down */
        for group = 0 to numGroups-1 do {
            shift = group*5;
            /* A[first+shift] is the start of the group, A[first+shift+4] is end of group */
            find median of A[first+shift .. first+shift+4] and swap it into A[first + group];
        } /* for group */;
        lastMedian = first+numGroups-1;
        /* now the medians of the numGroups groups are all A[first .. lastMedian] */
        /****** the first recursive call to find median of medians ******/
        select(A, first, lastMedian, numGroups/2);
        /* now median of medians is in slot A[first] */
        /*********** partition array *********************/
        k = partition(A,first, last); /* See partition on page 146 of text */
        /* now k is the index where the median of median winds up, the smaller elements */
        /* will be in A[first..k-1] and larger elements will be in A[k+1..last] */
        /************ where is the ith smallest element? ********/
        if (k == first + i -1) {
            /* ith smallest is the median of medians in A[k] */
            swap A[k] and A[first] and return
        } else if (k > = first + i -1) {
            /* second recursion to find ith smallest among the "small" keys in A[first..k-1] */
            select(A, first, k-1, i);
        } else /* k < first + i -1 */ {
            /* second recursion to find the proper element among the "large" keys */
            numSmaller = k-first+1; /* the number of "smaller" keys not recursed on */
            newi = i - numSmaller;
            /* the ith smallest of A[first..last] is the newi smallest of A[k+1..last] */
            select(A, k+1, last, newi);
            /* ith smallest now in A[k+1], put it in A[first] */
            swap A[k+1] and A[first];
        } /* if k - second else */
    } /* if n - else part */
} /*select */

У меня есть два вопроса:

первый относится к коду раздела, здесь нам дан только массив и его границы, элемент pivot не указан, так как должен выглядеть этот код раздела? Мы должны выбрать сводный индекс и сводный элемент как:

int pivotindex=(end-begin)/2
int pivot values=a[pivotindex];

или это должен быть случайный выбор?

как вывести выбранную медиану?

Обычно язык не имеет значения, но было бы здорово, если бы пример был показан на C ++.