Here is pseudo code for implementation of median by dividing array into 5 groups
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 */
I have two questions:
first one is related to partition code, here we are given only array and its bounds, no pivot element is indicated, so how this partition code should look? We should choose pivot index and pivot element as:
int pivotindex=(end-begin)/2 int pivot values=a[pivotindex];
or it should be random choice?
how to output selected median?
Generally language does not matter, but it would be great if example would be shown in C++.