Wednesday, October 17, 2012

Median of Medians to find Kth Smallest

Given an array of unsorted integers find the Kth smallest element using "Median of Medians".
This method is guaranteed to work in max linear time

Solution
Posted by at
Labels: , , ,

2 comments:

  1. fivestarNovember 30, 2013 at 12:41 PM

    you forgot to find the MOM element by recursivly calling the select at line 58. You are simply getting hte middle of medians instead of median of medians

    ReplyDelete
  2. GurgadurgenApril 20, 2014 at 6:30 PM

    "v = (x.length%2 == 0)? x[x.length%2-1]: x[x.length/2];"
    will always produce an error when the boolean part evaluates to true. Are you sure you didn't mean
    "v = (x.length%2 == 0)? x[x.length/2-1]: x[x.length/2];"?

    ReplyDelete

Subscribe to: Post Comments (Atom)
UA-36403895-1