Account Options

  1. Sign in
The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Google Groups Home
« Groups Home
comp.theory
+ new post
About this group
Subscribe to this group
This is a Usenet group - learn more
Message from discussion New Sorting Algorhithm 1-Pass Complete Sort!
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
Sean Lorber  
View profile  
 More options Feb 4 2002, 9:26 pm
Newsgroups: comp.theory
From: lorber_s...@hotmail.com (Sean Lorber)
Date: 4 Feb 2002 18:26:10 -0800
Local: Mon, Feb 4 2002 9:26 pm
Subject: Re: New Sorting Algorhithm 1-Pass Complete Sort!
Print | View thread | Show original | Report this message | Find messages by this author

"Dann Corbit" <dcor...@connx.com> wrote in message <news:a3mn1l01l0a@enews1.newsguy.com>...
> "Sean Lorber" <lorber_s...@hotmail.com> wrote in message
> news:e21e6ed5.0202020942.14467aa8@posting.google.com...
> > Dan,

> > I have read "The Art of Computer Programming" by Donald Knuth and
> > unless I missed something, he suggests counting identical keys to get
> > the bin size prior to sorting.  My algo does not need to do this.

> And the algorithm I posted does not need to allocate [besides the static
> array] any memory and makes exactly one pass over the data.  Unfortunately,
> both of our algorithms are fairly useless for general purpose sorting.  They
> work only for a special case.

Well that is without identical keys, is it not?

> > Can
> > you point me to a book which implements Radix with a single linked
> > list and no pre calculation of identical keys?

> No book needed.  I posted an algorithm that does exactly that.  Too bad it
> isn't worth the powder to blow it up with.

Why would you say that?  It's already 2x as fast as the current Radix
using Knuth's best solution.  It's certainly more efficient then
allocating memory (even if you sub allocate) and the amount of memory
needed is always the same:  N linked list elements.

Sean


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
©2013 Google