Page 1 of 2 12 Last
  • Jump to page:
    #1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    India
    Posts
    19
    Rep Power
    0

    mth largest element in array


    Given an array of N elements . cud any of u suggest how to find the mth largest element where 1<m<=n

    thankx
  2. #2
  3. digital sinner
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Location
    sinner's land
    Posts
    68
    Rep Power
    12
    use the binary method
    (i'll get back with more)
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    Bangalore, India
    Posts
    13
    Rep Power
    0

    Question


    Try binary search/ linear search or any of the searching methods and then get the mth member
    Last edited by mathurnitin; June 30th, 2003 at 08:42 AM.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    325
    Rep Power
    12
    for binary search, u need to sort it first
    sorting will cost 'n*log(n)' for unknown range of numbers, or cost 'n' with known range using bucket sort
    once you have that just pick it out of the mth position in the array.

    That's the best i can think of.
    You will obviously need to inspect every element which will cost you 'n' and then get it, so with a known range of numbers this is the best you will get. And without a known range, 'nlogn' is still excellent!

    Cheers
  8. #5
  9. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    India
    Posts
    19
    Rep Power
    0
    E'one's posted replies saying to use binary search and all.. but that wudnt really be reqd... sorting wud ensure that all elements fall in place .. jus accessing the mth element from the array would see me thro'.

    Sorting is 1 of the ways i agree , but given n elements and
    1<= m <=n why shud i sort elements upto m-1... when all i need is elements starting from m onwards sorted... I hope u are getting my point
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    325
    Rep Power
    12
    Originally posted by me_no_xpert
    Sorting is 1 of the ways i agree , but given n elements and
    1<= m <=n why shud i sort elements upto m-1... when all i need is elements starting from m onwards sorted... I hope u are getting my point
    no .. u need to check every element

    for example getting the 3rd smallest element from a list
    what if you added an element that is smaller than all in the list, and if u didnt check all elements (including the lsat one) then u'd have the 4th smallest instead of hte 3rd smallest

    u need to sort EVERY element.
  12. #7
  13. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    India
    Posts
    19
    Rep Power
    0
    ok... i have been working in dis algo dis way... heap-sorting the elements... so for the 1st ele... the ele on d top of d heap is d answer...
    but say i want the 3/4/5th ele... then ???
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    325
    Rep Power
    12
    ahh .. my flatmate thought of a much better way than sorting!

    -pick a pivot (as in quick sort)
    -split up elements to
    left side = element less than pivot
    right side = elements more than pivot

    then you would be ablt to decide which side to continue searching on for ur element

    for avg case,you need to inspect
    n + n/2 + n/4 + .......
    which limits to 2n which is pretty ****ing excellent!

    cheers
  16. #9
  17. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    India
    Posts
    19
    Rep Power
    0
    yogi,
    are u asking me to apply quick sort algo??
    iam still not clear what u'd written.. can u clarify plz
  18. #10
  19. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    325
    Rep Power
    12
    no don't use quick sort, just use the pivot idea from it

    for example, say you hve the numbers
    2,4,7,8,1,3,5,6
    and you wanna find the 3rd largest

    you pick a pivot, say (first+last)/2 = 4
    then split into those less(or equal) and thos more
    less_1 = 2,4,1,3
    more_1 = 7,8,5,6
    now you want 3rd largest so you only need to check the right (more_1) side since the 4 largest elements are there.

    so do it again .. but with 7,8,5,6
    pick pivot = (7+6)/2 = 6 (after rounding)

    more_2 = 7,8
    less_2 = 5,6

    you want third largest, and cuz the more_2 is the two largest and the more_1 is the 4 largest, you'd do it again and look for the largest in less_2

    you do this recursively splitting it in half each time.
    so the avg cost will be n + n/2 + n/4 + .....
    which limits to 2n in cost.

    Cheers
  20. #11
  21. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    India
    Posts
    19
    Rep Power
    0
    thanks yogi !
  22. #12
  23. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Location
    Magrath, Alberta CANADA
    Posts
    2
    Rep Power
    0
    Ummm...
    I don't think yogi is lazy enough.

    I am totally NOT dumping on your algorithm, but by the time you've done the grouping (into less and more groups) you could have been done finding the correct element.

    I'll show you:
    pick pivot (+1)
    do comparisons with every element in the list (+n)
    pick new pivot (+1)
    re-compare etc.

    Try a quicksort and index the mth largest element directly.
    quicksort (+nlogn)
    retrieve element (+1)

    Also easier to implement since everyone on the planet's written a quicksort

    -pb
  24. #13
  25. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    325
    Rep Power
    12
    haha .. I am lazy!! And I'll prove it!!

    ur wrong ! - twice !
    1. I am lazy!!


    quicksort cost :
    ---------------
    best : n
    avg: nlogn
    worst: n^2

    mine:
    -----
    best: n (if u split it right first time)
    avg: 2n = O(n)
    worst = n^2

    avg case is most often used and O(n) is better than O(nlogn)

    QED: I am lazy!
  26. #14
  27. digital sinner
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Location
    sinner's land
    Posts
    68
    Rep Power
    12
    offtopic: lazy_yoigi....u wrote those lines...therefore u r not lazy :P
  28. #15
  29. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    325
    Rep Power
    12
    OY!
Page 1 of 2 12 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo