tag:blogger.com,1999:blog-8858921836121088131.post5602504807085686524..comments2019-07-29T22:37:10.490-07:00Comments on Adam Horvath's blog: Quick select algorithm - find the Kth element in a list in linear timeAdamhttp://www.blogger.com/profile/09720738376586525885noreply@blogger.comBlogger25125tag:blogger.com,1999:blog-8858921836121088131.post-65001502962161538622018-09-13T18:06:13.706-07:002018-09-13T18:06:13.706-07:00Very nice done. Thank you for posting this. Very nice done. Thank you for posting this. Unknownhttps://www.blogger.com/profile/00956828458942665314noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-5148755138162541952018-06-08T02:53:12.961-07:002018-06-08T02:53:12.961-07:00Nice blog has been shared by you. it will be reall...Nice blog has been shared by you. it will be really helpful to many peoples who are all working under the technology.thank you for sharing this blog.<br /><br /><a href="https://www.zuaneducation.com/php-training-courses" rel="nofollow"> Php course in chennai</a>sriramhttps://www.blogger.com/profile/09683538147321194792noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-12453153801916189762015-05-13T18:59:08.615-07:002015-05-13T18:59:08.615-07:00Adam, thank you for sharing this code sample and e...Adam, thank you for sharing this code sample and explanation. <br /><br />The issue I had porting to "C" is that "r" can go negative. If k is declared as unsigned (e.g. size_t), the evaluation " if (k <= r) " casts r to "unsigned" rather than k to "signed". Thus, r= -1 is seen as r=0xffff.... (to however many bytes precision you're using), and so unsigned r compares as being larger than (unsigned) k in that case and throws everything off. Make sure k and r are both signed in the comparison, and that you have enough bits of precision to handle the indexes for your array size without overflowing, and it should work.Tom Warfelhttps://www.blogger.com/profile/00704742770773600884noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-77362205039717542412015-03-24T13:31:19.915-07:002015-03-24T13:31:19.915-07:00Right. The worst time runtime complexity of quick ...Right. The worst time runtime complexity of quick select is known to be O(n^2). Average is O(n), though.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-49765895812440414142014-03-17T14:10:21.539-07:002014-03-17T14:10:21.539-07:00Great post, the best I have seen on the topic!
The...Great post, the best I have seen on the topic!<br />There is a subtle problem, though... When you pass 4 as k, it finds the 5th smallest value. To fix this, a simple k-- at the very beginning of the algorithm will suffice; if I have to nit-pick...Erhan Onalhttps://www.blogger.com/profile/11454276661309509891noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-39212110970042813402014-01-11T12:43:36.846-08:002014-01-11T12:43:36.846-08:00You mention that after the first iteration all ele...You mention that after the first iteration all elements to the left of the pivot are less than the pivot while all element to the right are larger or equal. However, if your initial array is {5,4,1,3,2} your pivot happens to be the minimum and in this case after the first iteration it will be placed in in the second position, i.e. you have {4,1,3,2,5}. The algorithm still works but because of this condition:<br />if (arr[r] >= mid)<br />when you get {1,4,3,2,5}<br />you swap 1 and 4 since 1>=1 (r is at 0 and w is at 1). <br />When the pivot is the minimum in the fist iteration you never reach the else body (r++) so you constantly decrement w until it reaches 0 where the first iteration stops.<br />Christinahttps://www.blogger.com/profile/07508463890483685959noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-72847476162840834962014-01-06T13:41:20.544-08:002014-01-06T13:41:20.544-08:00// if we stepped up (r++) we need to step one down...// if we stepped up (r++) we need to step one down<br /> if (arr[r] > mid)<br /> r--;<br />Could you clarify this portion of the code? I'm having trouble thinking of cases where this occurs.Anonymoushttps://www.blogger.com/profile/01034755096517143398noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-29426471994576879482013-12-06T03:44:06.591-08:002013-12-06T03:44:06.591-08:00This comment has been removed by the author.Ashishhttps://www.blogger.com/profile/04074065255654957185noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-62473940996607492342013-09-19T10:29:58.757-07:002013-09-19T10:29:58.757-07:00I found the problem:
The compiler did not handle ...I found the problem:<br /><br />The compiler did not handle the last comparisation correctly:<br /><br />if (k <= r) {<br /> to = r;<br /> } else {<br /> from = r + 1;<br /> }<br /><br />instead of setting "from" to "r+1" ==0 in the mentioned case, it set "to" to "r"== 0xFFFF. <br />The problem seemed to be related to a 16 Bit/ 32 Bit implementation problem.<br /><br />Thomas<br /><br /><br /> Thomas Leuthnerhttps://www.blogger.com/profile/13458214926665069745noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-36022579419849761532013-09-19T10:03:40.629-07:002013-09-19T10:03:40.629-07:00This comment has been removed by the author.Thomas Leuthnerhttps://www.blogger.com/profile/13458214926665069745noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-84822823350007738932013-09-19T09:58:57.474-07:002013-09-19T09:58:57.474-07:00This comment has been removed by the author.Thomas Leuthnerhttps://www.blogger.com/profile/13458214926665069745noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-27231476301218016562013-09-19T09:15:15.115-07:002013-09-19T09:15:15.115-07:00Hello Adam,
I think Java, being an interpreted la...Hello Adam,<br /><br />I think Java, being an interpreted language, checks for false indizes and probably ignores access to an array with a size of seven bytes with an index of (FFFF).<br />The good thing with this ARM controller is that it has a very good debugger, and it can easily be traced down to the line that decrements r index while r is still zero. The microcontroller goes into a hard fault then when accessing the array with that index in the next loop. <br /><br />In some cases, mainly when the pivot is the smallest number of the set of numbers currently checked, the "else" path is never taken, the algorithm loops through the "if" part only:<br /><br />if (arr[r] >= mid) { // put the large values at the end<br /> int tmp = arr[w];<br /> arr[w] = arr[r];<br /> arr[r] = tmp;<br /> w--;<br /> } else { // the value is smaller than the pivot, skip<br /> r++;<br /> }<br /><br />In some cases, still the "r--" is executed, since "(arr[r] > mid)". <br /><br />I am not an expert in Java programming, so maybe a few things are handled differently, but I checked that arrays indices start also at 0, and the meaning of >, >= and <, <= are hopefully also the same.<br /><br />Thomas<br /><br /><br />Thomas Leuthnerhttps://www.blogger.com/profile/13458214926665069745noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-48271479244555145092013-09-16T16:19:41.823-07:002013-09-16T16:19:41.823-07:00Hi Thomas,
The Java implementation above correctl...Hi Thomas,<br /><br />The Java implementation above correctly prints out the numbers from your sequence when k is set to 0..6:<br />1<br />82<br />83<br />94<br />122<br />192<br />251<br /><br />I think your C code might be flaky?Adam Horvathhttps://www.blogger.com/profile/09720738376586525885noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-82598718398375803012013-09-16T07:31:37.022-07:002013-09-16T07:31:37.022-07:00Forgot to mention:
For the cases it works, it is a...Forgot to mention:<br />For the cases it works, it is about four times faster than the ARM C library "qsort" function.<br />TLThomas Leuthnerhttps://www.blogger.com/profile/13458214926665069745noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-60697201628257713452013-09-16T07:27:35.789-07:002013-09-16T07:27:35.789-07:00Hi, I tried to implement the algorithm in C, on an...Hi, I tried to implement the algorithm in C, on an ARM controller. After some successful testing, I found out there are many combinations that make the program fail:<br />It can easily happen that you are decrementing the r index, although it is still zero:<br />>>// if we stepped up (r++) we need to step one down<br />>> if (arr[r] > mid)<br />>> r--;<br />Try a median length of seven, and the values 94,83,82,1,192,122,251, for example<br />Fails in the first loop already, and sets r to -1, which crashes the program, in the next loop.<br /><br /><br />Haven't found a solution yet, but testing.<br /><br />Best regards<br />Thomas<br />Thomas Leuthnerhttps://www.blogger.com/profile/13458214926665069745noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-57511530901320533042013-09-15T23:15:38.842-07:002013-09-15T23:15:38.842-07:00Thanks, very simple and clear explanationThanks, very simple and clear explanationAlexey Skidanovhttps://www.blogger.com/profile/08052587238735526610noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-62523452646664214302013-08-06T13:29:01.588-07:002013-08-06T13:29:01.588-07:00Came across your blog by searching "implement...Came across your blog by searching "implementation of fast selection". It's a nice posting. <br /><br />FYI: The complexity analysis on "Hoare's algorithm" here is too "idealized" (each time you assume an ideal pivot); the realistic complexity should be "O(n^2)". The real "fast selection" algorithm, which is O(n), goes to Blum, Floyd, Pratt, Rivest and Tarjan. See<br />https://en.wikipedia.org/wiki/Selection_algorithm if you are interested.Ronghttps://www.blogger.com/profile/13118788198384610557noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-17201150313308823672013-05-20T05:11:58.034-07:002013-05-20T05:11:58.034-07:00Thanks great blog !Thanks great blog !נעםhttps://www.blogger.com/profile/13175157489462977953noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-37346702152058345942012-12-10T13:58:16.234-08:002012-12-10T13:58:16.234-08:00Maybe try translating line by line? The above algo...Maybe try translating line by line? The above algorithm works fine for small and large arrays :)Adam Horvathhttps://www.blogger.com/profile/09720738376586525885noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-43445045544901225732012-12-10T12:20:56.390-08:002012-12-10T12:20:56.390-08:00Interesting algorithm, is it supposed to work when...Interesting algorithm, is it supposed to work when K is much smaller than N, right? Because I've implemented it in C++ for small arrays (N = 10) with different elements to get a feeling of how it works and I found that it fails for K > 4. I think my code is correct and I think this problem happens when K is near to the pivot but I didn't realize how to solve it.<br /><br />Anyway, I think this isn't a big problem.gfs.reboucashttps://www.blogger.com/profile/00586544700964883409noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-90851108061924834522012-10-07T00:55:10.212-07:002012-10-07T00:55:10.212-07:00Good point Ashwin. The above code is the purest fo...Good point Ashwin. The above code is the purest form of the algorithm without additional tweaks - like the one you mentioned. Watch out though, depending on your input data, adding that extra branch might be very expensive if mispredicted compared to a branchless cached memory read/write operation! Adam Horvathhttps://www.blogger.com/profile/09720738376586525885noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-54282346909572846922012-10-04T22:46:09.051-07:002012-10-04T22:46:09.051-07:00Could the algorithm be improved if you were to als...Could the algorithm be improved if you were to also walk leftwards with the "w" pointer for all a[w] > pivot. That way you could avoid some repeated swaps where a high value is first moved to "r" and then swapped back to a "--w".<br /><br />AshwinAshwinhttps://www.blogger.com/profile/11728187704386816706noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-36291748557339903202012-10-04T21:33:57.269-07:002012-10-04T21:33:57.269-07:00This comment has been removed by the author.Ashwinhttps://www.blogger.com/profile/11728187704386816706noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-29632562937931213972012-09-18T01:03:46.742-07:002012-09-18T01:03:46.742-07:00I was testing with randomized arrays; The algorith...I was testing with randomized arrays; The algorithm handles repeating values well. If you think of the general selection, repeating values do not make any difference; however, poorly written solutions will generally fail with repeating values. GIve it a go, it's open source ;)Adam Horvathhttps://www.blogger.com/profile/09720738376586525885noreply@blogger.comtag:blogger.com,1999:blog-8858921836121088131.post-33746620465180032572012-09-17T16:00:23.077-07:002012-09-17T16:00:23.077-07:00Thanks for the blog post!
When you tested the per...Thanks for the blog post!<br /><br />When you tested the performance, were your test values all non-repeating integers?<br /><br />I'm doing something similar to your algorithm, and I find that if the median value has repeating values, I will go into an infinite loop. I didn't see any code to protect against this, so I'm wondering if your code naturally solves this problem, or if it is also susceptible to this?Ken Jacksonhttps://www.blogger.com/profile/13289073656005638126noreply@blogger.com