Quote:Original post by Nice Coder I'm still in the habbit of using egsample. It just seems more natural to use eg. (considering that the contraction is e.g.)
It's latin: "Exempli Gratia", meaning "for example".
i.e. = "id est", "that is"
et al. = "et alia", "and others (people)"
etc. = "et caetera", "and others (things)"
Very nifty.
I'll try to change over to example.
From, Nice coder
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
Quote:Original post by lonesock definition, but not super helpful on the sorting topic...sorry.
Ok....
Either way, any viewpoint is a good one. (just what do you think of it? does it seem hard to code, have hidden costs, ect, ?)
From, Nice coder
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
If you're doing not-in-place sorting, rather than doing insertions into a vector (which can lead to horrible performance), use a binary tree, more specifically, a self balancing binary tree like the red-black tree. So, the algorithm becomes:
allocate memory for tree // you can build a tree in an arrayfor each element in array to sort add element to self balancing treenextfor each element in tree add element to end of vectornextdelete memory for tree
which gives you one allocation / deallocation, two copies per element (which can be very expensive depending on the class) plus O (log2 n), n = current element index (a summation of 0 <= n < number of elements). You can save a whole bunch of time by sorting an array of pointers to objects rather than objects if the object is greater in size than sizeof (int).
Probably not as fast as qsort (almost certainly slower if sorting pointers to objects).
Sounds now kinda like NC is describing radix sort or forward radix sort (Bitwise Sort). Skizz is describing red-black-tree sort.
btw, For arrays I have templated C++ implementations of the following sorting algorithms, many of which are known by other names, and some of which are my own creation. In approximate order of best to worst Big-O-notation.
All thoroughly tested of course, complete with asserts and unit tests, and a sorting demo program. I will release the code some day. I know of a few that I haven't done yet (like telephone sort), and am always looking out for more. I'm not seeing anything new, worth implementing, here yet though.
Or if you are talking about list sorting, I could name the algorithms I have for that, etc. You could say I got a bit carried away with sorting...
You've forgotten the linear-time Quantum Bogosort: randomize the data (constant-time quantum operation), and if it not sorted (linear-time check, maybe even constant-time), destroy the universe (constant-time).
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
allocate memory for tree // you can build a tree in an arrayfor each element in array to sort add element to self balancing treenextfor each element in tree add element to end of vectornextdelete memory for tree
Skizz
Sounds alot like a heap sort to me, which has best, average, and worst complexity always the same as qsort's average. It's basically what you have above, but with a heap ( priority queue ) instread of the RB tree, since all you care is that you can get the biggest element quickly, not that everything is sorted.
Yes. It seems quite a bit like heapsort to me too.
But its a good idea.
From, Nice coder
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
(ts both in place, it does the same number of ops/node, and it runs in o(log2 n) max time. (Ie, most of the time, it hits a point where it switches to insertionsort.)
From, Nice coder
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
