My Invention of "Bug Sort".

My Invention of "Bug Sort".

[Austin Obyrne]

Copyright © 2012 Austin O'Byrne.

Let us say that “NextNum” is a variable in a program output string that the user wants to sort at the end of the program run.

How it works.

Each change in ‘NextNum’ is trapped as it is computed by a ‘bug’ strategically placed in the lines of source code. 

Q := NextNum(I);
I_NUM(Q):= I_NUM(Q)+1;

(This is the bug)

The bug ‘gets’ (captures) the instantaneous value of NextNum as it materializes and then immediately writes this instantaneous value  to a dedicated array in order of *magnitude and returns for the next i.e. each value indexes its own place in the array ( *not in sequential order where the entries would be contiguous and remain unsorted – this is the most salient point for the reader to note).

 *This is defacto sorting per se.

It only needs to read back from the array to see the sorted string which can be anything up to 1 million or more elements sorted in a split second, to complete the task.

Discussion.

Although I do not yet have performance figures to hand I think I can safely say that this is super quick, super efficient sorting.

The method is hugely intrinsic to Ada and should be considered as a permanent part of the language mathematical library like say the ‘vector cross product’, trig functions, and calculus.  I am proposing that idea here and now if any reader wants to get behind it with me to promote the idea further to the powers that be in Ada.  I am retaining the copyright meanwhile.

I cannot see any of the synthetic algorithms like ‘quick sort’, ‘tree sort’ etc, coming even close to it.  I think this blows them all right out of the water.

I am developing the demonstration pilot programs (half way there) that I will be uploading to my site later for your perusal.

There will be,

1) An interactive real-time, separate numerical and alphanumerical working program.

2) Batch working in numerical and alphanumerical – i.e. reading in from external unsorted files and out-putting to other sorted external files.

A full description document will accompany the four uploaded programs in Ada that will have the compiler with them and are for free downloading.

I would like to corner this invention as being fundamentally an Ada feature – you guys should get behind it now if you know how to contact the Ada people who have the power to make changes to the language – I don’t. 

With both feet firmly on the ground I say this ‘sort’ method could become ubiquitous in the future and /or a bench mark for all other sort programs if they still exist.

Enjoy,

Austin O’Byrne ( aka - adacrypt).

Re: My Invention of "Bug Sort".

[Peter C. Chapin]

On 2012-06-19 03:13, Austin Obyrne wrote:

> Copyright � 2012 Austin O'Byrne.
>
> Let us say that �NextNum� is a variable in a program output string that the user wants to sort at the end of the program run.
>
> How it works.
>
> Each change in �NextNum� is trapped as it is computed by a �bug� strategically placed in the lines of source code.
>
> Q := NextNum(I);
> I_NUM(Q):= I_NUM(Q)+1;
>
> (This is the bug)
>
> The bug �gets� (captures) the instantaneous value of NextNum as it materializes and then immediately writes this instantaneous value  to a dedicated array in order of *magnitude and returns for the next i.e. each value indexes its own place in the array ( *not in sequential order where the entries would be contiguous and remain unsorted � this is the most salient point for the reader to note).
>
>   *This is defacto sorting per se.
>
> It only needs to read back from the array to see the sorted string which can be anything up to 1 million or more elements sorted in a split second, to complete the task.

I find your style of writing difficult to understand. However, if I 
follow what you are saying, you are talking about Radix Sort. That 
sorting method is O(n) instead of O(n log(n)) (which is the best 
attainable running time for a comparison sort). However in general it 
can have huge memory requirements and is really only practical in 
special cases.

Peter

Re: My Invention of "Bug Sort".

[Austin Obyrne]

On Tuesday, June 19, 2012 12:55:12 PM UTC+1, Peter C. Chapin wrote:
> On 2012-06-19 03:13, Austin Obyrne wrote:
> 
> > Copyright � 2012 Austin O'Byrne.
> >
> > Let us say that �NextNum� is a variable in a program output string that the user wants to sort at the end of the program run.
> >
> > How it works.
> >
> > Each change in �NextNum� is trapped as it is computed by a �bug� strategically placed in the lines of source code.
> >
> > Q := NextNum(I);
> > I_NUM(Q):= I_NUM(Q)+1;
> >
> > (This is the bug)
> >
> > The bug �gets� (captures) the instantaneous value of NextNum as it materializes and then immediately writes this instantaneous value  to a dedicated array in order of *magnitude and returns for the next i.e. each value indexes its own place in the array ( *not in sequential order where the entries would be contiguous and remain unsorted � this is the most salient point for the reader to note).
> >
> >   *This is defacto sorting per se.
> >
> > It only needs to read back from the array to see the sorted string which can be anything up to 1 million or more elements sorted in a split second, to complete the task.
> 
> I find your style of writing difficult to understand. However, if I 
> follow what you are saying, you are talking about Radix Sort. That 
> sorting method is O(n) instead of O(n log(n)) (which is the best 
> attainable running time for a comparison sort). However in general it 
> can have huge memory requirements and is really only practical in 
> special cases.
> 
> Peter

Hi Peter,

I have never heard of Radix Sort unitl you mention it now so I have checked it out on Wikipedia just to get an impression of how it works when compared to my Bug Sort.

That's a truly tortuous algorithm and I can see where the memory goes.

I only deal with whole numbers - integers and alphanumeric characters and the memory consumption is very much smaller - 10 megabytes does an awful lot of sorting i.e in normal situations this is quite little.

My interest is largely in cryptography which never uses anything but integers so you can see why my pre-occupation is with integers. 

There is no comparison as far as I can see between Radix Sort and Bug Sort but I take your point that something taht sorts float values on a basis of signicficant values must require a lot of memory.

If I had that problem I would look for a better solution beforehand.

Many thanks for your useful pointer.

Regards - Austin O'Byrne

Re: My Invention of "Bug Sort".

[ggsub]

On Tuesday, June 19, 2012 12:13:28 AM UTC-7, Austin Obyrne wrote:
> 
> Each change in ‘NextNum’ is trapped as it is computed by a ‘bug’ strategically placed in the lines of source code. 

"Bug" in engineering is a euphemism for "error"; this usage goes back at least to the 19th century. You might want to choose another name.

> Q := NextNum(I);
> I_NUM(Q):= I_NUM(Q)+1;

This is straightforward, and probably very good for your specific needs. Specialized sorting algorithms like this can do much better than general ones. Like all specialized algorithms, this one has a number of shortcomings as a general sorting algorithm, not least of which is its restriction to sorting values of discrete types only.

It is hardly instantaneous. A complexity analysis is interesting:

Most sorting algorithms' complexity analyses are based only on N, the number of values (the number of times Q gets a value in the example). This algorithm must also take into account the number of possible values Q may have. If Q is of type T, this is T'Pos (T'Last) - T'Pos (T'First) + 1. I'll call this value M. M may be less than, equal to, or greater than N. For convenience, I'll define

B = Max (M, N)

First, time complexity: The algorithm must initialize the array I_Num to all zeros; this is O(M). It then increments the corresponding value of I_Num for each value of Q encountered; this is O(N). Finally, it must traverse I_Num to do something with the resulting values; this is O(M). So the overall time complexity is O(B). Linear time complexity, which is very good. No general sorting algorithm is linear.

Now space complexity: The algorithm needs the space for I_Num, which is O(M). Depending on what you do with the results, you may need to transform I_Num into the corresponding sorted sequence. For example, if you're sorting the values (3, 7, 1), you often want to end up with an array (1 => 1, 2 => 3, 3 => 7). Such a sequence is O(N). So the space complexity is at least O(M), and may be O(N) (if that's larger). To be safe for all cases we must call it O(B). Several sorting algorithms have O(N) space requirements, so that's not necessarily a problem.

For the following discussions, I'll presume the following declarations:

Q     : TQ;
I_Num : array (TQ) of TI;

An implementation of this must take into account a number of factors specific to the problem being solved. TI must be large enough to hold the maximum number of times a given value of Q may occur, but small enough that I_Num can be declared. If a component of I_Num overflows, you'll either get incorrect results (TI is a modular integer type) or and exception (TI is a signed integer type).

I_Num'Size will be 2 ** (TQ'Size + TI'Size); that must fit in memory. If parts of I_Num have to be swapped to disk, this could result in absolute times slower than a general, in-place algorithm.

This could also be slower if M >> N.

This is a form of insertion sort, in which values are sorted as they are encountered. In this it is similar to an ordered-tree insertion sort, in which values are inserted into an ordered, balanced, binary tree (or equivalent structure) as they are encountered. This is another general sorting algorithm that is O(N log N).

An interesting approach, and probably well suited to your specific problem area, but I doubt it will replace general sort algorithms.

Re: My Invention of "Bug Sort".

[Martin Trenkmann]

On 06/19/2012 09:13 AM, Austin Obyrne wrote:
> Copyright � 2012 Austin O'Byrne.
>
> Let us say that �NextNum� is a variable in a program output string that the user wants to sort at the end of the program run.
>
> How it works.
>
> Each change in �NextNum� is trapped as it is computed by a �bug� strategically placed in the lines of source code.
>
> Q := NextNum(I);
> I_NUM(Q):= I_NUM(Q)+1;
>
> (This is the bug)
>
> The bug �gets� (captures) the instantaneous value of NextNum as it materializes and then immediately writes this instantaneous value  to a dedicated array in order of *magnitude and returns for the next i.e. each value indexes its own place in the array ( *not in sequential order where the entries would be contiguous and remain unsorted � this is the most salient point for the reader to note).
>
>   *This is defacto sorting per se.
>
> It only needs to read back from the array to see the sorted string which can be anything up to 1 million or more elements sorted in a split second, to complete the task.
>
> Discussion.
>
> Although I do not yet have performance figures to hand I think I can safely say that this is super quick, super efficient sorting.
>
> The method is hugely intrinsic to Ada and should be considered as a permanent part of the language mathematical library like say the �vector cross product�, trig functions, and calculus.  I am proposing that idea here and now if any reader wants to get behind it with me to promote the idea further to the powers that be in Ada.  I am retaining the copyright meanwhile.
>
> I cannot see any of the synthetic algorithms like �quick sort�, �tree sort� etc, coming even close to it.  I think this blows them all right out of the water.
>
> I am developing the demonstration pilot programs (half way there) that I will be uploading to my site later for your perusal.
>
> There will be,
>
> 1) An interactive real-time, separate numerical and alphanumerical working program.
>
> 2) Batch working in numerical and alphanumerical � i.e. reading in from external unsorted files and out-putting to other sorted external files.
>
> A full description document will accompany the four uploaded programs in Ada that will have the compiler with them and are for free downloading.
>
> I would like to corner this invention as being fundamentally an Ada feature � you guys should get behind it now if you know how to contact the Ada people who have the power to make changes to the language � I don�t.
>
> With both feet firmly on the ground I say this �sort� method could become ubiquitous in the future and /or a bench mark for all other sort programs if they still exist.
>
> Enjoy,
>
> Austin O�Byrne ( aka - adacrypt).

I think your approach is known as Bitmap Sort, which was originally 
described by John Bentley in his famous book "Programming Pearls".

Try a Google search for it or just check out my first two hits:

http://designingefficientsoftware.wordpress.com/2011/03/31/bitmap-sort/
http://www.stoimen.com/blog/2010/06/25/friday-algorithms-sorting-a-set-of-integers-far-quicker-than-quicksort/

Kind regards,
Martin Trenkmann

Re: My Invention of "Bug Sort".

[robin.vowels]

On Tuesday, 19 June 2012 17:13:28 UTC+10, Austin Obyrne  wrote:
> Copyright © 2012 Austin O'Byrne.
> 
> Let us say that “NextNum” is a variable in a program output string that the user wants to sort at the end of the program run.
> 
> How it works.
> 
> Each change in ‘NextNum’ is trapped as it is computed by a ‘bug’ strategically placed in the lines of source code. 
> 
> Q := NextNum(I);
> I_NUM(Q):= I_NUM(Q)+1;

How large is Q?

Re: My Invention of "Bug Sort".

[Austin Obyrne]

On Tuesday, June 19, 2012 11:39:07 PM UTC+1, (unknown) wrote:
> On Tuesday, June 19, 2012 12:13:28 AM UTC-7, Austin Obyrne wrote:
> > 
> > Each change in ‘NextNum’ is trapped as it is computed by a ‘bug’ strategically placed in the lines of source code. 
> 
> "Bug" in engineering is a euphemism for "error"; this usage goes back at least to the 19th century. You might want to choose another name.
> 
> > Q := NextNum(I);
> > I_NUM(Q):= I_NUM(Q)+1;
> 
> This is straightforward, and probably very good for your specific needs. Specialized sorting algorithms like this can do much better than general ones. Like all specialized algorithms, this one has a number of shortcomings as a general sorting algorithm, not least of which is its restriction to sorting values of discrete types only.
> 
> It is hardly instantaneous. A complexity analysis is interesting:
> 
> Most sorting algorithms' complexity analyses are based only on N, the number of values (the number of times Q gets a value in the example). This algorithm must also take into account the number of possible values Q may have. If Q is of type T, this is T'Pos (T'Last) - T'Pos (T'First) + 1. I'll call this value M. M may be less than, equal to, or greater than N. For convenience, I'll define
> 
> B = Max (M, N)
> 
> First, time complexity: The algorithm must initialize the array I_Num to all zeros; this is O(M). It then increments the corresponding value of I_Num for each value of Q encountered; this is O(N). Finally, it must traverse I_Num to do something with the resulting values; this is O(M). So the overall time complexity is O(B). Linear time complexity, which is very good. No general sorting algorithm is linear.
> 
> Now space complexity: The algorithm needs the space for I_Num, which is O(M). Depending on what you do with the results, you may need to transform I_Num into the corresponding sorted sequence. For example, if you're sorting the values (3, 7, 1), you often want to end up with an array (1 => 1, 2 => 3, 3 => 7). Such a sequence is O(N). So the space complexity is at least O(M), and may be O(N) (if that's larger). To be safe for all cases we must call it O(B). Several sorting algorithms have O(N) space requirements, so that's not necessarily a problem.
> 
> For the following discussions, I'll presume the following declarations:
> 
> Q     : TQ;
> I_Num : array (TQ) of TI;
> 
> An implementation of this must take into account a number of factors specific to the problem being solved. TI must be large enough to hold the maximum number of times a given value of Q may occur, but small enough that I_Num can be declared. If a component of I_Num overflows, you'll either get incorrect results (TI is a modular integer type) or and exception (TI is a signed integer type).
> 
> I_Num'Size will be 2 ** (TQ'Size + TI'Size); that must fit in memory. If parts of I_Num have to be swapped to disk, this could result in absolute times slower than a general, in-place algorithm.
> 
> This could also be slower if M >> N.
> 
> This is a form of insertion sort, in which values are sorted as they are encountered. In this it is similar to an ordered-tree insertion sort, in which values are inserted into an ordered, balanced, binary tree (or equivalent structure) as they are encountered. This is another general sorting algorithm that is O(N log N).
> 
> An interesting approach, and probably well suited to your specific problem area, but I doubt it will replace general sort algorithms.



<< This is straightforward, and probably very good for your specific needs.

I think this sums it up completely. I realise now that this is a can of worms when taken as general sort program and probably no better than any other.

I think the fact that it works concurrently with the main program amd requires no extra handling of data after it has been computed is a plus?.

Question: In a real world situation could this sort mechanism be done by a 'tasking' package in Ada. 

Many thanks for your excellent and informed analysis.

Austin O'Byrne

Many thanks for your excellent analysis

Re: My Invention of "Bug Sort".

[Austin Obyrne]

On Wednesday, June 20, 2012 1:11:27 AM UTC+1, (unknown) wrote:
> On Tuesday, 19 June 2012 17:13:28 UTC+10, Austin Obyrne  wrote:
> > Copyright © 2012 Austin O'Byrne.
> > 
> > Let us say that “NextNum” is a variable in a program output string that the user wants to sort at the end of the program run.
> > 
> > How it works.
> > 
> > Each change in ‘NextNum’ is trapped as it is computed by a ‘bug’ strategically placed in the lines of source code. 
> > 
> > Q := NextNum(I);
> > I_NUM(Q):= I_NUM(Q)+1;
> 
> How large is Q?

I am treating this sort program more as 'tool' for specific needs now rather than a general sort program following the analysis given me by the previous reader.

In answer to your question, Q is limited only by the computer capacity to provide memory as far as I can see. 

I have written some new "Theoretically Unbreakable" cryptography that is well proven and I was lookin at this as an enhancement which it still is of course but that is as far as it goes.  It may not compete (it might if it comes to that) with other sort programs when it is extended to the broader field of sorting all data types.

See "Skew Line Encryptions - The Eventual Cipher" on 
http://www.adacrypt.com/introduction.html 

This is downloadable and comes with the original compiler (older but perfectly ok) 

Thanks for your interest.

Austin.

Re: My Invention of "Bug Sort".

[Austin Obyrne]

On Tuesday, June 19, 2012 11:39:07 PM UTC+1, (unknown) wrote:
> On Tuesday, June 19, 2012 12:13:28 AM UTC-7, Austin Obyrne wrote:
> > 
> > Each change in ‘NextNum’ is trapped as it is computed by a ‘bug’ strategically placed in the lines of source code. 
> 
> "Bug" in engineering is a euphemism for "error"; this usage goes back at least to the 19th century. You might want to choose another name.
> 
> > Q := NextNum(I);
> > I_NUM(Q):= I_NUM(Q)+1;
> 
> This is straightforward, and probably very good for your specific needs. Specialized sorting algorithms like this can do much better than general ones. Like all specialized algorithms, this one has a number of shortcomings as a general sorting algorithm, not least of which is its restriction to sorting values of discrete types only.
> 
> It is hardly instantaneous. A complexity analysis is interesting:
> 
> Most sorting algorithms' complexity analyses are based only on N, the number of values (the number of times Q gets a value in the example). This algorithm must also take into account the number of possible values Q may have. If Q is of type T, this is T'Pos (T'Last) - T'Pos (T'First) + 1. I'll call this value M. M may be less than, equal to, or greater than N. For convenience, I'll define
> 
> B = Max (M, N)
> 
> First, time complexity: The algorithm must initialize the array I_Num to all zeros; this is O(M). It then increments the corresponding value of I_Num for each value of Q encountered; this is O(N). Finally, it must traverse I_Num to do something with the resulting values; this is O(M). So the overall time complexity is O(B). Linear time complexity, which is very good. No general sorting algorithm is linear.
> 
> Now space complexity: The algorithm needs the space for I_Num, which is O(M). Depending on what you do with the results, you may need to transform I_Num into the corresponding sorted sequence. For example, if you're sorting the values (3, 7, 1), you often want to end up with an array (1 => 1, 2 => 3, 3 => 7). Such a sequence is O(N). So the space complexity is at least O(M), and may be O(N) (if that's larger). To be safe for all cases we must call it O(B). Several sorting algorithms have O(N) space requirements, so that's not necessarily a problem.
> 
> For the following discussions, I'll presume the following declarations:
> 
> Q     : TQ;
> I_Num : array (TQ) of TI;
> 
> An implementation of this must take into account a number of factors specific to the problem being solved. TI must be large enough to hold the maximum number of times a given value of Q may occur, but small enough that I_Num can be declared. If a component of I_Num overflows, you'll either get incorrect results (TI is a modular integer type) or and exception (TI is a signed integer type).
> 
> I_Num'Size will be 2 ** (TQ'Size + TI'Size); that must fit in memory. If parts of I_Num have to be swapped to disk, this could result in absolute times slower than a general, in-place algorithm.
> 
> This could also be slower if M >> N.
> 
> This is a form of insertion sort, in which values are sorted as they are encountered. In this it is similar to an ordered-tree insertion sort, in which values are inserted into an ordered, balanced, binary tree (or equivalent structure) as they are encountered. This is another general sorting algorithm that is O(N log N).
> 
> An interesting approach, and probably well suited to your specific problem area, but I doubt it will replace general sort algorithms.



Re Your suggestion:  "Bug" in engineering is a euphemism for "error";

I agree this needs to be changed.

I originally thought of "Tag Sort" but this clashes with 'tag' in Ada terminology.

I'm considering "Cell Sort" (<= elements of an array),"Trap Sort" (<= data is systematically trapped), "Abstraction Sort" (<= data is abstracted from the stream of data being assigned to the variable during runtime of the host program.

Would any of these clash with other sort program tiles known to you?

Your suggestion on one of these names would be greatly appreciated.

I am treating my invention now as more of an application (a tool)to specific problems rather than a general method in all of mathematics. 

I still see it as a tool specific to each language in programming while not being acceptable as an infinite principle or theorem in mathematics 
.

I sincerely hope you take the time to reply to this.


Austin O'Byrne. 

Re: My Invention of "Bug Sort".

[Manuel Collado]

El 20/06/2012 12:57, Austin Obyrne escribi�:
> ...
> Re Your suggestion:  "Bug" in engineering is a euphemism for
> "error";
>
> I agree this needs to be changed.
>
> I originally thought of "Tag Sort" but this clashes with 'tag' in Ada
> terminology.
>
> I'm considering "Cell Sort" (<= elements of an array),"Trap Sort" (<=
> data is systematically trapped), "Abstraction Sort" (<= data is
> abstracted from the stream of data being assigned to the variable
> during runtime of the host program.
>
> Would any of these clash with other sort program tiles known to you?
>
> Your suggestion on one of these names would be greatly appreciated.

http://en.wikipedia.org/wiki/Bucket_sort

-- 
Manuel Collado - http://lml.ls.fi.upm.es/~mcollado

Re: My Invention of "Bug Sort".

[Manuel Collado]

El 20/06/2012 14:47, Manuel Collado escribi�:
> El 20/06/2012 12:57, Austin Obyrne escribi�:
>> ...
>> Re Your suggestion: "Bug" in engineering is a euphemism for
>> "error";
>>
>> I agree this needs to be changed.
>>
>> I originally thought of "Tag Sort" but this clashes with 'tag' in Ada
>> terminology.
>>
>> I'm considering "Cell Sort" (<= elements of an array),"Trap Sort" (<=
>> data is systematically trapped), "Abstraction Sort" (<= data is
>> abstracted from the stream of data being assigned to the variable
>> during runtime of the host program.
>>
>> Would any of these clash with other sort program tiles known to you?
>>
>> Your suggestion on one of these names would be greatly appreciated.
>
> http://en.wikipedia.org/wiki/Bucket_sort
>

More precisely:

http://en.wikipedia.org/wiki/Pigeonhole_sort

-- 
Manuel Collado - http://lml.ls.fi.upm.es/~mcollado

Re: My Invention of "Bug Sort".

[Manuel Collado]

El 20/06/2012 14:51, Manuel Collado escribi�:
> El 20/06/2012 14:47, Manuel Collado escribi�:
>> El 20/06/2012 12:57, Austin Obyrne escribi�:
>>> ...
>>> Re Your suggestion: "Bug" in engineering is a euphemism for
>>> "error";
>>>
>>> I agree this needs to be changed.
>>>
>>> I originally thought of "Tag Sort" but this clashes with 'tag' in Ada
>>> terminology.
>>>
>>> I'm considering "Cell Sort" (<= elements of an array),"Trap Sort" (<=
>>> data is systematically trapped), "Abstraction Sort" (<= data is
>>> abstracted from the stream of data being assigned to the variable
>>> during runtime of the host program.
>>>
>>> Would any of these clash with other sort program tiles known to you?
>>>
>>> Your suggestion on one of these names would be greatly appreciated.
>>
>> http://en.wikipedia.org/wiki/Bucket_sort
>>
>
> More precisely:
>
> http://en.wikipedia.org/wiki/Pigeonhole_sort

Ooops!. Should be:

http://en.wikipedia.org/wiki/Counting_sort

The original algorithm dates back to 1954. See ref. 8.

-- 
Manuel Collado - http://lml.ls.fi.upm.es/~mcollado

Re: My Invention of "Bug Sort".

[Austin Obyrne]

On Wednesday, June 20, 2012 1:51:10 PM UTC+1, Manuel Collado wrote:
> El 20/06/2012 14:47, Manuel Collado escribió:
> > El 20/06/2012 12:57, Austin Obyrne escribió:
> >> ...
> >> Re Your suggestion: "Bug" in engineering is a euphemism for
> >> "error";
> >>
> >> I agree this needs to be changed.
> >>
> >> I originally thought of "Tag Sort" but this clashes with 'tag' in Ada
> >> terminology.
> >>
> >> I'm considering "Cell Sort" (<= elements of an array),"Trap Sort" (<=
> >> data is systematically trapped), "Abstraction Sort" (<= data is
> >> abstracted from the stream of data being assigned to the variable
> >> during runtime of the host program.
> >>
> >> Would any of these clash with other sort program tiles known to you?
> >>
> >> Your suggestion on one of these names would be greatly appreciated.
> >
> > http://en.wikipedia.org/wiki/Bucket_sort
> >
> 
> More precisely:
> 
> http://en.wikipedia.org/wiki/Pigeonhole_sort
> 
> -- 
> Manuel Collado - http://lml.ls.fi.upm.es/~mcollado

Many thanks for this.

I think there is much of a muchness in all of these fine programs.  I guess we all want to be able to say we have invented the best program but this is more an elite group of similar programs from what I can see.

I am claiming that the only restriction to my version of this sort program type is the data type is discrete.

Many thanks for your contibution to my education of sort programs.

Regards - Austin.

Re: My Invention of "Bug Sort".

[ggsub]

On Wednesday, June 20, 2012 3:57:55 AM UTC-7, Austin Obyrne wrote:
> 
> Your suggestion on one of these names would be greatly appreciated.

As Collado pointed out, this is an implementation of Counting Sort.

The extension of sorting algorithms to arrays indexed by non-numeric discrete types (in languages that support them) is obvious and well established. I first encountered it in Pascal in the late 1970s.

--
Jeff Carter
jrcarter commercial-at-sign acm (period | full stop) org

Re: My Invention of "Bug Sort".

[ggsub]

On Wednesday, June 20, 2012 1:32:44 AM UTC-7, Austin Obyrne wrote:
> 
> I think this sums it up completely. I realise now that this is a can of worms when taken as general sort program and probably no better than any other.

Since it takes linear time O(B), it's faster than any comparison sort, the best of which are O(N log N).

> Question: In a real world situation could this sort mechanism be done by a 'tasking' package in Ada. 

Parallelizing this algorithm is straightforward; there's a discussion of it in the Wikipedia page on counting sort.

--
Jeff Carter
jrcarter commercial-at-sign acm (period | full stop) org

Re: My Invention of "Bug Sort".

[Austin Obyrne]

On Tuesday, June 19, 2012 11:39:07 PM UTC+1, Jeffrey R. Carter wrote:
> On Tuesday, June 19, 2012 12:13:28 AM UTC-7, Austin Obyrne wrote:
> > 
> > Each change in ‘NextNum’ is trapped as it is computed by a ‘bug’ strategically placed in the lines of source code. 
> 
> "Bug" in engineering is a euphemism for "error"; this usage goes back at least to the 19th century. You might want to choose another name.
> 
> > Q := NextNum(I);
> > I_NUM(Q):= I_NUM(Q)+1;
> 
> This is straightforward, and probably very good for your specific needs. Specialized sorting algorithms like this can do much better than general ones. Like all specialized algorithms, this one has a number of shortcomings as a general sorting algorithm, not least of which is its restriction to sorting values of discrete types only.
> 
> It is hardly instantaneous. A complexity analysis is interesting:
> 
> Most sorting algorithms' complexity analyses are based only on N, the number of values (the number of times Q gets a value in the example). This algorithm must also take into account the number of possible values Q may have. If Q is of type T, this is T'Pos (T'Last) - T'Pos (T'First) + 1. I'll call this value M. M may be less than, equal to, or greater than N. For convenience, I'll define
> 
> B = Max (M, N)
> 
> First, time complexity: The algorithm must initialize the array I_Num to all zeros; this is O(M). It then increments the corresponding value of I_Num for each value of Q encountered; this is O(N). Finally, it must traverse I_Num to do something with the resulting values; this is O(M). So the overall time complexity is O(B). Linear time complexity, which is very good. No general sorting algorithm is linear.
> 
> Now space complexity: The algorithm needs the space for I_Num, which is O(M). Depending on what you do with the results, you may need to transform I_Num into the corresponding sorted sequence. For example, if you're sorting the values (3, 7, 1), you often want to end up with an array (1 => 1, 2 => 3, 3 => 7). Such a sequence is O(N). So the space complexity is at least O(M), and may be O(N) (if that's larger). To be safe for all cases we must call it O(B). Several sorting algorithms have O(N) space requirements, so that's not necessarily a problem.
> 
> For the following discussions, I'll presume the following declarations:
> 
> Q     : TQ;
> I_Num : array (TQ) of TI;
> 
> An implementation of this must take into account a number of factors specific to the problem being solved. TI must be large enough to hold the maximum number of times a given value of Q may occur, but small enough that I_Num can be declared. If a component of I_Num overflows, you'll either get incorrect results (TI is a modular integer type) or and exception (TI is a signed integer type).
> 
> I_Num'Size will be 2 ** (TQ'Size + TI'Size); that must fit in memory. If parts of I_Num have to be swapped to disk, this could result in absolute times slower than a general, in-place algorithm.
> 
> This could also be slower if M >> N.
> 
> This is a form of insertion sort, in which values are sorted as they are encountered. In this it is similar to an ordered-tree insertion sort, in which values are inserted into an ordered, balanced, binary tree (or equivalent structure) as they are encountered. This is another general sorting algorithm that is O(N log N).
> 
> An interesting approach, and probably well suited to your specific problem area, but I doubt it will replace general sort algorithms.

<<<<<< This is another general sorting algorithm that is O(N log N). 

 I don't have the time to digress into a study of how this is arrived at so could I ask you to fill me briefly as follows.

1) Does this take into account repeats of elemental numbers or does it assume no repeats in a sample.

2 ) In "O(N log N)" do I assume log to the base 'e' or what. 

3) Is 'N' the sample length or the array length.

Thanks in anticipation - Austin O'Byrne

Re: My Invention of "Bug Sort".

[Jeffrey R. Carter]

On Wednesday, June 20, 2012 4:59:24 PM UTC-7, Austin Obyrne wrote:
> 
> <<<<<< This is another general sorting algorithm that is O(N log N). 
> 
>  I don't have the time to digress into a study of how this is arrived at so could I ask you to fill me briefly as follows.
> 
> 1) Does this take into account repeats of elemental numbers or does it assume no repeats in a sample.

It is irrespective of whether or not a value occurs more than once.

> 2 ) In "O(N log N)" do I assume log to the base 'e' or what. 

In "Big-O" notation, log is understood to be to the base 2.

> 3) Is 'N' the sample length or the array length.

Typically in comparison sorts the 2 are the same, but N refers to the number of values being sorted.

Re: My Invention of "Bug Sort".

[Simon Wright]

"Jeffrey R. Carter" <ggsub@pragmada.co.cc> writes:

>> 2 ) In "O(N log N)" do I assume log to the base 'e' or what. 
>
> In "Big-O" notation, log is understood to be to the base 2.

Isn't there a constant factor between log2(x) and ln(x)? Which is taken
up in the O?

   N = e**x = 2**y

Taking natural logs,

   ln N = x = y.ln 2

Re: My Invention of "Bug Sort".

[Manuel Collado]

El 21/06/2012 7:13, Simon Wright escribi�:
> "Jeffrey R. Carter"<ggsub@pragmada.co.cc>  writes:
>
>>> 2 ) In "O(N log N)" do I assume log to the base 'e' or what.
>>
>> In "Big-O" notation, log is understood to be to the base 2.
>
> Isn't there a constant factor between log2(x) and ln(x)? Which is taken
> up in the O?
>
>     N = e**x = 2**y
>
> Taking natural logs,
>
>     ln N = x = y.ln 2

Yes. In "Big-O" notation, the base for log() is irrelevant.

   O(log N) = O(ln N)

Both expressions denote exactly the same set of functions.

-- 
Manuel Collado - http://lml.ls.fi.upm.es/~mcollado

Re: My Invention of "Bug Sort".

[Austin Obyrne]

On Thursday, June 21, 2012 2:17:52 AM UTC+1, Jeffrey R. Carter wrote:
> On Wednesday, June 20, 2012 4:59:24 PM UTC-7, Austin Obyrne wrote:
> > 
> > <<<<<< This is another general sorting algorithm that is O(N log N). 
> > 
> >  I don't have the time to digress into a study of how this is arrived at so could I ask you to fill me briefly as follows.
> > 
> > 1) Does this take into account repeats of elemental numbers or does it assume no repeats in a sample.
> 
> It is irrespective of whether or not a value occurs more than once.
> 
> > 2 ) In "O(N log N)" do I assume log to the base 'e' or what. 
> 
> In "Big-O" notation, log is understood to be to the base 2.
> 
> > 3) Is 'N' the sample length or the array length.
> 
> Typically in comparison sorts the 2 are the same, but N refers to the number of values being sorted.

Many thanks for that.

I realise now you have said it (it's coming back to me )that Big O is complexity notation.

I understand it all beter now.

I'm a retired ships' engineer (pensioner) so you will undertsand why I am not as au fait as you guys who are 'hands-on' so speak exponents.

This has been an enlightening experience in sorting techniques.

My interest in cryptography brought me to sorting only after I notice an implementation to sorting in Ada. Serendipity you might say with some generosity.

Summarising.

I have uncovered an implementaion in Ada of an existing sort type program.

I consider this a rather novel use of the language that is extensible to other languages - it is not important that this is not groundbreaking stuff after but I will continue with my demonstration programs in case anybody is interested. 


Really grateful,

Austin O'Byrne

Re: My Invention of "Bug Sort".

[Austin Obyrne]

On Thursday, June 21, 2012 8:23:12 AM UTC+1, Manuel Collado wrote:
> El 21/06/2012 7:13, Simon Wright escribió:
> > "Jeffrey R. Carter"<ggsub@pragmada.co.cc>  writes:
> >
> >>> 2 ) In "O(N log N)" do I assume log to the base 'e' or what.
> >>
> >> In "Big-O" notation, log is understood to be to the base 2.
> >
> > Isn't there a constant factor between log2(x) and ln(x)? Which is taken
> > up in the O?
> >
> >     N = e**x = 2**y
> >
> > Taking natural logs,
> >
> >     ln N = x = y.ln 2
> 
> Yes. In "Big-O" notation, the base for log() is irrelevant.
> 
>    O(log N) = O(ln N)
> 
> Both expressions denote exactly the same set of functions.
> 
> -- 
> Manuel Collado - http://lml.ls.fi.upm.es/~mcollado

---------------


This is surprising to me - is it right?

<<Yes. In "Big-O" notation, the base for log() is irrelevant. 

   << O(log N) = O(ln N) 

<< Both expressions denote exactly the same set of functions. 

In general,

A change of base in logarithms:

Log(base(a)M = Log (base(b))M / Log (base(b))'a'.

Applying that,In particular here,

Ln of N = Log2N / Ln 2


Unless it is true that there is some constant incorporated in O that verifies this, then

N(Ln N) /=  N(Log2 N)

Which is it?

On face value it appears totally incorrect arithmetically, I'm surprised that such an anomaly would be acceptable. 

Austin O'Byrne

Re: My Invention of "Bug Sort".

[Dmitry A. Kazakov]

On Thu, 21 Jun 2012 04:50:34 -0700 (PDT), Austin Obyrne wrote:

> On Thursday, June 21, 2012 8:23:12 AM UTC+1, Manuel Collado wrote:
>> El 21/06/2012 7:13, Simon Wright escribi�:
>>> "Jeffrey R. Carter"<ggsub@pragmada.co.cc>  writes:
>>>
>>>>> 2 ) In "O(N log N)" do I assume log to the base 'e' or what.
>>>>
>>>> In "Big-O" notation, log is understood to be to the base 2.
>>>
>>> Isn't there a constant factor between log2(x) and ln(x)? Which is taken
>>> up in the O?
>>>
>>>     N = e**x = 2**y
>>>
>>> Taking natural logs,
>>>
>>>     ln N = x = y.ln 2
>> 
>> Yes. In "Big-O" notation, the base for log() is irrelevant.
>> 
>>    O(log N) = O(ln N)
>> 
>> Both expressions denote exactly the same set of functions.

> This is surprising to me - is it right?

Yes, O(nX)=O(Y) for all n>0.

O(f)=O(g) when lim f/g exists, finite, non-zero.

http://en.wikipedia.org/wiki/Big_O_notation

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: My Invention of "Bug Sort".

[Adam Beneschan]

On Wednesday, June 20, 2012 10:13:48 PM UTC-7, Simon Wright wrote:
> "Jeffrey R. Carter" writes:
> 
> >> 2 ) In "O(N log N)" do I assume log to the base 'e' or what. 
> >
> > In "Big-O" notation, log is understood to be to the base 2.
> 
> Isn't there a constant factor between log2(x) and ln(x)? Which is taken
> up in the O?

log[b] (x) = ln(x)/ln(b) for any base b.  So, yes, the base doesn't matter in O notation.  

                         -- Adam

Re: My Invention of "Bug Sort".

[Jeffrey Carter]

On 06/20/2012 10:13 PM, Simon Wright wrote:
>
> Isn't there a constant factor between log2(x) and ln(x)? Which is taken
> up in the O?
>
>     N = e**x = 2**y
>
> Taking natural logs,
>
>     ln N = x = y.ln 2

My mistake. I'd always heard it referred to as log base 2, but as you point out, 
the base is irrelevant.

-- 
Jeff Carter
"Death awaits you all, with nasty, big, pointy teeth!"
Monty Python & the Holy Grail
20

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

Re: My Invention of "Bug Sort".

[Jeffrey Carter]

On 06/21/2012 04:50 AM, Austin Obyrne wrote:
>
> In general,
>
> A change of base in logarithms:
>
> Log(base(a)M = Log (base(b))M / Log (base(b))'a'.
>
> Applying that,In particular here,
>
> Ln of N = Log2N / Ln 2

No. log2 N = ln N / ln 2, so ln N = log2 N � ln 2. Not that it matters to Big-O 
notation.

> Unless it is true that there is some constant incorporated in O that verifies this, then
>
> N(Ln N) /=  N(Log2 N)
>
> Which is it?
>
> On face value it appears totally incorrect arithmetically, I'm surprised that such an anomaly would be acceptable.

Big-O notation is about the order of the complexity, not its exact value. If you 
have a super fast algorithm that only does 1 pass over the data, it takes time 
proportional to N. A slower algorithm that makes 2 passes over the data takes 
time proportional to 2N. Both have time complexity of O(N); a constant factor 
doesn't affect the Big-O value.

Another way to think about it is that Big-O indicates how the time required 
increases as N increases, not what the time is for a specific value of N.

-- 
Jeff Carter
"Death awaits you all, with nasty, big, pointy teeth!"
Monty Python & the Holy Grail
20

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

Re: My Invention of "Bug Sort".

[Austin Obyrne]

On Thursday, June 21, 2012 7:45:21 PM UTC+1, Jeffrey Carter wrote:
> On 06/21/2012 04:50 AM, Austin Obyrne wrote:
> >
> > In general,
> >
> > A change of base in logarithms:
> >
> > Log(base(a)M = Log (base(b))M / Log (base(b))'a'.
> >
> > Applying that,In particular here,
> >
> > Ln of N = Log2N / Ln 2
> 
> No. log2 N = ln N / ln 2, so ln N = log2 N • ln 2. Not that it matters to Big-O 
> notation.
> 
> > Unless it is true that there is some constant incorporated in O that verifies this, then
> >
> > N(Ln N) /=  N(Log2 N)
> >
> > Which is it?
> >
> > On face value it appears totally incorrect arithmetically, I'm surprised that such an anomaly would be acceptable.
> 
> Big-O notation is about the order of the complexity, not its exact value. If you 
> have a super fast algorithm that only does 1 pass over the data, it takes time 
> proportional to N. A slower algorithm that makes 2 passes over the data takes 
> time proportional to 2N. Both have time complexity of O(N); a constant factor 
> doesn't affect the Big-O value.
> 
> Another way to think about it is that Big-O indicates how the time required 
> increases as N increases, not what the time is for a specific value of N.
> 
> -- 
> Jeff Carter
> "Death awaits you all, with nasty, big, pointy teeth!"
> Monty Python & the Holy Grail
> 20
> 
> --- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

Must check out my change of base algorithm sometime soon.

But as you point out this is not absolute but relative conjecture -i.e. its the order of the rate of change that is meaningful but more as a philosophy than a mathematicaly computed result - i.e. There is no unit of complexity as far as I can see ???

Austin O'Byrne

Re: My Invention of "Bug Sort".

[Randy Brukardt]

"Austin Obyrne" <austin.obyrne@hotmail.com> wrote in message 
news:5b936896-12fb-4238-a5a7-3851f1959d0b@googlegroups.com...
...
>I am claiming that the only restriction to my version of this sort program 
>type is the data type is discrete.

You could get rid of that restriction if you stored the items in a hashed or 
ordered map container. (But that probably would be a lot slower than using 
an array, O(log N) for the ordered map.) A map container can be thought of 
as an array indexed by any type that you want (including indefinite ones 
like String).

                                  Randy.

Re: My Invention of "Bug Sort".

[Randy Brukardt]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1389 bytes --]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:1u9ig9nnen59q$.ajozwlsekr7l.dlg@40tude.net...
> On Thu, 21 Jun 2012 04:50:34 -0700 (PDT), Austin Obyrne wrote:
>
>> On Thursday, June 21, 2012 8:23:12 AM UTC+1, Manuel Collado wrote:
>>> El 21/06/2012 7:13, Simon Wright escribi�:
>>>> "Jeffrey R. Carter"<ggsub@pragmada.co.cc>  writes:
>>>>
>>>>>> 2 ) In "O(N log N)" do I assume log to the base 'e' or what.
>>>>>
>>>>> In "Big-O" notation, log is understood to be to the base 2.
>>>>
>>>> Isn't there a constant factor between log2(x) and ln(x)? Which is taken
>>>> up in the O?
>>>>
>>>>     N = e**x = 2**y
>>>>
>>>> Taking natural logs,
>>>>
>>>>     ln N = x = y.ln 2
>>>
>>> Yes. In "Big-O" notation, the base for log() is irrelevant.
>>>
>>>    O(log N) = O(ln N)
>>>
>>> Both expressions denote exactly the same set of functions.
>
>> This is surprising to me - is it right?
>
> Yes, O(nX)=O(Y) for all n>0.
>
> O(f)=O(g) when lim f/g exists, finite, non-zero.
>
> http://en.wikipedia.org/wiki/Big_O_notation

Or, if you want a directly relevant reference, see A.18(3-4/2) in Ada 2005 
or Ada 2012.

http://www.ada-auth.org/standards/12rm/html/RM-A-18.html#p3

(I'm sure the wikipedia article is less terse, but I wanted to point out 
that this is defined in the Ada Standard as well as common programming 
analysis.)

                          Randy.

Re: My Invention of "Bug Sort".

[Simon Wright]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> Or, if you want a directly relevant reference, see A.18(3-4/2) in Ada
> 2005 or Ada 2012.
>
> http://www.ada-auth.org/standards/12rm/html/RM-A-18.html#p3

I notice http://www.ada-auth.org/standards/12rm/html/RM-A-18.html#p5 -
the last part of this is very terse. Wikipedia suggests that "(or both)"
should be added. But I'm still baffled; and this paragraph appears to be
for users, not implementers!

Re: My Invention of "Bug Sort".

[Randy Brukardt]

"Simon Wright" <simon@pushface.org> wrote in message 
news:m2sjdnyrlh.fsf@pushface.org...
...
> I notice http://www.ada-auth.org/standards/12rm/html/RM-A-18.html#p5 -
> the last part of this is very terse. Wikipedia suggests that "(or both)"
> should be added. But I'm still baffled; and this paragraph appears to be
> for users, not implementers!

This is the definition of "strict weak ordering", it is described as 
precisely as possible. There's nothing really here for users; I don't think 
its possible to define this informally and have it make any sense. I have no 
idea where you are adding "or both", but if it is to the end of the 
sentence, it's unnecessary as the truth table for "or" includes True or True 
= True. "or" is not "xor"! (I realize that when writing English, there is an 
ambiguity - "or" sometimes is taken to mean "xor". That might explain why 
wikipedia would say that. But this is an Ada text, and "or" is well-defined 
here - and it's not "xor"!!)

As to why you're baffled, I can't say; this is pretty straightforward 
algebra. What else could this say? (Without the "strict weak ordering" 
requirement, it's impossible to have a complete ordering and we cannot 
expect implementations to do sensible things in that case.)

                                      Randy.

Re: My Invention of "Bug Sort".

[Niklas Holsti]

On 12-06-27 01:29 , Randy Brukardt wrote:
> "Simon Wright"<simon@pushface.org>  wrote in message
> news:m2sjdnyrlh.fsf@pushface.org...
> ...
>> I notice http://www.ada-auth.org/standards/12rm/html/RM-A-18.html#p5 -
>> the last part of this is very terse. Wikipedia suggests that "(or both)"
>> should be added.  But I'm still baffled; and this paragraph appears to be
>> for users, not implementers!
>
> This is the definition of "strict weak ordering", it is described as
> precisely as possible. There's nothing really here for users;

A user (programmer) using Ada.Containers and providing an actual Boolean 
function for "<" must make sure that this actual function obeys this 
rule; otherwise the container may not work as intended (as Randy said). 
So *in principle* users need to understand this.

The first three rules (with names, even more terse) are simple to 
understand, because they are familiar properties from the usual complete 
ordering of numbers and strings:

- irreflexive: x < x must be False for all values x.
- asymmetric: if x < y is True, then y < x must be False.
- transitive: if x < y is True, and y < z is True, then x < z must be 
True also.

It is the fourth rule that is tricky, because it is important only when 
there are incomparable (but different) values x and y for which neither 
x < y nor y < x is True. If we use the symbol x # y for this 
"incomparability" relation between x and y, the fourth rule can be 
stated as: the relation # is an equivalence relation (a reflexive and 
transitive relation).

The reflexivity of # follows directly from the irreflexivity assumed for 
"<"; the transitivity follows from the fourth rule for "<".

For me, the rule "incomparability is an equivalence" is more intuitively 
understandable than the formulation in the RM. The RM rule is easier to 
state directly, however. That incomparability is an equivalence relation 
comes out in the name of the function 
Ada.Containers.Ordered_Maps.Equivalent_Keys.

In practice, the fourth rule comes into play when the 
programmer-supplied actual "<" function depends on only a part of the 
compared values, for example, on only one "key" component of a record 
type. If two record values x and y have the same key, x.key = y.key, 
then neither is "<" than the other, but they can still be different if 
they have different values in their other components.

*In practice* I expect most programmer-supplied "<" functions will 
compare one or a few "key" components of the operands. As long as each 
invocation of "<" compares the same components of the operands, in the 
same way, giving a complete ordering of these component values, the 
fourth rule holds and the container should work. So perhaps most users 
can get away with ignoring this rule.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: My Invention of "Bug Sort".

[Simon Wright]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "Simon Wright" <simon@pushface.org> wrote in message 
> news:m2sjdnyrlh.fsf@pushface.org...
> ...
>> I notice http://www.ada-auth.org/standards/12rm/html/RM-A-18.html#p5 -
>> the last part of this is very terse. Wikipedia suggests that "(or both)"
>> should be added. But I'm still baffled; and this paragraph appears to be
>> for users, not implementers!
>
> This is the definition of "strict weak ordering", it is described as 
> precisely as possible. There's nothing really here for users; I don't think 
> its possible to define this informally and have it make any sense.

