From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.0 required=5.0 tests=BAYES_00,FORGED_HOTMAIL_RCVD2,
	FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: 103376,8cb466bc329b6af9
X-Google-NewGroupId: yes
X-Google-Attributes: gida07f3367d7,domainid0,public,usenet
X-Google-Language: ENGLISH,CP1252
Received: by 10.68.227.67 with SMTP id ry3mr6723527pbc.8.1341411343011;
        Wed, 04 Jul 2012 07:15:43 -0700 (PDT)
Path: 
 l9ni10838pbj.0!nntp.google.com!news1.google.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
From: Austin Obyrne <austin.obyrne@hotmail.com>
Newsgroups: comp.lang.ada
Subject: 
 =?windows-1252?Q?Re=3A_More_on_the_=93Parallel_Sort=94_Data_Sorting_Pro?=
	=?windows-1252?Q?gram=2E?=
Date: Wed, 4 Jul 2012 07:15:42 -0700 (PDT)
Organization: http://groups.google.com
Message-ID: <0d853e86-5fb1-4e24-8e79-ff43399305cb@googlegroups.com>
References: <0117b182-7d8f-40ab-8729-6eb258ba5616@googlegroups.com>
NNTP-Posting-Host: 86.128.16.224
Mime-Version: 1.0
X-Trace: posting.google.com 1341411342 2311 127.0.0.1 (4 Jul 2012 14:15:42
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Wed, 4 Jul 2012 14:15:42 +0000 (UTC)
In-Reply-To: <0117b182-7d8f-40ab-8729-6eb258ba5616@googlegroups.com>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com;
 posting-host=86.128.16.224;
 posting-account=pmkN8QoAAAAtIhXRUfydb0SCISnwaeyg
User-Agent: G2/1.0
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
Date: 2012-07-04T07:15:42-07:00
List-Id: <comp.lang.ada>

On Tuesday, July 3, 2012 12:22:43 PM UTC+1, Austin Obyrne wrote:
> I am promoting this as a re-invention of =93Counting Sort=94 having being=
 acquainted of the latter=92s existence by readers, something I was truly u=
naware of but would like to point out that =93Counting =93 or =93Count sort=
=94 was invented in 1954.
>=20
> I quote from Wikipedia,
>=20
> =93Although radix sorting itself dates back far longer, counting sort, an=
d its application to radix sorting, were both invented by Harold H. Seward =
in 1954.=94  - Unquote      =20
>=20
>=20
> Given the state of progress in computer development at that time this inv=
ention must surely have been more of a longhand algorithm than a computer d=
riven program concept.
>=20
> I am not an an ego-trip here but I think it=92s fair to say that my imple=
mentation of =93Parallel Sort=94 as a data sorting program written in Ada i=
s a quite different invention.
>=20
> Given that the algorithm is unique and cannot possibly be presented in so=
me identical but different form (similar to the distinctiveness of the fact=
oring algorithm which is also a benchmark in computing)) I am claiming that=
 this is a bench mark for future in data sorting techniques that might even=
 be used as a yardstick in comparing computer and language combinations.
>=20
> I know that personally, I have supreme confidence that this is true of Ad=
a.
>=20
> In the course of updating my background knowledge, I made a few =91almost=
=92 right but not totally right statements that I would like to amend here =
just in case.
>=20
> In the general macro study of complexity theory the highest order of a fu=
nction is taken as the Big O rating and the minor terms including constants=
 are ignored.
>=20
> This is not true in data sorting theory =96 the constants cannot be ignor=
ed.
>=20
> Example.
>=20
> I have said,
>=20
> 1) In the expression (n Lg n) for the =91worst case=92 scenario datum in =
comparison type sort methods, any base will be acceptable and,=20
>=20
> 2) Log(a) n =3D Log (b) n /Log(b) (a) =96 the constant Log(b)(a) can be i=
gnored.
>=20
> These are both wrong statements in data sort theory, only (n Ln n) is cor=
rect and if it is changed to a different base (pointless really) then the c=
onstant must be included.
>=20
> Example:
>=20
> Comparing my =93Parallel Sort=94 data sort program that has linear comple=
xity growth with =91n=92 increasing, to a comparison-based sort program as =
a ratio of these two would be,=20
>=20
> n; (n ln n)=20
> or,
> 1; (Ln n)
>=20
> It would be totally worng if I was to instead say,
>=20
> 1; Log(b)(n)
>=20
> Clearly, changing the base of the logarithm without including the constan=
t of change would be wrong.
>=20
> Suppose I substituted,
> (Ln(n)) =3D (Log (b)(n) / log (b)(e)=20
>=20
> as shown it  would give a totally wrong comparison ratio not to include t=
he constant (Log(b)(e))
>=20
> I contend also that this is the first implementation in any computer lang=
uage of any version of =93Counting Sort) ever.
>=20
> I am mooting my invention of =93Parallel Sort=94 as a benchmark for futur=
e i.e. =93Parallel Sort=94 in Ada is both a first in data sorting and a fir=
st in any computer language.=20
>=20
> I have written a few specimen comparison programs in Ada just for the hel=
l of it and there is such a great amount of user assistance by way of condi=
tional statements required in the source code that there is no case whateve=
r that can be argued for retaining these in the future - they are just tota=
lly redundant.
>=20
> It is time to move forward in another area of computational mathematics i=
n my view away from comparison sorting methods =96 they are no longer requi=
red.
>=20
> Austin O=92Byrne,

Example.=20

I have said,=20

1) In the expression (n Lg n) for the =91worst case=92 scenario datum in co=
mparison type sort methods, any base will be acceptable and,=20

2) Log(a) n =3D Log (b) n /Log(b) (a) =96 the constant Log(b)(a) can be ign=
ored.=20

These are both wrong statements in data sort theory, only (n Ln n) is corre=
ct and if it is changed to a different base (pointless really) then the con=
stant must be included.=20

Example:=20

Comparing my =93Parallel Sort=94 data sort program that has linear complexi=
ty growth with =91n=92 increasing, to a comparison-based sort program as a =
ratio of these two would be,=20

n; (n ln n)=20
or,=20
1; (Ln n)=20

It would be totally worng if I was to instead say,=20

1; Log(b)(n)=20

Clearly, changing the base of the logarithm without including the constant =
of change would be wrong.=20

Suppose I substituted,=20
(Ln(n)) =3D (Log (b)(n) / log (b)(e)=20

as shown it  would give a totally wrong comparison ratio not to include the=
 constant (Log(b)(e))=20

Correction.

Humblest apologies.

<Example.=20

<I have said,=20

<1) In the expression (n Lg n) for the =91worst case=92 scenario datum in c=
omparison type sort methods, any base will be acceptable and,=20

<2) Log(a) n =3D Log (b) n /Log(b) (a) =96 the constant Log(b)(a) can be ig=
nored.=20

<These are both wrong statements in data sort theory, only (n Ln n) is corr=
ect <and if it is changed to a different base (pointless really) then the c=
onstant <must be included.=20

<Example:=20

<Comparing my =93Parallel Sort=94 data sort program that has linear complex=
ity <growth with =91n=92 increasing, to a comparison-based sort program as =
a ratio of <these two would be,=20

<n; (n ln n)=20
or,=20
<1; (Ln n)=20

<It would be totally worng if I was to instead say,=20

<1; Log(b)(n)=20

<Clearly, changing the base of the logarithm without including the constant=
 of <change would be wrong.=20

<Suppose I substituted,=20
<(Ln(n)) =3D (Log (b)(n) / log (b)(e)=20

<as shown it  would give a totally wrong comparison ratio not to include th=
e <constant (Log(b)(e))=20

*This is hogwash.

I have just realised that Lg in (n lg n ) is always the binary logarithm lo=
g base 2 and there is no question of changing it.

so the ratio of "Parallel Sort" to "Comparison Sort" in terms of complexity=
 growth is ,

1; (lg n) where lg is log(base2)and 'n' is the number of items being sorted=
.

Sorry about that.

Austin O'Byrne