|
Linky?
- I would love to change the world, but they won’t give me the source code.
|
|
|
|
|
|
I have Visual Studio, gives me the best experience! I don't need to try anything at all. 
The sh*t I complain about
It's like there ain't a cloud in the sky and it's raining out - Eminem
~! Firewall !~
|
|
|
|
|
That's the odd thing - it's integrated with VS2013. I installed it back in July and forgot about it, silly me. I spent a couple of hours trying to figure out their model - never did really comprehend what they were offering a developer...
Charlie Gilley
<italic>Stuck in a dysfunctional matrix from which I must escape...
"Where liberty dwells, there is my country." B. Franklin, 1783
“They who can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety.” BF, 1759
|
|
|
|
|
charlieg wrote: It's like they are amateurs.
Well, what do you expect from hardware guys (and not even hardware, but that voodoo magic of etching millions of nanometer wide traces on thin wafers.)
I figure, they hired a bunch of idiot kids and idiot Java/Ruby/Python developers from third world countries around the world to quilt together something that works for their limited test cases.
I could be wrong though.
Marc
|
|
|
|
|
Marc Clifton wrote: I could be wrong though.
"... whatever you're left with, regardless how improbable, must be the truth."
|
|
|
|
|
.. 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.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
