Quick select algorithm - find the Kth element in a list in linear time

Quick select algorithm - find the Kth element in a list in linear time

Monday, July 23, 2012 Quick select algorithm - find the Kth element in a list in linear time Quick select algorithm (Hoare's selection algorithm) – select the Kth element or the first K element from a list in linear time Working with large datasets is always painful, especially when it needs to be displayed in a 'human readable' format. It is a very frequent task to display only the largest, newest, most expensive etc. items. While sorting the whole dataset definitely gives a correct result, it is much slower than it needs to be – it needs at least O(n*log(n)) time and an it often uses recursion for the sorting, so in practice it can be quite slow. The quick select algorithm can get the top K element from a list of N items in linear time, O(n), with a very reasonable multiplication factor. The quick select does not use recursion so the performance is great for even large datasets. Algorithm The idea of the quick select is quite simple: just like with quicksort,

Read full article from Quick select algorithm - find the Kth element in a list in linear time