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.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	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: bokr@accessone.com (Bengt Richter)
Subject: Re: What's the best language to start with? [was: Re: Should I learn
 C or Pascal?]
Date: 1996/08/31
Message-ID: <5085ou$ra7@kanga.accessone.com>#1/1
X-Deja-AN: 177549278
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>
organization: -
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-31T00:00:00+00:00
List-Id: <comp.lang.ada>


"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