2
$\begingroup$

We make $n$ insertions and each insertion targets a list of size $k\le n$, so we can make a binary search which takes maximum $\log k\le \log n$. So why isn't the running time of selection sort $O(n \log n)?$

$\endgroup$
  • 3
    $\begingroup$ How can you perform binary search on yet to be sorted array? Order is random, so binary search will not work. $\endgroup$ – Evil Jun 4 '16 at 0:23
  • $\begingroup$ Try running insertion sort on an array that is nonincreasing (i.e., reverse sorted order). How many operations do you perform? $\endgroup$ – Ryan Jun 4 '16 at 3:30
  • $\begingroup$ Very, very closely related question. $\endgroup$ – Raphael Jun 4 '16 at 15:33
  • $\begingroup$ "Why don't things fall up?" I'm not clear on what kind of answer you expect. It doesn't because it doesn't. Perform a proper analysis and you'll see that. $\endgroup$ – Raphael Jun 4 '16 at 15:34
5
$\begingroup$

Selection sort proceeds by finding the smallest unsorted element and adding it to the end of the sorted section of the array. You can't use binary search to find the smallest unsorted element, because binary search only works on sorted lists.

Your question seems to be based on the mistaken understanding that selection sort takes the first unsorted element and inserts it into the correct place in the sorted list. The correct place could then be found by binary search but the problem with that attempt at an algorithm is that you need array-like access to the sorted portion for binary searching it, and list-like access for inserting in the middle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.