0

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)?

MNRC
  • 175
  • 2
  • 12
  • 6
    Look 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 Jul 03 '14 at 14:04
  • 1
    The 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 Jul 03 '14 at 14:05
  • possible duplicate of [Finding the kth smallest item in an array using quicksort => expected running time?](http://stackoverflow.com/questions/17914808/finding-the-kth-smallest-item-in-an-array-using-quicksort-expected-running-ti) – Sneftel Jul 03 '14 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 Jul 03 '14 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 Jul 03 '14 at 16:05
  • @Sneftel: I forgot that quickselect already partitions, so indeed no final pass is necessary. Still I think this is not the same *question* as the question you linked to -- it just happens that the answer is the same. – j_random_hacker Jul 03 '14 at 17:26
  • @j_random_hacker It looks like a very similar problem to finding the kth smallest elements but is different. Please remove the downvote if you had clicked on it. Thanks. – MNRC Jul 07 '14 at 08:24
  • @user3802002: ??? I'm the one who said *it's not quite the same problem*. It doesn't make sense that I would be the downvoter. – j_random_hacker Jul 07 '14 at 08:37
  • @j_random_hacker Sorry, misread the signature of your comment! – MNRC Jul 07 '14 at 23:28
  • @Sneftel Hi, this question is slightly different from finding the kth element but both seem to share the same solution. If you had down voted this question could you remove the down vote? Thanks so much. – MNRC Jul 07 '14 at 23:31

1 Answers1

1

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.

Clever Neologism
  • 1,322
  • 8
  • 9
  • 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. – j_random_hacker Jul 03 '14 at 15:49