True or False ?

True or False ?

[Austin@hotmail.com]

I have invented some new data sort methods that are particularly suited to Ada and am preparing some script that I will later be posting to a maths group to which I belong.

I want to say that the traditional sort methods i.e. quick sort and tree sort etc. in my view are almost benign classroom models not used in the real world of computing and programming today and are too inefficient in the way they work i.e. the data must be collected as a string of unsorted data first of all and then goes through a repetitive reduction process of comparing values and swopping places until there is proper ascending order in the transposed string. The whole thing in my view is top heavy with too much “too-ing” and “fro-ing” and is just too inefficient all round. 

I am not a professional programmer and I am not even in the industry but I have a cracker of a sort program that I will be disseminating free to readers later although I will be keeping the copyright to guard against commercial marketing to myself for now. 

To be honest, I am not entirely sure of my ground regarding my statement that tree sort and quick sort not being used and would like to know from any of you readers who do know, what is being used today in the real world of programming.

I want to be sure that I don’t make any brash statements that are not entirely true to the maths group.

Do you know if these sort programs are used in real world programming today ?

- adacrypt

Re: True or False ?

[Ludovic Brenta]

Austin writes on comp.lang.ada:
> Do you know if these sort programs are used in real world programming
> today ?

In our two-million-line mission-critical software we use heap sort and
tree sort but not quick sort.

-- 
Ludovic Brenta.

Re: True or False ?

[adacrypt]

On Sunday, June 17, 2012 10:37:17 AM UTC+1, Ludovic Brenta wrote:
> Austin writes on comp.lang.ada:
> > Do you know if these sort programs are used in real world programming
> > today ?
> 
> In our two-million-line mission-critical software we use heap sort and
> tree sort but not quick sort.
> 
> -- 
> Ludovic Brenta.

Many thanks.

I have never heard of heap save - is this to be found in academic books?
I'm taking it then that there has not been any huge advance in sorting methods over the past twenty years.

Could I pick your brains a bit further.

My scheme is ideal for accessing vast programs of millions of lines of source code like you mentioned - I tag every variable as it is being keyed in at the outset (at creation time) and then disable it until it is needed (I comment it out ) and if I do need it I simply uncomment it for sorting by a specially developed sorting method.  The tags can be stored up front or even stored in a file in memory for systematic calling by the main program

Perhaps you would have a look at this new method later when I go public.

Question - would it call it a big asset to improve on sorting methods? - given that there is so much computer power available to day - poor or even bad methods are getting by without notice?

Many thanks for your help again.

Regards - Austin.

Re: True or False ?

[Nasser M. Abbasi]

On 6/17/2012 5:35 AM, adacrypt wrote:
> On Sunday, June 17, 2012 10:37:17 AM UTC+1, Ludovic Brenta wrote:
>> Austin writes on comp.lang.ada:
>>> Do you know if these sort programs are used in real world programming
>>> today ?
>>
>> In our two-million-line mission-critical software we use heap sort and
>> tree sort but not quick sort.
>>
>> --
>> Ludovic Brenta.
>
> Many thanks.
>
> I have never heard of heap save - is this to be found in academic books?

I never heard of 'heap save' either. But Ludovic wrote above 'heap sort'
not 'heap save' , at least this is how it shows up on my news reader
(I do not use google groups). If you see it as heap save, then
this might be a googles groups bug again.

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

--Nasser

Re: True or False ?

[adacrypt]

On Sunday, June 17, 2012 12:37:23 PM UTC+1, Nasser M. Abbasi wrote:
> On 6/17/2012 5:35 AM, adacrypt wrote:
> > On Sunday, June 17, 2012 10:37:17 AM UTC+1, Ludovic Brenta wrote:
> >> Austin writes on comp.lang.ada:
> >>> Do you know if these sort programs are used in real world programming
> >>> today ?
> >>
> >> In our two-million-line mission-critical software we use heap sort and
> >> tree sort but not quick sort.
> >>
> >> --
> >> Ludovic Brenta.
> >
> > Many thanks.
> >
> > I have never heard of heap save - is this to be found in academic books?
> 
> I never heard of 'heap save' either. But Ludovic wrote above 'heap sort'
> not 'heap save' , at least this is how it shows up on my news reader
> (I do not use google groups). If you see it as heap save, then
> this might be a googles groups bug again.
> 
> http://en.wikipedia.org/wiki/Heapsort
> 
> --Nasser

I beg your pardon - this is a typo on my part - I should hve written heap sort  - sorry -adacrypt

Re: True or False ?

[Martin Trenkmann]

On 06/17/2012 12:35 PM, adacrypt wrote:
> On Sunday, June 17, 2012 10:37:17 AM UTC+1, Ludovic Brenta wrote:
>> Austin writes on comp.lang.ada:
>>> Do you know if these sort programs are used in real world programming
>>> today ?
>>
>> In our two-million-line mission-critical software we use heap sort and
>> tree sort but not quick sort.
>>
>> --
>> Ludovic Brenta.
>
> Many thanks.
>
> I have never heard of heap save - is this to be found in academic books?
> I'm taking it then that there has not been any huge advance in sorting methods over the past twenty years.
>
> Could I pick your brains a bit further.
>
> My scheme is ideal for accessing vast programs of millions of lines of source code like you mentioned - I tag every variable as it is being keyed in at the outset (at creation time) and then disable it until it is needed (I comment it out ) and if I do need it I simply uncomment it for sorting by a specially developed sorting method.  The tags can be stored up front or even stored in a file in memory for systematic calling by the main program
>
> Perhaps you would have a look at this new method later when I go public.
>
> Question - would it call it a big asset to improve on sorting methods? - given that there is so much computer power available to day - poor or even bad methods are getting by without notice?
>
> Many thanks for your help again.
>
> Regards - Austin.
>

Have you done an extensive research of sorting algorithms [1] before 
inventing your scheme or any comparison regarding best/avg/worst case 
runtime complexity?

I think there is still much research in this area going on and depending 
on the real use case many hybrid algorithms exist. For example the C++ 
std::sort from GCC uses intosort [2] which is a hybrid of quicksort and 
heapsort. Python and Java 7, as far as I know, use timsort [3], a hybrid 
of merge sort and insertion sort.

So I would be careful stating that "classroom" algorithms are not used 
in industry.

Anyway, the description of your scheme is not clear to me, but it 
reminds me a bit of counting sort [4], just to be sure not to reinvent 
the wheel.

Regards -- Martin Trenkmann

[1] http://en.wikipedia.org/wiki/Sorting_algorithm
[2] http://en.wikipedia.org/wiki/Introsort
[3] http://en.wikipedia.org/wiki/Timsort
[4] http://en.wikipedia.org/wiki/Counting_sort

Re: True or False ?

[Austin Obyrne]

On Sunday, June 17, 2012 3:14:48 PM UTC+1, Martin Trenkmann wrote:
> On 06/17/2012 12:35 PM, adacrypt wrote:
> > On Sunday, June 17, 2012 10:37:17 AM UTC+1, Ludovic Brenta wrote:
> >> Austin writes on comp.lang.ada:
> >>> Do you know if these sort programs are used in real world programming
> >>> today ?
> >>
> >> In our two-million-line mission-critical software we use heap sort and
> >> tree sort but not quick sort.
> >>
> >> --
> >> Ludovic Brenta.
> >
> > Many thanks.
> >
> > I have never heard of heap save - is this to be found in academic books?
> > I'm taking it then that there has not been any huge advance in sorting methods over the past twenty years.
> >
> > Could I pick your brains a bit further.
> >
> > My scheme is ideal for accessing vast programs of millions of lines of source code like you mentioned - I tag every variable as it is being keyed in at the outset (at creation time) and then disable it until it is needed (I comment it out ) and if I do need it I simply uncomment it for sorting by a specially developed sorting method.  The tags can be stored up front or even stored in a file in memory for systematic calling by the main program
> >
> > Perhaps you would have a look at this new method later when I go public.
> >
> > Question - would it call it a big asset to improve on sorting methods? - given that there is so much computer power available to day - poor or even bad methods are getting by without notice?
> >
> > Many thanks for your help again.
> >
> > Regards - Austin.
> >
> 
> Have you done an extensive research of sorting algorithms [1] before 
> inventing your scheme or any comparison regarding best/avg/worst case 
> runtime complexity?
> 
> I think there is still much research in this area going on and depending 
> on the real use case many hybrid algorithms exist. For example the C++ 
> std::sort from GCC uses intosort [2] which is a hybrid of quicksort and 
> heapsort. Python and Java 7, as far as I know, use timsort [3], a hybrid 
> of merge sort and insertion sort.
> 
> So I would be careful stating that "classroom" algorithms are not used 
> in industry.
> 
> Anyway, the description of your scheme is not clear to me, but it 
> reminds me a bit of counting sort [4], just to be sure not to reinvent 
> the wheel.
> 
> Regards -- Martin Trenkmann
> 
> [1] http://en.wikipedia.org/wiki/Sorting_algorithm
> [2] http://en.wikipedia.org/wiki/Introsort
> [3] http://en.wikipedia.org/wiki/Timsort
> [4] http://en.wikipedia.org/wiki/Counting_sort

No, I have not done any research on current sort algorithms.

The replies from you and the other readers have brought me up to date however.
I can see now that there is still some research going on and that is what I really wanted to know - it is not a closed book by any means.

My scheme will make all of these other sort programs redundant possibly but I am not clear why in my own mind - is speed still the essence in sort programs?  I think you will like the connection with Ada when it comes.

I will of course watch out now for making staements about academia.

Could I ask you to watch this space so to speak when I go public with my scheme - there is alot of Ada in it and it may even become a bench mark for comparisons with the existing sort algorithms.

Many thanks for your advice - Austin 

Re: True or False ?

[Shark8]

> No, I have not done any research on current sort algorithms.

It's actually kinda interesting; though it can quickly become rather technical.
 
> The replies from you and the other readers have brought me up to date however.
> I can see now that there is still some research going on and that is what I really wanted to know - it is not a closed book by any means.

It may actually have been on the verge of being "closed-book" for the most part, except that the move toward more parallel (esp multicore) systems means that a lot of them will have to be revisited if only to ensure that they both "play well" and 'are efficient' in parallel.

Indeed, this paper ( http://www.irma-international.org/viewtitle/66353/ ) shows that Shellsort is about twice as fast as Quicksort on parallel (CDUA in this case) systems. This is interesting because the Shellsort has traditionally always been been in the class of "better worst-case, better best-case, worse avg-case" when compared to Quicksort. So the move to parallel systems in non-trivial and has profound impact on what's "best".

> My scheme will make all of these other sort programs redundant possibly but I am not clear why in my own mind - is speed still the essence in sort programs?  I think you will like the connection with Ada when it comes.

That would be nifty.

> I will of course watch out now for making staements about academia.
> 
> Could I ask you to watch this space so to speak when I go public with my scheme - there is alot of Ada in it and it may even become a bench mark for comparisons with the existing sort algorithms.

Well, as an Ada fan/advocate I'd sat that'd be awesome.