Advertisement
vinocastro

Median of Medians ni Beebom

Jan 4th, 2021
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.36 KB | None | 0 0
  1. int median_of_medians(int A[], int p, int r){
  2.  
  3. int M = r-p+1;
  4. int groups_no = M/5;
  5. if(M%5 !=0)
  6. {
  7. groups_no ++;
  8. }
  9. int indices[groups_no][2];
  10. for(int i = 0;i<groups_no;i++)
  11. {
  12. if(i==groups_no-1)
  13. {
  14. indices[i][0] = i*5;
  15. indices[i][1] = M-1;
  16. break;
  17. }
  18. else
  19. {
  20. indices[i][0] = i*5;
  21. indices[i][1] = (i*5)+4;
  22. }
  23. }
  24. for(int i = 0;i<groups_no;i++)
  25. {
  26. insertion_sort(A,indices[i][0],indices[i][1]);
  27. }
  28.  
  29. int medians[groups_no];
  30. for(int i = 0;i<groups_no;i++)
  31. {
  32. int index;
  33. if(i == groups_no-1)
  34. {
  35. index = (i*5) + (((M-1)) - (i*5))/2;
  36. medians[i] = A[index];
  37. break;
  38. }
  39. else
  40. {
  41. medians[i] = A[i*5+2];
  42. }
  43.  
  44. }
  45.  
  46. return quick_select(medians,p,r,((M+1)/2));
  47. // if(groups_no > 5)
  48. // {
  49. // median_of_medians(medians,0,groups_no);
  50. // }
  51. // else
  52. // {
  53. // int median_of_all;
  54. // if(groups_no % 2 == 0)
  55. // {
  56. // median_of_all = medians[(groups_no/2)-1];
  57. // }
  58. // else
  59. // {
  60. // median_of_all = medians[(groups_no+1/2)-1];
  61. // }
  62.  
  63. // return median_of_all;
  64. // }
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement