Path: csiph.com!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!news.glorb.com!Xl.tags.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!news.giganews.com.POSTED!not-for-mail NNTP-Posting-Date: Sun, 13 Mar 2016 08:03:11 -0500 From: Scott Hemphill Newsgroups: comp.sys.apple2.programmer Subject: Re: qsort for 65c02 References: <21cdc87f-461c-4351-82d3-241a0c3689d4@googlegroups.com> <09f553ea-ec51-4742-a372-2ceb0bce4b8e@googlegroups.com> <56b96c23-bb76-4018-a32f-a86ee8b5691f@googlegroups.com> <1a698500-b4e6-4ef5-b545-9ed4730486c6@googlegroups.com> <59ac624e-a9ba-4d4a-8939-cbefd6ec37bf@googlegroups.com> <83649064-082a-4f0e-be6a-ce626c0d9c27@googlegroups.com> Reply-To: hemphill@alumni.caltech.edu Date: Sun, 13 Mar 2016 09:03:11 -0400 Message-ID: <87io0qlecw.fsf@hemphills.net> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) Cancel-Lock: sha1:+GuUpH9ZB90Hi+h05K9d8ezIpZk= MIME-Version: 1.0 Content-Type: text/plain Lines: 29 X-Usenet-Provider: http://www.giganews.com X-Trace: sv3-GQeJKtLVg8cF2fuH65eeB2vJBITBFl/dkP2kdyJr4ySaeyo1uedyFAozVUKgCCkO8O7jl4Lnrn6xdKX!h4N1c/JWTDNj0pQwRJ/vDnDAeqTOF29ayFYYqgQQSARBusSw3ow4kmA= X-Complaints-To: abuse@giganews.com X-DMCA-Notifications: http://www.giganews.com/info/dmca.html X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 2764 Xref: csiph.com comp.sys.apple2.programmer:2499 wssimms@gmail.com writes: > I couldn't quite figure out AM and BM myself, so I changed them to FM > (first character) and LM (last character). > > You are right about the increased number of buckets playing a large > role in the sort time. Of course that means an increased extra memory > requirement but as long as your got the variable space to spare that's > fine. > > As for the switch to binary search or qsort on the buckets, that's a > prinlet because it's really tough to binary search a linked > list. Instead you would just replace the linked list with a balanced > binary tree. That would speed things up a bit for larger N. > > But actually the idea of implementing balanced binary trees in > AppleSoft to speed up a string sort seems pretty comical to me. You've > got to draw a line somewhere on what's just not a great use of > AppleSoft and that's past the line for me :-) Unbalanced trees would be simpler to implement, and might be better for the relatively small number of records you would want to sort on a 6502. Both have poor behavior if the records are already in order, so you could shuffle the array first. :-) Scott -- Scott Hemphill hemphill@alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear