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=3.8 required=5.0 tests=BAYES_00,INVALID_MSGID,
	RATWARE_MS_HASH,RATWARE_OUTLOOK_NONAME autolearn=no autolearn_force=no
	version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
From: "Maurice M. Carey IV" <mmc@primenet.com>
Subject: Re: What's the best language to start with? [was: Re: Should I learn
 C or Pascal?]
Date: 1996/09/01
Message-ID: <01bb9868$85b9fd00$3d2e44c6@primenet.primenet.com>#1/1
X-Deja-AN: 177890808
references: <31FBC584.4188@ivic.qc.ca>
 <01bb83f5$923391e0$87ee6fce@timpent.airshields.com>
 <4uah1k$b2o@solutions.solon.com>
 <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com>
 <4udb2o$7io@solutions.solon.com>
 <01bb8569$9910dca0$87ee6fce@timpent.airshields.com>
 <4urqam$r9u@goanna.cs.rmit.edu.au>
 <01bb8b84$200baa80$87ee6fce@timpent.airshields.com>
 <4vbbf6$g0a@goanna.cs.rmit.edu.au> <01bb8f18$713e0e60$32ee6fce@timhome2>
 <4vgs4j$evl@news.accessone.com>
 <01bb903b$be2fe260$87ee6fce@timpent.airshields.com>
 <5085ou$ra7@kanga.accessone.com>
content-type: text/plain; charset=ISO-8859-1
organization: Primenet Services for the Internet
mime-version: 1.0
x-posted-by: @198.68.46.61 (mmc)
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-09-01T00:00:00+00:00
List-Id: <comp.lang.ada>


So.

Bengt Richter <bokr@accessone.com> wrote in article
<5085ou$ra7@kanga.accessone.com>...
> "Tim Behrendsen" <tim@airshields.com> wrote:
> 
> >Bengt Richter <bokr@accessone.com> wrote in article
> ><4vgs4j$evl@news.accessone.com>...
> >> "Tim Behrendsen" <tim@airshields.com> wrote:
> >> [...]
> >> >Wait, hold the phone!  "Sorts the data without moving it"?  What,
> >> >is APL's sorting algorithm O(1)?  Yes, it may not actually get
> >> >sorted until it gets printed, but that's irrelevent to the fact
> >> >that it eventually gets sorted.
> >> 	Does that mean that your concept of the essential aspect of
> >> sorting is putting the data into sort order, rather than establishing
> >> the order itself? The respective timings say otherwise to me ;-)
> 
> >I'm not sure what you're trying to say, but if I have a data set,
> >and I set a bit that says "this data set has the property of
> >being ordered", then technically I have an ordered data set in
> >O(1) time.  Now, if I do an add reduction (terminology?), the
> >sorting doesn't actually have to be done, and I've saved some
> >CPU cycles.
> 
> >But all that's not the point.  If my point is to take a vector as
> >input, order it, and then display it on the screen, the vector
> >will be sorted.  And sorting something requires moving it into
> >a sorted order.
> 
> If you have (please overlook syntax bloopers)
>   struct tBigComplexThing {
>     ... blah, blah
>   } aBigArrayOfThem[kBig];
> you could sort them by moving the data around, and then print it
> by a loop such as for(i=0;i<kBig;i++)
>    printf("theformat",aBigArrayOfThem[i].anItem, etc..);
> You could also sort by using an array
>   int aiPermute[kbig];
> initialized by 
>   for(i=0;i<kBig;i++) aiPermute[i]=i;
> and then use a quicksort or whatever so that the
> integer elements of aiPermute[] get moved around instead
> of the tBigComplexThing elements of aBigArrayOfThem[].
> The comparison function just has to take two indices into
> aiPermute[], e.g., j and k, and compare
>   aBigArrayOfThem[aiPermute[j]].someField
> and
>   aBigArrayOfThem[aiPermute[k]].someField
> and operate on aiPermute[] as if it had compared
>   aiPermute[j] with aiPermute[k].
> I take it something like this is involved in the APL
> use of a "permutation vector" cited in a previous post.
> 
> Anyway, now you can do your print by the loop
>   for(i=0;i<kBig;i++)
>     printf("theformat",aBigArrayOfThem[aiPermute[i]].anItem, etc..);
> and expensive movements of the original data don't have to be part
> of the sorting process, even though you could say that the data
> eventually gets "moved into sorted order" into the output stream.
> But the latter happens in linear time, and is not relevant to the
> sorting algorithm executed beforehand.
> 	To summarize what I was getting at, I think
> "sorting data without moving it" is a fair description of sorting
> data by reordering references to it, since the sorting does not
> involve moving the data. I don't think subsequent extraction of
> the data itself into an ordered stream can be called sorting.
> 
> Regards,
> Bengt Richter
> 
> 
>