Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.sys.apple2.programmer > #2499

Re: qsort for 65c02

From Scott Hemphill <hemphill@hemphills.net>
Newsgroups comp.sys.apple2.programmer
Subject Re: qsort for 65c02
References (3 earlier) <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> <a257fb9d-01bd-42d4-866a-1e99ca6d00d2@googlegroups.com>
Date 2016-03-13 09:03 -0400
Message-ID <87io0qlecw.fsf@hemphills.net> (permalink)

Show all headers | View raw

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

Back to comp.sys.apple2.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

qsort for 65c02 wssimms@gmail.com - 2016-03-10 07:34 -0800
  Re: qsort for 65c02 qkumba <peter.ferrie@gmail.com> - 2016-03-10 09:10 -0800
  Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-10 17:23 -0800
    Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-10 19:13 -0800
    Re: qsort for 65c02 "Michael J. Mahon" <mjmahon@aol.com> - 2016-03-10 19:37 -0800
      Re: qsort for 65c02 wssimms@gmail.com - 2016-03-10 21:37 -0800
        Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 12:43 -0800
          Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-11 15:48 -0600
            Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 20:59 -0800
              Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 21:13 -0800
                Re: qsort for 65c02 wssimms@gmail.com - 2016-03-11 21:19 -0800
          Re: qsort for 65c02 wssimms@gmail.com - 2016-03-12 07:15 -0800
            Re: qsort for 65c02 wssimms@gmail.com - 2016-03-12 07:25 -0800
            Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-12 11:22 -0600
            Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-12 10:00 -0800
              Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-12 14:09 -0600
              Re: qsort for 65c02 wssimms@gmail.com - 2016-03-12 22:17 -0800
                Re: qsort for 65c02 Scott Hemphill <hemphill@hemphills.net> - 2016-03-13 09:03 -0400
                Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-13 09:22 -0700
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-13 13:45 -0500
                Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-13 19:01 -0700
                Re: qsort for 65c02 wssimms@gmail.com - 2016-03-13 21:28 -0700
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
                Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-13 22:15 -0700
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-13 13:45 -0500
                Re: qsort for 65c02 wssimms@gmail.com - 2016-03-13 15:46 -0700
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
  Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-11 03:30 -0800
    Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 13:25 -0800
      Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-14 16:24 -0700
        Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 23:35 -0500
          Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-15 10:20 -0700
            Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-15 17:30 -0500
          Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-15 13:35 -0700
            Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-15 20:15 -0700
            Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-15 20:23 -0700
              Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-16 10:33 -0700
                Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 08:50 -0700
                Re: qsort for 65c02 David Schmidt <schmidtd@my-deja.com> - 2016-03-18 12:37 -0400
                Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 10:04 -0700
                Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-18 10:12 -0700
                Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 10:33 -0700
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-18 13:01 -0500
                Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 11:33 -0700
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-18 17:37 -0500
                Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-20 10:52 -0700
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-20 13:42 -0500
                Re: qsort for 65c02 D Finnigan <dog_cow@macgui.com> - 2016-03-20 19:05 +0000
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-20 15:37 -0500
                Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-20 13:33 -0700
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-20 15:53 -0500
                Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-20 18:40 -0700
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-21 01:40 -0500

csiph-web