c++ - ith order Selection in O(n) time -
from "introduction algorithms" trying implement code dividing n elements in n/5 groups, recursively finding median , recursively finding ith order statistics. here code
bool istrue(int *a, int *b) { if((*a) < (*b)) swap(*a, *b); return *a < *b; } int select(int *a, int n ,int p) { int *b[(n / 5) + 2]; cout << (n / 5) + 2 << endl; int i, j; for(i = 1, j = 1; <= (n - 5); += 5, ++j) { sort(a + i, + + 5); b[j] = + + 2; } sort(a + i, + n + 1); b[j] = + + (n - i) / 2; sort(b + 1, b + (n / 5) + 2, istrue); }
this far can go. trying find median of b
, b[median] - a
pivot. doesn't seems right. in book says recursively find median of medians.i can't catch that. help? edit: note in wiki didnt use recursion!
Comments
Post a Comment