As Niklas has noted, the implementer doesn't provide the ordering
function and can't control it. The only people who need to decide
whether the ordering function is OK are the developers (which is the
group I meant by "users"; the users of the compiler).

It may be necessary to understand this definition if you are a compiler
writer, but there are going to be a lot of developers who will have real
trouble with it. Including me (I was a physicist, not a
mathematician). I think the Standard would be better without the last
sentence of (5); give us a reference if you like.

The RM says 'if x < y for any values x and y, then for all other values
z, (x < z) or (z < y).'.

Wikipedia[1] says 'in which the relation "neither a < b nor b < a" is
transitive", which seems a lot clearer to me.

Wikipedia[2] lists as the fourth condition 'For all x, y, and z, if x is
incomparable with y, and y is incomparable with z, then x is
incomparable with z (transitivity of equivalence).' which is also clear,
aside from the use of 'incomparable' to mean, I think, 'equivalent'.

[1] http://en.wikipedia.org/wiki/Strict_weak_ordering
[2] http://en.wikipedia.org/wiki/Strict_weak_ordering#Properties

>                                                                    I have no 
> idea where you are adding "or both", but if it is to the end of the 
> sentence, it's unnecessary as the truth table for "or" includes True or True 
> = True. "or" is not "xor"! (I realize that when writing English, there is an 
> ambiguity - "or" sometimes is taken to mean "xor". That might explain why 
> wikipedia would say that. But this is an Ada text, and "or" is well-defined 
> here - and it's not "xor"!!)

Oh? so what about (3), "the desired average or worst case".

> As to why you're baffled, I can't say; this is pretty straightforward 
> algebra. What else could this say? (Without the "strict weak ordering" 
> requirement, it's impossible to have a complete ordering and we cannot 
> expect implementations to do sensible things in that case.)

I completely understand that ">" must have certain properties. I can;t
grasp the formulation; maybe it's age.

Re: My Invention of "Bug Sort".

[Randy Brukardt]

"Niklas Holsti" <niklas.holsti@tidorum.invalid> wrote in message 
news:a53o7tF6gfU1@mid.individual.net...
> On 12-06-27 01:29 , Randy Brukardt wrote:
>> "Simon Wright"<simon@pushface.org>  wrote in message
>> news:m2sjdnyrlh.fsf@pushface.org...
>> ...
>>> I notice http://www.ada-auth.org/standards/12rm/html/RM-A-18.html#p5 -
>>> the last part of this is very terse. Wikipedia suggests that "(or both)"
>>> should be added.  But I'm still baffled; and this paragraph appears to 
>>> be
>>> for users, not implementers!
>>
>> This is the definition of "strict weak ordering", it is described as
>> precisely as possible. There's nothing really here for users;
>
> A user (programmer) using Ada.Containers and providing an actual Boolean 
> function for "<" must make sure that this actual function obeys this rule; 
> otherwise the container may not work as intended (as Randy said). So *in 
> principle* users need to understand this.
>
> The first three rules (with names, even more terse) are simple to 
> understand, because they are familiar properties from the usual complete 
> ordering of numbers and strings:
>
> - irreflexive: x < x must be False for all values x.
> - asymmetric: if x < y is True, then y < x must be False.
> - transitive: if x < y is True, and y < z is True, then x < z must be True 
> also.
>
> It is the fourth rule that is tricky, because it is important only when 
> there are incomparable (but different) values x and y for which neither x 
> < y nor y < x is True. If we use the symbol x # y for this 
> "incomparability" relation between x and y, the fourth rule can be stated 
> as: the relation # is an equivalence relation (a reflexive and transitive 
> relation).
>
> The reflexivity of # follows directly from the irreflexivity assumed for 
> "<"; the transitivity follows from the fourth rule for "<".
>
> For me, the rule "incomparability is an equivalence" is more intuitively 
> understandable than the formulation in the RM. The RM rule is easier to 
> state directly, however. That incomparability is an equivalence relation 
> comes out in the name of the function 
> Ada.Containers.Ordered_Maps.Equivalent_Keys.
>
> In practice, the fourth rule comes into play when the programmer-supplied 
> actual "<" function depends on only a part of the compared values, for 
> example, on only one "key" component of a record type. If two record 
> values x and y have the same key, x.key = y.key, then neither is "<" than 
> the other, but they can still be different if they have different values 
> in their other components.
>
> *In practice* I expect most programmer-supplied "<" functions will compare 
> one or a few "key" components of the operands. As long as each invocation 
> of "<" compares the same components of the operands, in the same way, 
> giving a complete ordering of these component values, the fourth rule 
> holds and the container should work. So perhaps most users can get away 
> with ignoring this rule.

Thanks for the detailed and complete explanation given above. For the rest 
of you, Niklas was the person who reported that the rule given in the Ada 
2005 RM was insufficient. Thus we had to add the "strict weak ordering" rule 
(and definition) given in the Ada 2012 RM. It shouldn't be surprising that 
he understands it better than I do. ;-)

                           Randy. 

Re: My Invention of "Bug Sort".

[Randy Brukardt]

"Simon Wright" <simon@pushface.org> wrote in message 
news:m21ukzywy4.fsf@pushface.org...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
...
>> This is the definition of "strict weak ordering", it is described as
>> precisely as possible. There's nothing really here for users; I don't 
>> think
>> its possible to define this informally and have it make any sense.
>
> As Niklas has noted, the implementer doesn't provide the ordering
> function and can't control it. The only people who need to decide
> whether the ordering function is OK are the developers (which is the
> group I meant by "users"; the users of the compiler).
>
> It may be necessary to understand this definition if you are a compiler
> writer, but there are going to be a lot of developers who will have real
> trouble with it. Including me (I was a physicist, not a
> mathematician). I think the Standard would be better without the last
> sentence of (5); give us a reference if you like.

We only can refer to a very limited number of references in the Standard, 
and our reference of choice for mathematics terms didn't include this one. 
In addition, we found at least three different names for this concept, and 
some confusion as to exactly how it is defined, so we felt it was necessary 
to define it formally in the Standard. I'm pretty sure that this definition 
was copied verbatim from some reference.

The Standard has to walk a serious tightrope, of both being accessible to 
mere mortals, as well as being precise. It's not always possible to do both. 
(We've been leaning more toward precise in recent versions, especially 
because of the efforts of professional nit-pickers like Adam Beneschan.)

                                                  Randy.

Re: My Invention of "Bug Sort".

[Simon Wright]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> I'm pretty sure that this definition 
> was copied verbatim from some reference.

The (free-standing) last bullet of [1] (before the "Total preorders"
section) concurs, though I don't suppose that Wikipedia was the
reference in question!

Thanks for the discussion.

[1] http://en.wikipedia.org/wiki/Strict_weak_ordering#Properties