Demo-Building - some of sorting method.

<b>Demo-Building</b> - some of
sorting method.

__________________________________________


    Hello. Once WOLF promised in the first
DEMO OR DIE room to tell about some
sorting method. But by coincidence
different circumstances the task entrusted
to me, Kenotron'a.


    By sorting an array of numbers to understand
organize them in ascending order. This
the problem is classical in
programming, and there are several methods
its solution. We make a little review of these.


    1. Sorting an array by

                 'Bubble'

Method is as follows:


    - Produce a consistent view of the array and compare 
adjacent pairs numbers, arranging them in ascending order


    - As a result of such a view on
last place will be the largest
number (surfaced 'bubble');

    - Repeat this procedure until
while during the show will not be
produced by a single permutation.


    It looks like this:

;--------------------------------------;
; Sort routine;
; One-dimensional array of numbers;
; By the 'bubble';
;--------------------------------------;
;>: HL = [array address];
; B = [array length];
;--------------------------------------;


        LD HL, DATA

        LD B, 10


        DEC B
SORT1 PUSH BC, HL


        LD D, 1; count permutations

SORT2 LD A, (HL); compare

        INC HL; neighboring

        CP (HL); number

        JR C, SORT3

        JR Z, SORT3


        LD C, (HL); here it where,

        LD (HL), A; swam bubble

        DEC HL

        LD (HL), C

        INC HL


        INC D; fix

                    ; Permutation
SORT3 DJNZ SORT2


        POP HL, BC


        DEC D; a permutation?

        JR NZ, SORT1

        RET

DATA DB 1,9,2,8,3,7,4,6,5,5


Note: here and below are
source code written in assembly language
STORM by X-Trade (rulez!).


    An example of a worker, but is subject to global
optimization.

    I do not know what to say about the benefits of
this method, but the lack of -
rather inhibitory (maybe even most)


    2. Sorting an array by

       permutation (a simple choice)

Here's the gist:


    - The first array element (X1) is compared with all other;

    - If at any point of comparison
find that X1> Xi, then they change
places;

    - As a result of on-site X1 will be
be the smallest element;

    - Now compared to X2, followed by items on the same 
conditions; 

    - After this view in place X2
will be greater than X1, but less
all remaining;

    - Then carried out a similar comparison for all other 
elements until then, until the last two will be compared;


    - We end up with the increasing
sequence of numbers.


    This can be illustrated as follows:

;--------------------------------------;
; Sort routine;
; One-dimensional array of numbers;
; By rearrange;
;--------------------------------------;
;>: HL = [array address];
; B = [array length];
;--------------------------------------;


        LD HL, DATA

        LD B, 10

SORT1 PUSH BC, HL


        LD A, (HL); have an element of

        DEC B

        JR Z, SORT4; end of the array?

SORT2 INC HL

        CP (HL); compare

        JR C, SORT3

        JR Z, SORT3


        LD C, (HL); swap

        LD (HL), A

        LD A, C

SORT3 DJNZ SORT2


        POP HL, BC


        LD (HL), A; the smallest:)

        INC HL

        DJNZ SORT1

        RET

SORT4 POP BC, HL

        RET

DATA DB 1,9,2,8,3,7,4,6,5,5


    Compared to the previous, this method
works a little (much) faster.


    3. Sorting an array by

             John von Neumann


    Suppose we need to sort
A long sequence of numbers N, such as
A (N):


    1) Set a certain amount equal to the K
unity, ie K = 1;

    2) Divide the sequence of numbers
for subsequences of length K;

    3) Merge standing next to a subsequence in one;

    4) Do K = K * 2;

    5) If K <N, then go to step 2.

In more detail:

    What does it mean: Splits sequence? Means to create, for 
example, two Index: i and j (j = i + K), indicating

beginning of sequences.

    And the United States - sort two
subsequence of another, ie:
A (i) compared with A (j) and, if necessary,
reversed, then A (i +1) with A (j +1) and
etc., to give an ordered sequence. The next time you pass a 
subsequence will be twice as long. 


    I do not know what to say about the implementation
this method on the Spectrum. Make sure
You can, but how it will work!
Operate with no pointers, addresses,
each time counting them. Well, in general,
if you long to suffer - something
get:)


    4. Bitwise sorting array

                  (BITSORT)


    Very fast method (say
faster than QUICKSORT), is now in
what:

    - Create two so-called
STACK: The first is called '0 'and the second - '1';

    - Then takes the first number in the array
and analyze its bit zero: if it
is zero, then the number is entered onto the stack
'0 ', Otherwise the stack '1'. And so the same
for all numbers of the array;

    - Then the place of the original array
