How would you find the k smallest elements from an unsorted array using quicksort (other than just sorting and taking the k smallest elements)? Would the worst case running time be the same O(n^2)?
10
-
6Look at the quickselect algorithm to find the kth smallest element. Then partition around that element and get the k smallest elements. And yes worst case time complexity would be k*n.Abhishek Bansal– Abhishek Bansal2014-07-03 14:04:07 +00:00Commented Jul 3, 2014 at 14:04
-
1The naive answer is "sort the list, then take the first k elements", which yes, has the worst-case time complexity of O(n^2). However, you may be asking about the quickselect algorithm (which user1990169 just mentioned as well).chepner– chepner2014-07-03 14:05:20 +00:00Commented Jul 3, 2014 at 14:05
-
possible duplicate of Finding the kth smallest item in an array using quicksort => expected running time?Sneftel– Sneftel2014-07-03 14:18:05 +00:00Commented Jul 3, 2014 at 14:18
-
@Sneftel: Finding the kth smallest element allows you to find all k smallest elements in a subsequent O(n) pass, but it's not quite the same problem.j_random_hacker– j_random_hacker2014-07-03 15:51:26 +00:00Commented Jul 3, 2014 at 15:51
-
1@j_random_hacker Quickselect finds the kth-smallest element by partitioning around it. After quickselect, the elements in slots [0,k) are the smallest k elements (though not sorted WRT each other).Sneftel– Sneftel2014-07-03 16:05:50 +00:00Commented Jul 3, 2014 at 16:05
|
Show 5 more comments
1 Answer
You could optimize quicksort, all you have to do is not run the recursive potion on the other portions of the array other than the "first" half until your partition is at position k. If you don't need your output sorted, you can stop there.
Warning: non-rigorous analysis ahead.
However, I think the worst-case time complexity will still be O(n^2). That occurs when you always pick the biggest or smallest element to be your pivot, and you devolve into bubble sort (i.e. you aren't able to pick a pivot that divides and conquers).
Another solution (if the only purpose of this collection is to pick out k min elements) is to use a min-heap of limited tree height ciel(log(k)) (or exactly k nodes). So now, for each insert into the min heap, your maximum time for insert is O(n*log(k)) and the same for removal (versus O(n*log(n)) for both in a full heapsort). This will give the array back in sorted order in linearithmic time worst-case. Same with mergesort.
1 Comment
j_random_hacker
Generally good but note that (a) guaranteed linear-time median selection is possible, and drops the worst case for your first algo back to O(nlog n) (though it has a large constant factor so it's seldom used in practice); (b) for your second algo you actually want a max-heap, so that you can quickly identify the worst ((k+1)th) element after each heap push and throw it away.