tag:blogger.com,1999:blog-6314876008291942531.post8544628090631018119..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Selecting the median in an arrayUnknownnoreply@blogger.comBlogger6125tag:blogger.com,1999:blog-6314876008291942531.post-84591170990904501822010-01-13T06:29:23.591-08:002010-01-13T06:29:23.591-08:00In practice, if the integers are 32-bit words, i w...In practice, if the integers are 32-bit words, i would use a radix-based approach. With a single scan of the array build a table with 256 entries, such that T[i] stores the number of elements whose topmost 8 bits are i. Then you can trivially locate the bucket containing the median, which gives its first 8 bits. Reiterating the same scheme compute the median with 4 scan of the array and 256 words of extra space. Clearly, the size of the table need to be tuned to make the algorithm as fast as possible in practice.GiroTontihttps://www.blogger.com/profile/10692779656905527925noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-80667831153037634122010-01-05T09:42:35.860-08:002010-01-05T09:42:35.860-08:00No it is not allowedNo it is not allowedcodingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-10914503278524727112010-01-05T04:54:43.529-08:002010-01-05T04:54:43.529-08:00Hum, probably I misunderstood the question... is t...Hum, probably I misunderstood the question... is the algorithm allowed to modify the input array?<br />If the answer is no then achieving O(n) time in the RAM model is probably an open problem and is actually impossible in the comparison-based model (see T.Chan SODA09 on that problem). If the answer is yes, the classic selection algorithm inspired by quicksort is O(n) expected time and is already inplace.GiroTontihttps://www.blogger.com/profile/10692779656905527925noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-13812242231429014462010-01-04T05:52:08.078-08:002010-01-04T05:52:08.078-08:00that's classical quickselect. Any linear time ...that's classical quickselect. Any linear time solution ?codingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-50289416879952458842010-01-02T12:04:30.355-08:002010-01-02T12:04:30.355-08:00It can be done in O(n log n) time and O(1) additio...It can be done in O(n log n) time and O(1) additional space using binary search. <br /><br />Assume that the median is contained in the range [l,r]. With a single scan of the array we can sample a random value among the elements of the array contained in [l,r]. Then we just count the number of values less than x in order to decide if the median is in [l,x] or [x,r]. This solution does not modify the array.GiroTontihttps://www.blogger.com/profile/10692779656905527925noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-12425098722903414052009-12-30T08:51:20.445-08:002009-12-30T08:51:20.445-08:00Various solutions are:
1) Sort ant take the eleme...Various solutions are:<br /><br />1) Sort ant take the element in the middle; O(n log n) and it takes additional space O(n)<br /><br />2) QuickSelect which you find in any Algo book is linear in average, but still takes O(n) space<br /><br />3) A linear solution given by Cormern and other, which I cited in a previous post. It still takes additional O(n) space.<br /><br />What if I want to have this in place?codingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.com