correspond with the numbers from the stack '0 'and
trace from the stack '1 '. Thus we
obtain a sequence of numbers
sorted by a zero bit;

    - Well, and on an array of similar
sorted by the first bat, etc. to
the latter. All sorting is finished.


    Everything seems easy, but in practice
sort bat is sometimes slow
(Especially if you sort of 16 or
32-bit numbers). Therefore, the analysis can be
performed immediately on two, three or more
bits (to reduce the number
passes), creating a
accordingly (4,8 ,...) of
stacks (which requires more memory).

    At the Spectrum, this method can be
apply in the case of analysis directly 8 bits
ie bytes. In connection with this bit
Sort 'degenerates' into a byte
(Bytesort), for which you already
256 (!) Stacks.


    And then there is the idea of making
sorting, the result of which
an array of numbers in packaged form,
ie:

    that if each of the 256 stacks
not record the numbers themselves, but their number
repetitions in an array, and 0 on the stack will be
mean that such numbers do not in
array! It looks like this:


    - First we need to reset all
256 stacks located at the address # xx00
(This of course will take time, but for this
cases do not mind);

    - Take the first number of the array, it
shows us the number of stack contents
which increases by 1;

    - Repeat the same for all
other numbers;

    - Resulting from the address # xx00 get sorted packed 
sequence. 


    I do not know, maybe you'll come up and how it
(Sequence) used in this
form, but with a strong desire, it can be
unzip to any location, which is also
takes a piece of time ;-(

    But there is still one limitation:
occurrence of any number should not be
255. Although this can be avoided
make the stack double-byte.

    As an example, proposed
program that implements the above-described
idea. Program is working, but is
optimization:)

;--------------------------------------;
; Sort routine;
; One-dimensional array of numbers;
; Method 'BYTESORT +';
;--------------------------------------;
;>: HL = [array address];
; BC = [array length];
,;
, <: # 8000 .. # 81FF: 256 stacks (packed);
; # C000 .. : Sorted array;
;--------------------------------------;


        LD HL, DATA

        LD BC, 10


        DI

        PUSH HL

        PUSH BC


        LD (NORMA +1), SP

        LD SP, # 8200; clean stacks

        LD HL, 0, a total of 512 bytes
.255 PUSH HL

        PUSH HL
NORMA LD SP, 0


        POP DE

        POP BC

        LD H, # 1980

SORT LD A, (DE); proper

        LD L, A; sorting

        INC (HL); packaging

        JR NZ, SORT1

        INC H; if the numbers> 255 -

        INC (HL); change the senior

        DEC H; bytes
SORT1 INC DE

        DEC BC

        LD A, B

        OR C

        JP NZ, SORT


        LD DE, # 8000; and this unboxing

        LD HL, DEP_3

        LD C, E

        EXX

        LD BC, # C000; here here

        LD DE, OPEN_CL-2

        EXX

DEP_2 INC D

        LD A, (DE); first look

        DEC D; byte

        OR A

        LD B, A

        LD A, E

        JP Z, BYTE_D
DEP_1 EXX

        CALL OPEN_CL

        DJNZ DEP_1

BYTE_D EX AF, AF

        LD A, (DE); and then - Junior

        INC E

        NEG; this is a test to 0:

        JR Z, DEP_3; whether there exists a number

        PUSH HL

        EXX

        LD H, 0, count

        LD L, A; jump

        ADD HL, HL; open loop

        ADD HL, DE

        EX AF, AF

        PUSH HL

        RET

DEP_3 DEC C

        JP NZ, DEP_2

        EI

        RET

OPEN_CL; is open
.255 LD (BC), A: INC BC; cycle decompression

        EXX

        RET

DATA DB 1,9,2,8,3,7,4,6,5,5


    The task was to sort
array of 60 numbers, and here are the results
Test:

    BYTESORT with unpacking performed best
results - slightly less than 1 / 2 Interrupt
(About 30000 cycles, frame!:) And on
sorting only 14 (!) percent
all the time, the rest is
unpacking. It is interesting to note that for
increasing the length of the array when sorting
increases proportionately, and the time
unpacking is growing more slowly!

    Permutation method has proved
a little worse - a little more than interrupt
(Thousands of commercials 85 cycles), and it's just something to
some 60 bytes!

    The method of bladder spent ... much as three (3)
Interrupt! No comments.


    I think the method of BIT / BYTE sort can
find application.


    There is a lot different
methods of sorting, viewing that
beyond the scope of this article
focused on the possibility SPECCY.


    When writing this text, partly
has benefited from
RU.ALGORITHMS. Thanks also Kopytin
Paul (DIZZY) for assistance.


    And once again: the main thing in our business -
Optimization! Here it themselves twist.
__________________________________________