{"id":181,"date":"2018-03-06T07:42:28","date_gmt":"2018-03-06T07:42:28","guid":{"rendered":"http:\/\/www.datastructure.org\/?p=181"},"modified":"2025-04-21T13:49:11","modified_gmt":"2025-04-21T13:49:11","slug":"find-the-kth-largest-number-or-median-of-medians","status":"publish","type":"post","link":"https:\/\/www.bhargaviurs.com\/index.php\/2018\/03\/06\/find-the-kth-largest-number-or-median-of-medians\/","title":{"rendered":"Find the kth largest number or Median of medians"},"content":{"rendered":"
Finding the Kth biggest using Heap Sort<\/strong><\/h6>\n
    \n
  1. Sort it by getting the biggest, then the next biggest, then the next and so on. . .<\/li>\n
  2. Every time to get the next biggest – get the biggest and fix the heap  takes —-> logn
    \nHence, for kth biggest –> klogn
    \n2nd biggest—>2logn
    \n3rd biggest —>3logn
    \nMiddle one —> (n\/2)logn
    \n(we want this in linear time)<\/li>\n<\/ol>\n

    Note:<\/strong> Calculating the median is a special case of finding the kth biggest element.<\/p>\n

    Method to calculate the median (or) to find the kth biggest element<\/strong><\/h6>\n

    Fill the numbers in a 2D array with 5 rows and ‘n\/5’ columns, where ‘n’ is the number of elements in your list.
    \nGoal is to find the middle element in each column.<\/p>\n

    Steps:<\/strong><\/h6>\n
      \n
    1. Find the middle element in each column.(it takes 6 comparisons for 5 elements).\"\"<\/li>\n
    2. Partition the column such that smaller ones are above and larger ones are below the middle element.(constant number of moves since there are only 5 elements)\"\"<\/li>\n
    3. Find the median of middle row and partition it left to right(as in Quick Sort) such that smaller elements are on left and bigger ones are on the right of the median.
      \nMove the complete length 5 columns around appropriately after the partition.\"\"<\/li>\n
    4. Go through each element whose relationship to the big median is unknown and place it in the correct set.\"\"<\/li>\n<\/ol>\n

      For example:
      \nSay, set1 = 31 elements (smaller)
      \nset 2 = 68 elements (larger)
      \nset1——median——-set2
      \n31———–(32)———–68
      \n50th biggest —> 50 – 32 = 18 –> Find the 18th biggest from set2, gives 50th biggest in the original. (note that this is recursive)<\/p>\n

      Analysis
      \n<\/strong><\/h6>\n

      Step 1:<\/strong> Partition Columns
      \n6 comparisons each column, multiply by (n\/5) columns
      \nT(n) = 6(n\/5)
      \nStep 2<\/strong>: partition the middle row on the median and move the length 5 columns around appropriately.<\/p>\n

        \n
      1. Finding median –> recursive call –> T(n\/5)<\/li>\n
      2. Move things around –> partitioning –> length of the array.
        \nEvery time we swap, we swap 5 elements, length = (n\/5), swap = 5 for each –> (C1) some constant
        \nso, T(n) = 6(n\/5) + T(n\/5) + C1(n\/5)<\/li>\n<\/ol>\n

        Step 3:<\/strong> put unknowns to appropriate sets.
        \nWorst case – (n\/2) i.e half of the elements may be unknowns.
        \nso, T(n) = 6(n\/5) + T(n\/5) + C1(n\/5) + (n\/2)
        \nStep 4:<\/strong> Run the problem in set1 or set2 based on kth number(position).
        \nExample: 31—-median(32)——-68
        \nIf we want 6th largest, run in set1.
        \nWorst case =  T(3n\/4)
        \nmeaning, all unknown may fall into one set, making it 3\/4th of the whole space, and we have to run our algorithm on that whole space.
        \nWhen,  set1: set2 = 25 : 75 , and the kth biggest element falls in set2, and hence worst case is 3\/4th of the whole set.
        \nTherefore, T(n) = 6(n\/5) + T(n\/5) + C1(n\/5) + (n\/2)  + T(3n\/4)
        \nHence, T(n) <= T((constant fraction) n)<\/strong>
        \nReference: Algorithms – Searching & Data Structures – Lecture 4<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

        Finding the Kth biggest using Heap Sort Sort it by getting the biggest, then the next biggest, then the next and so on. . . Every time to get the next biggest – get the biggest and fix the heap  takes —-> logn Hence, for kth biggest –> klogn 2nd biggest—>2logn 3rd biggest —>3logn Middle … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"class_list":["post-181","post","type-post","status-publish","format-standard","hentry","category-algorithms","entry"],"_links":{"self":[{"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/posts\/181","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/comments?post=181"}],"version-history":[{"count":1,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/posts\/181\/revisions"}],"predecessor-version":[{"id":446,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/posts\/181\/revisions\/446"}],"wp:attachment":[{"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/media?parent=181"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/categories?post=181"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/tags?post=181"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}