Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int median_of_medians(int A[], int p, int r){
- int M = r-p+1;
- int groups_no = M/5;
- if(M%5 !=0)
- {
- groups_no ++;
- }
- int indices[groups_no][2];
- for(int i = 0;i<groups_no;i++)
- {
- if(i==groups_no-1)
- {
- indices[i][0] = i*5;
- indices[i][1] = M-1;
- break;
- }
- else
- {
- indices[i][0] = i*5;
- indices[i][1] = (i*5)+4;
- }
- }
- for(int i = 0;i<groups_no;i++)
- {
- insertion_sort(A,indices[i][0],indices[i][1]);
- }
- int medians[groups_no];
- for(int i = 0;i<groups_no;i++)
- {
- int index;
- if(i == groups_no-1)
- {
- index = (i*5) + (((M-1)) - (i*5))/2;
- medians[i] = A[index];
- break;
- }
- else
- {
- medians[i] = A[i*5+2];
- }
- }
- return quick_select(medians,p,r,((M+1)/2));
- // if(groups_no > 5)
- // {
- // median_of_medians(medians,0,groups_no);
- // }
- // else
- // {
- // int median_of_all;
- // if(groups_no % 2 == 0)
- // {
- // median_of_all = medians[(groups_no/2)-1];
- // }
- // else
- // {
- // median_of_all = medians[(groups_no+1/2)-1];
- // }
- // return median_of_all;
- // }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement