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)?$
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ How can you perform binary search on yet to be sorted array? Order is random, so binary search will not work. $\endgroup$– EvilCommented Jun 4, 2016 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 DoughertyCommented Jun 4, 2016 at 3:30
-
$\begingroup$ Very, very closely related question. $\endgroup$– RaphaelCommented Jun 4, 2016 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$– RaphaelCommented Jun 4, 2016 at 15:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Jun 4, 2016 at 1:02