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

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

Re: qsort for 65c02

Newsgroups comp.sys.apple2.programmer
Subject Re: qsort for 65c02
From Michael J. Mahon <mjmahon@aol.com>
References (7 earlier) <a257fb9d-01bd-42d4-866a-1e99ca6d00d2@googlegroups.com> <08136179-746a-4991-b236-86f54fa2ec8b@googlegroups.com> <JfSdne9ivfOoKHjLnZ2dnUU7-WHNnZ2d@giganews.com> <6976dd10-2d2c-432c-8601-827c062479dc@googlegroups.com> <daf4fcd4-b60f-4dd1-990f-704f21d86992@googlegroups.com>
Message-ID <bPadne64V-UGlnrLnZ2dnUU7-RtQAAAA@giganews.com> (permalink)
Date 2016-03-14 14:06 -0500

Show all headers | View raw

Michael Pohoreski <michael.pohoreski@gmail.com> wrote:
> On Sunday, March 13, 2016 at 7:01:15 PM UTC-7, gid...@sasktel.net wrote:
> 
>> Of all the years I have been programming, I have never come across a
>> radix sort in any language and on any computer, other than this one
>> little listing on a piece of crumpled magazine paper.  I'd like to get
>> the article that I got it from now, just to read.
> 
> In the games industry pre 2000 I've seen radix sort used in the days of
> software rendering to sort floats (polygon's vertices) in O(n) time.
> 
> The 3x memory space required makes it extremely slow on modern CPU's as
> the delta between CPU and Memory access speeds grew apart.
> 

3x seems a little extreme. I suppose it depends on the length of the
records compared to the length of a link. 

The only space required in addition to the items themselves is one link per
item. The bucket pointers (2 per bucket) are independent of the number of
items, and can be kept very reasonable by choosing a moderate number of
bits for the radix. 

In the common case of the input items already being a linked list, there is
no additional per item space needed, just two arrays of pointers with
length equal to the chosen radix. 
-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

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