Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Just finished the fastest ever, general purpose sorting algorithm.
Replies: 29   Last Post: Jan 8, 2013 10:21 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
kiru.sengal@gmail.com

Posts: 29
Registered: 12/7/05
Re: Just finished the fastest ever, general purpose sorting algorithm.
Posted: Jan 8, 2013 9:18 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Monday, January 7, 2013 6:39:50 AM UTC-5, JT wrote:
> On 7 Jan, 07:17, forbisga...@gmail.com wrote:
>

> > On Sunday, January 6, 2013 7:32:45 PM UTC-8, JT wrote:
>
> > > No a dynamic alloc memory pointer solution using a binary tree will
>
> > > not have any empty indeces.
>
> >
>
> > Why do you think I pointed you at the page for the binary insertion sort?
>
> > How do you pass through the binary tree without comparisons?  Even if you
>
> > do dynamic leveling it takes time and the results will depend upon the order
>
> > in the "unordered" set.
>
> >
>
> > The old Burroughs DMSII database supported ISAM, B-tree, and hash access
>
> > methods to retrieve data.  Each had their place.  Hash was by far the fastest
>
> > access as long as one didn't have too many overflow pages but it wasn't very
>
> > good for sequential access of the data and the data wasn't ordered other than
>
> > by hash algorithm.
>
> >
>
> > It's interesting that SQLServer seems to handle ordered insertion into
>
> > a b-tree much faster than the Unisys DMSII did.  It seems to keep more
>
> > information lying around.  Maybe it just keeps more of the index in memory.
>
> > Back in the day 64K was a lot of memory, now we're thowing 10s of G at
>
> > machines.  I don't really know and don't care as long as the results
>
> > are satisfactorally fast.  I can import millions of records in a few
>
> > minutes and that's good enough.  I can keep several indexes on huge
>
> > tables and get the data back out very quickly.  That's good enough for
>
> > me.  I don't care to know the specifics of the system's internals unless
>
> > performance is suffering.
>
> >
>
> > You don't know what you're talking about.  You talk like a beginner.
>
> > I don't like responding this way to anyone because I don't like being
>
> > responded to this way by anyone.  Everyone's a beginner at something.
>
> > Go read up on sorts then try writing your own.  You're not up to speed
>
> > on the basics yet.  There's nothing worse than a rude beginner.
>
> http://en.wikipedia.org/wiki/Sorting_algorithm#Counting_sort
>
> Counting sort
>
> Main article: Counting sort
>
> Counting sort is applicable when each input is known to belong to a
>
> particular set, S, of possibilities. The algorithm runs in O(|S| + n)
>
> time and O(|S|) memory where n is the length of the input. It works by
>
> creating an integer array of size |S| and using the ith bin to count
>
> the occurrences of the ith member of S in the input. Each input is
>
> then counted by incrementing the value of its corresponding bin.
>
> Afterward, the counting array is looped through to arrange all of the
>
> inputs in order. This sorting algorithm cannot often be used because S
>
> needs to be reasonably small for it to be efficient, but the algorithm
>
> is extremely fast and demonstrates great asymptotic behavior as n
>
> increases. It also can be modified to provide stable behavior.
>
>
>
> ***So as you can see the implementation of this algoritm that i showed
>
> to numbnuts work in index style, by first counting occurences this
>
> means comparissons and have restrictions upon setsize(unique members)
>
> due to memory restrictions, and they ***will also have to sort those
>
> members after they have been counted in*** to their respective indexes
>
> in array. And this is very bad if all values have low number of
>
> occurences.
>
>
>
> As you can see my pet array algorithm do no such thing because it just
>
> use the array index so there will be no sort needed. Now the pet array
>
> algorithm of course have it weakness that possibly no more then 2^20
>
> elements can be created in most programming languages, this means
>
> without index approach only elements of max 2.5 character could be
>
> stored.
>
> And that would not be much use for sorting text (unless you chose the
>
> index solution).
>
>
>
> However a recursive pointer solution with digit branches do not need
>
> to allocate slots for null values so would not need to have any
>
> restrictions upon size of elements as long there is system memory to
>
> store each unique value and the occurences of it, so basicly anything
>
> can be indexed without any sort needed.


Can you prove that quicksort won't beat your algorithm like a drum on random input instances?

Benchmark it.


Date Subject Author
1/5/13
Read Just finished the fastest ever, general purpose sorting algorithm.
JT
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
David Bernier
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
Scott Berg
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/8/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
kiru.sengal@gmail.com
1/8/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
UpChunky
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.