4 ms·
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, bubbl
by xmprt 6y ago
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?
- contravariant 6y agoIf 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.
- xmprt 6y agoWhat would the brute force algorithm be? You mean like a 3 step selection sort?
- smiths1999 6y agoThey 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.
- andi999 6y agoWhat 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.
- smiths1999 6y agoWell I was actually thinking of quickselect, but regardless I was too quick to post. Quickselect is O(n) average time (as you pointed out).