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,50880f040eb869b4
X-Google-Attributes: gid103376,public
From: mfb@mbunix.mitre.org (Michael F Brenner)
Subject: Re: Anyone help develop an algorythm?
Date: 1997/04/25
Message-ID: <5jqds4$mfa@top.mitre.org>#1/1
X-Deja-AN: 237286968
References: <97042417025012@psavax.pwfl.com>
Organization: The MITRE Corporation, Bedford Mass.
Newsgroups: comp.lang.ada
Summary: Alternative to slow sort
Date: 1997-04-25T00:00:00+00:00
List-Id: <comp.lang.ada>


Slow sort is an interesting development, but might not satisfy the realtime
criterion for certain non-genetic embedded systems. Taking the basic loop

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

one could enhance it as follows 

     -- precondition: the unsorted array of integers has no repeats and
     --               is already read into the array object_list

     subtype sub_type is object_exact_integer_type range
        get_min (all_objects) .. get_max (all_objects);

     type ar_ray is array (object_exact_integer_type range <>);
     subtype condensed_essence_of_objects is ar_ray range sub_type;

     for i in indexes loop
       ar_ray (object_list (i)) := True;
     end loop;

     for i in sub_type loop
       j := get_next_non_zero_index;
       text_io.put_line (my_image (j));
     end loop;

     -- This sort takes time linear in the number of elements of your
     -- array on any machine in which inputting, outputting, searching
     -- for the next non-zero index, imaging, indexing arrays, and
     -- reading and writing bits in bit arrays can be done in constant
     -- time; the main exception to this will be searching for the next
     -- non-zero index. The BESM-6 computer produced by Russia has a
     -- hardware op-code to do this, however, it is only useful for
     -- sorting arrays whose object values range from 0..7 with no repeats.