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

Popular posts from this blog

javascript - Count length of each class -

What design pattern is this code in Javascript? -

hadoop - Restrict secondarynamenode to be installed and run on any other node in the cluster -