Hacker News new | past | comments | ask | show | jobs | submit login

You make it sound like bubble sort is trivia when in reality, it's quite useful in specific real world situations. If I need the top 3 elements of a list, bubble or insertion sort are the most efficient ways to do that.

But that's something you wouldn't think about if you didn't know how bubble sort was implemented. Do you see how memorizing this can lead to creativity?




If you need the top 3 elements then neither of those are efficient. Technically insertion sort is more efficient if you stop early, but the straightforward brute force algorithm will be faster by a factor of 3.


What would the brute force algorithm be? You mean like a 3 step selection sort?


They are probably thinking of simply going through the list and tracking the top 3. This gives you linear time but as you noted you can go faster with quickselect (edit: I originally mistakenly wrote selection sort despite thinking of quickselect), giving you linear time (edit: I original said logarithmic time, which is obviously wrong).

I suppose it is besides the point, but you shouldn't be reaching for a specific algorithm but rather using your language's library sort algorithm.


What do you nean with selection sort giving logarithmic time? I mean any algorithm finding anything unique on an unsorted list has to be at least O(n) or resort to magic.


Well I was actually thinking of quickselect, but regardless I was too quick to post. Quickselect is O(n) average time (as you pointed out).




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: