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: 103376,9c33a91b2e4acc09
X-Google-Attributes: gid103376,public
From: mfb@mbunix.mitre.org (Michael F Brenner)
Subject: Re: Putting in alphebetical order
Date: 1997/04/25
Message-ID: <5jqd8n$m8f@top.mitre.org>#1/1
X-Deja-AN: 237284650
References: <01bc5176$95982c20$23bad084@SbastienGemme.uqam.ca>
Organization: The MITRE Corporation, Bedford Mass.
Newsgroups: comp.lang.ada
Summary: Enhance the following loop
Date: 1997-04-25T00:00:00+00:00
List-Id: <comp.lang.ada>


In order to put things in alphabetical order, you need to have a practical
knowledge of arrays, orderings, swapping, and elementary algorithms.
To get the knowledge on arrays and the "<" operator, read any introduction
to computer science, and reference the Ada Language Reference Manual.

Swapping things is a non-intuitive idiom developed to satisfy the need of
the priesthood of programming to indulge in a ceremoney called the 
bottleneck. The trick to implement this idiom is to recognize that
temporary storage is needed. Because temporary storage is not available
in ROM, embedded systems normally do NOT sort arrays, but rather implement
a separate array of tags, called an index, which points to the array of 
data in sorted order, while the array itself stays in the order it was
created (or generated or acquired). 

Finally, you need a sort algorithm to decide in which order to implement
the "<" and the swap methods. Such an algorithm will be an enhancement of
the following little loop:

     loop
         find two elements which are out of order
         swap them
     end loop

You will need to establish your precondition, postcondition, invariant
condition, and you will need to add a loop termination condition to this
loop because, for air conditioning purposes, your computer center 
may lock you in to the computer room until your loop terminates. Therefore,
you will have to add the appropriate EXIT statement or in other ways
properly exit the loop (such as addition a WHILE clause or a RAISE statement,
if you prefer those over the EXIT statement).

Many adventures in computer science are included in the phrase
<an enhancement of the following little loop>.

A complete theory of sorting arrays, if you wish to go beyond what is
in your introductory textbook, appears in Knuth, the Art of Computer
Programming, Volume 3, Sorting and Searching, published by Addison-Wesley.

Good luck