|
Demo or Die #02
31 июля 1999 |
|
Demo-Building - 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.
__________________________________________
Other articles:
Similar articles: