|
.. said Mr. Spock
If it's not broken, fix it until it is
|
|
|
|
|
|
(Fresh off my discussion of BubbleSort, I've decided to move on another sort of topic [pun intended].)
It seems to me that there are only 5 really important sorting algorithms, although the others have their place for specific situations. There is BubbleSort (recently discussed) and InsertionSort, the latter of which is typically the best quadratic sort, and that has some use for smaller sizes. And then there are the big 3, QuickSort, MergeSort & HeapSort, which AIUI are generally used for the stable & unstable sorting functions; the unstable one seems to be IntroSort, which generally uses QuickSort, but cleverly figures out if the worst case (or something close) for QuickSort will happen, in which case it does HeapSort instead. My understanding is that QuickSort has the least stochastic expected time, but that it can go to quadratic time for the worst case, and that HeapSort has the fastest worst-case time, but still has a better stochastic expected time than MergeSort, so both are to be preferred, so long as equal-valued entries do not have to be in the same relative order. MergeSort has the least stochastic, and perhaps worst-case time (or at least not too bad of a worst case time), if the relative order of equal-value entries must be preserved, and so is used for stable_sort.
I understand how all of these work, except for HeapSort, which seems to be very complicated. It seems to rely on the fact that the binary heap tree can be automatically mapped to positions in an array, and that comparisons are done between positions that only differ by a single bit, with the result being swapped with the position corresponding to the previous bit. Somehow this simplicity is exploited so that the resultant algorithm is very efficient. I wonder if all but the top algorithm nerds really understand it.
|
|
|
|
|
I don't claim to be typical, but I don't understand it. (Nor do I understand QuickSort.)
|
|
|
|
|
Well they're probably not born with understanding of how heapsort works, but it's not so bad when you look it up is it?
edit: quick explanation, you have a binary heap there, of the max kind. The array is divided into the heap area and the "tail". RemoveMin gives the current highest number from the heap, removing it makes space in the tail, prepend it to the tail. The heap itself is at a high level a recursive structure with a node that has a value not lower than its children, which automatically means that the only legal place for the highest value overall is in the root. Adding the structural properties (fill level by level, right child can only exist if the left child exists) makes it map simply to a dense array because the size of every level (except the last one) is a known power of two. The structural properties are then essentially true automatically, only the ordering has to be taken care of, and it can be fixed recursively (in practice iteratively) by swapping a "too small parent" with the largest child.
modified 19-Aug-15 14:13pm.
|
|
|
|
|
I did when I was at university - but I don't think I've even used it since, much less needed to understand and / or implement it! 
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
|
|
|
|
|
Same here. I still remember how we had to draw diagrams to sort a few elements for the exam.
The language is JavaScript. that of Mordor, which I will not utter here
This is Javascript. If you put big wheels and a racing stripe on a golf cart, it's still a f***ing golf cart.
"I don't know, extraterrestrial?"
"You mean like from space?"
"No, from Canada."
If software development were a circus, we would all be the clowns.
|
|
|
|
|
I went back for a grad degree in CS (starting my third career), and the instructor in algorithms was a complete coding hard-ass--for which I am eternally grateful.
I didn't get my full degree (need a "real" job), but within two years I found the perfect business case for a Heap Sort, and it's been a life saver.
Situation: Need to perform team assignments to incoming records. Along with multiple assignment criteria, the final assignment should be to the guy/gal with the least number of current assignments. Need to process thousands of new team assignments at a time, and make it work out equitably in the end.
Solution: Create a MinHeap to hold each pool of candidates. When a team assignment comes in, pull top (meaning least-assigned) member from each pool, increment their counter, then throw them back into their MinHeap. The MinHeap takes care of keeping the pools organized.
I pretty much took publicly available code, abstracted out the array type, and changed the comparator to be defaulted to min but alterable. That way I can reverse the whole process and add other sorting capabilities if I ever need to.
It's only one use-case, but I've been using it over and over, with only minor modifications, if any. Resorting the entire pool (and having to select different sorting criteria every time) would have slowed the process down quite a bit. Probably not enough for a human to really notice, but I wanted the simplest maintenance arrangement that I could come up with.
vuolsi così colà dove si puote
ciò che si vuole, e più non dimandare
--The answer to Minos and any question of "Why are we doing it this way?"
|
|
|
|
|
Sounds interesting. If you can remember where you got the code (or left any copyright notice in place) there could be a good article in there - why not write it up?
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
|
|
|
|
|
Good point! I made sure to keep the source URL in the comments, so that won't be a problem. Since the question came up here, I wouldn't be surprised if the article would be useful.
vuolsi così colà dove si puote
ciò che si vuole, e più non dimandare
--The answer to Minos and any question of "Why are we doing it this way?"
|
|
|
|
|
Possibly Wirth book could help. It helped me when I wrote Heap Data Structure and Heap Sort[^] (shameless self-promotion). However I've forgot it and happily use bubblesort all the time
|
|
|
|
|
I usually sort my laundry into a heap as quickly as I can and them merge it all into the washing machine, if that helps.
|
|
|
|
|
Heap sort is easy. Keep removing Min element for ascending sort. Keep removing Max element for descending sort. The tricky part is understanding how heap data structure allows for log(n) operation for GetMinx() or GetMax()
|
|
|
|
|
This[^] may also be of help.
|
|
|
|
|
Not really. IMO those visualizations work well for more trivial sorts; but once something more interesting is going on behind the scene you need to see more information than sequential item moves gives you. If you don't know how it works why things are moved around in the order they are in quicksort makes no sense. Nor does why a heap sort moves the biggest item to the front while shuffling the rest of the list before flipping it to the back as it orders them down. Ditto for WTE shellsort is doing (not one I'm even vaguely familiar with and neither the visualization, textual description, or code sample are enlightening).
Did you ever see history portrayed as an old man with a wise brow and pulseless heart, waging all things in the balance of reason?
Is not rather the genius of history like an eternal, imploring maiden, full of fire, with a burning heart and flaming soul, humanly warm and humanly beautiful?
--Zachris Topelius
Training a telescope on one’s own belly button will only reveal lint. You like that? You go right on staring at it. I prefer looking at galaxies.
-- Sarah Hoyt
|
|
|
|
|
No clue...
But in 2005 I pay close attention and wrote my own List<T> class with all sort implementation and a little associated commented on when best call which one! 
|
|
|
|
|
You might find this free coursea course of interest
Algorithms, Part I[^]
It's from Princeton University and co-taught by Robert Sedgewick (who was one of Knuth's grad students). It covers all sorts of algos including heapsort.
|
|
|
|
|
Computer Science is a type of Math. With some mathematical proofs, you can explain the "trick" in a sentence or two, and with others you can't. For example, to prove the formula for the area of a right triangle, the trick is form a rectangle with two copies of it. But you can't explain the trick for proving the Pythagorean Theorem briefly. That's also the sitch with heapsort. Proving it involves several non-obvious steps, and you just have to slog through them.
|
|
|
|
|
There are additional important sorting algorithms.
- Radix sort (also called bucket sort) whose performance is O(n logr n) where r is the number of buckets. Some people don't know there are sorts faster than O(n log2 n). Radix sort is interesting because IBM built a mechanical device that could sort data on Hollerith punch cards.
- FlashSort, a variation on radix sort that can sort some key distributions (like a consecutive subset of integers) in O(n).
I understand how heapsort and quicksort work. That's easy. But there are people who really understand them, who can use the pieces efficiently for other work. That's much harder.
|
|
|
|
|
Like someone else said, sure, back when I was in college. But do you need to understand it today? There are tools that do sorting and so many other tasks. You can't understand the inner workings of all of them. Hell, when I come back to some of my old "still working, but now needing a mod" code, I sometimes don't understand it. At least not without some studying and reacquaintance with the problem I was solving at the time. The great majority of sorting I need to do is done via indexes in the database tools I use. Using a HeapSort is not really on my radar. Not that it hurts to internalize it and - if you've got that good of a memory - to remember it, but it's certainly not required.
|
|
|
|
|
Just got this email AND a voicemail:
Hello my name is Tomas and I am a Technical Recruiter working with TEKsystems. I came across your information in our database and wanted to speak with you about your extensive .NET background and the trends that I see here currently in the Southern California market.
"I came across your information in our database"  Ya, ok, sure
"Trends"?? What trends in Southern California?
Please give me a call at your earliest convenience and we can discuss the trends.
I'm reaching for the phone..NOT!
Thanks Kevin I look forward to speaking with you soon.
You wait right by the phone...
Stupid recruiter trolling for commissions again
If it's not broken, fix it until it is
|
|
|
|
|
Well, per your "signature", it seems his commissions are not broke, so he's seeking to fix it until it is!
|
|
|
|
|
What they actually want is referrals to hiring managers. It's the same reason an agent will ask for references before you've discussed a role/been interviewed. I always say "If they offer me a role, I'll happily give you references". If they don't play, there is no job.
|
|
|
|
|
Worked through them several times. They're ok.
Regards,
Rob Philpott.
|
|
|
|
|
Rob Philpott wrote: Worked through them several times.
Same here. I had no issues with them. One of the gigs was quite good, actually. I never got spammed by them, though. Interesting.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
