Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #24184
| From | "Alex McDonald" <blog@rivadpm.com> |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: Simple Sort - the smallest sorting routine? |
| Date | 2013-07-06 00:18 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <kr7jth$ref$1@dont-email.me> (permalink) |
| References | (7 earlier) <d3515fe4-5421-47f3-b590-bff7e4d9584c@googlegroups.com> <18f27274-dc2c-4cda-95e7-a3526b319786@googlegroups.com> <bde62eee-6e01-422c-b2c6-104080ee6855@googlegroups.com> <1d68e6bc-f11c-4bd8-a907-fc819f0d4373@googlegroups.com> <ef461c0a-4955-4104-a17c-2f669ebfccfa@googlegroups.com> |
On 05/07/2013 05:30:54, wrote: > On Thursday, July 4, 2013 2:58:19 AM UTC-7, Alex McDonald wrote: >> On Thursday, 4 July 2013 02:41:28 UTC+1, hughag...@yahoo.com wrote: >> Heapsort and a linked list merge sort differ in that heapsort is unstable > , and it requires auxiliary space. So much for "theoretically the > same". Yo u mean that they are both worst case O(n log n); that's not > the only criter ia for categorising or selecting a sort. > > HeapSort doesn't require auxiliary memory. I miswrote (or rather, I wasn't clear enough with my comparison). Heapsort requires a small constant amount of auxiliary storage *if it uses tail recursion*; for a recursive solution, it requires proportional to lg(n) of call stack space, as does a link list merge. IIRC your novice package is not tail recursive. It could be, but it would also require a Forth that supports tail recursion. > > The reason why I use HeapSort rather than QuickSort, is because > HeapSort is more consistent in how much time it takes, whereas > QuickSort varies a lot depending upon how well-ordered the original > data is. This is important for micro-controllers, where consistency is > hugely important (although the nov ice package isn't for > micro-controllers, so that doesn't apply there). But quicksort is, on the average, much faster that heapsort. Only when the input is sorted is quicksort appreciably slower (for large n, yes, it can be hugely expensive) so it's fairly standard practice to swap the imput before starting. And quicksort has really good locality of reference, unlike heapsort that jumps about everywhere. Is that important? If speed and consistency are important, and n is relatively small (as I presume it would be in a micro controller) then quicksort can be made to win just about every time. In other words, I think you've possibly got this back to front. Picking a sort depends on a lot of factors, not just one. > > QuickSort is so simple that it is easy to memorize. In a job > interview, if they want me to write a sort program on the blackboard, > I'll go with QuickS ort for this reason --- I can't remember how to > implement HeapSort without looking it up, although HeapSort is what I > actually use in practice. Why? It isn't the best sort every time, since the best depends on what you want to achieve. > >> > I wouldn't be so bold as to say that the MergeSort is certainly faster > and that somebody else "ought" to use it, without having actually > tried the technique first myself. >> >> In other words, you don't have a clue, yet you're happy to spout off abou > t code quality, sorting in general and the superiority of you novice > code w ithout any justification. > > I have never implemented a MergeSort --- maybe I will do so for the > next no vice-package release. It is awkward right now, that I have two > ways to sort lists, the InsertionSort for small lists, and the > BIG-SORT (convert to and from an array of pointers) for big lists. It > would be better to just have one list-sort function. I will still keep > InsertionSort though, for the cas e where items are added to the list > one at a time, and inserted into a sort ed position --- this is > actually a lot more common than building up an enti re list unsorted, > and then sorting it all in one fell swoop --- in my own p rograms that > use list.4th, this is all that I've ever done. Your data and code seems to require an adaptive sort. There are adaptve versions of merge sort and heap sort. Or even a pre-swap to ensure the data isn't sorted; then use quicksort. And the sorted results will possibly be different, since some sorts are stable like merge sort; others aren't. An insertion sort can be either. > > Writing code for the novice package isn't just a way to benefit my > legion o f users (I don't actually have any users, afaik), but it is > also a way for me to learn new stuff. > Which is an admirable goal. But you once claimed that you didn't read anybody else's code or academic type articles. Remember the splay trees argument? That same lack of research and certainty in your own rightness shows in this set of posts too. You'd be a much better programmer -- and perhaps have some appreciative users of your library -- if you took a little time to check before sending crash and burn posts.
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar
Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-25 13:12 -0700
Re: Simple Sort - the smallest sorting routine? Mark Wills <markrobertwills@yahoo.co.uk> - 2013-06-25 23:48 -0700
Re: Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-26 09:11 -0700
Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-06-26 02:03 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-06-26 11:25 -0500
Re: Simple Sort - the smallest sorting routine? the_gavino_himself <visphatesjava@gmail.com> - 2013-06-26 12:36 -0700
Re: Simple Sort - the smallest sorting routine? "Elizabeth D. Rather" <erather@forth.com> - 2013-06-26 09:49 -1000
Re: Simple Sort - the smallest sorting routine? "WJ" <w_a_x_man@yahoo.com> - 2013-06-26 20:24 +0000
Re: Simple Sort - the smallest sorting routine? "WJ" <w_a_x_man@yahoo.com> - 2013-06-26 20:23 +0000
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-26 13:35 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-26 16:37 -0700
Re: Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-27 01:31 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-06-27 04:04 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 09:27 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-30 13:23 -0700
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-06-30 21:48 +0100
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 16:53 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-01 04:34 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-03 18:41 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-04 02:58 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-04 21:30 -0700
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-06 00:18 +0100
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-06 13:45 +0200
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-06 07:49 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-06 13:38 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-06 10:06 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 23:08 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:24 -0500
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-07 23:47 +0200
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-07 09:59 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:52 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-07 12:18 +0000
Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-07-08 00:06 -0700
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-08 09:50 +0000
Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-07-08 03:14 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-08 09:53 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-09 14:25 +0000
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-09 23:39 +0200
Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-09 18:03 -0700
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-10 23:05 +0200
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 03:21 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 10:29 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 05:44 -0500
Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-10 04:07 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 06:06 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 14:21 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 04:45 -0500
Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-10 03:13 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 05:09 -0500
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-10 12:16 +0000
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 10:38 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 06:45 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 13:56 +0000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 10:54 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-10 13:57 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 07:15 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 13:52 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 15:00 -0500
Re: Simple Sort - the smallest sorting routine? Coos Haak <chforth@hccnet.nl> - 2013-07-10 16:13 +0200
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 17:07 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 10:53 +0000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 10:40 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:17 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 16:54 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-12 03:07 -0500
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-07 00:43 +0200
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-07 00:21 +0000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 20:32 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:38 -0500
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 07:05 -0500
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-07 13:00 +0000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:47 -0700
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 21:22 +0100
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 19:25 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 21:58 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-08 02:27 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-08 21:18 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-09 04:20 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 10:30 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 15:13 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 13:57 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 16:57 -0500
Re: Simple Sort - the smallest sorting routine? Elizabeth D Rather <erather@forth.com> - 2013-07-10 13:00 -1000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 22:19 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 10:23 -0700
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-11 01:12 +0200
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 00:33 -0500
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-11 11:48 +0200
Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-11 03:08 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 05:00 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 10:17 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 06:53 -0500
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-11 15:21 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 10:37 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:07 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:19 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:33 +0000
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-11 18:18 +0000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 16:46 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-12 03:48 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-12 10:55 -0700
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-12 19:29 +0000
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-15 09:50 +0000
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-12 13:22 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-13 20:05 -0700
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-14 11:34 +0000
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-14 09:18 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 16:05 -0700
Re: Simple Sort - the smallest sorting routine? Ron Aaron <rambamist@gmail.com> - 2013-07-15 06:12 +0300
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 22:17 -0700
Re: Simple Sort - the smallest sorting routine? Ron Aaron <rambamist@gmail.com> - 2013-07-15 11:44 +0300
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-15 09:42 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-16 18:03 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-17 00:54 -0700
Re: Simple Sort - the smallest sorting routine? Howerd <howerdo@yahoo.co.uk> - 2013-07-14 10:09 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 15:35 -0700
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:08 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:30 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 09:34 -0700
Re: Simple Sort - the smallest sorting routine? Michael Morris <morrimichael@gmail.com> - 2013-07-15 23:09 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-16 17:46 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-17 03:14 -0500
Re: Simple Sort - the smallest sorting routine? "Rod Pemberton" <do_not_have@notemailnotq.cpm> - 2013-07-17 21:47 -0400
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-11 04:06 +0100
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 20:18 -0700
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 16:48 +0100
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:13 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:13 -0700
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 21:24 +0100
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-04 14:41 +0000
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-27 01:59 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 09:30 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-30 12:59 -0700
Re: Simple Sort - the smallest sorting routine? awegel@arcor.de (Alex Wegel) - 2013-06-27 00:08 +0200
Re: Simple Sort - the smallest sorting routine? Doug Hoffman <glidedog@gmail.com> - 2013-06-26 19:31 -0400
Re: Simple Sort - the smallest sorting routine? Doug Hoffman <glidedog@gmail.com> - 2013-06-27 06:26 -0400
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-06-28 02:05 +0000
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-04 07:33 -0700
Re: Simple Sort - the smallest sorting routine? Coos Haak <chforth@hccnet.nl> - 2013-07-05 00:47 +0200
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-14 19:01 +0000
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-15 01:28 +0000
Re: Simple Sort - the smallest sorting routine? Ian Osgood <iano@quirkster.com> - 2013-07-19 11:29 -0700
Re: Simple Sort - the smallest sorting routine? Brad Eckert <hwfwguy@gmail.com> - 2013-07-19 09:09 -0700
csiph-web