|
Inferno #09
31 июля 2006 |
|
For Coderz - On the sort of array elements.
About sorting
Alone Coder
Let the elements of the array a numbered
0 to num-1, and we need to sort them by
ascending order (smallest first by
value, then more and more - and
so to the maximum).
0
That's a stupid sort, "each with each,
which for some reason sometimes awarded IU
hundred in the literature:
for (i = 0; i <num; i + +) {
for (j = 0; j <num; j + +) {
if (a [i]> a [j])
swap (a [i], a [j])
}
}
Here, n * n passes of the inner loop.
General enough, someone came into my head comparison
Niva each pair of elements twice.
It only goes to get results
i> j, while their older counterparts are useless
- They sort in the opposite direction. But the EU
Do we remove these passages-doubles, then
obtain acceleration only twice, and then
in any way. This is a dead end.
1
Change the algorithm so that it is exchanged
only the neighboring array elements. At the same time
accelerate it in the same 2-fold (to (n-1) *
* (N-1) / 2 passes), using the fact that the maximum
maximal element is at the end of the array
After the first iterate ("pops").
It turns out the so-called "bubble with
rtirovka "- bubble sort.
for (i = num; i> 0; i -) {
for (j = 0; j a [j +1])
swap (a [j], a [j +1])
}
}
Number of exchanges is the number of displacements
elements, divided by 2. The number of displacements
tions of numbers equal to the number of elements, the mind
sheath, the average number of displacements for
element.
The number of displacements of the element well: the number
of move left plus the number of displacements
right. (Da-da! element before finding
its place in the array can move as
drunken sailor! Example - Element 2 in the array
ve 4 2 1 3.)
Element [i] moves to the left so much
again, how many more of its elements were
left in the original array a [i]. In
average, it will be i / 2.
Element [i] moves to the right one hundred
lko of times smaller than its elements
was right in the original array a [i].
On average, it will be (num-i-1) / 2.
Total average number of movements of elements
that: (num-1) / 2. Hence, the average number of variables
displacements of the elements: n * (num-1) / 2. Hence
the average number of exchanges: n * (num-1) / 4, ie
approximately half the number of passes
the inner loop.
Here's how our algorithm performs a typical
processor (reg - it registers):
for (reg_i = num; reg_i> 0; reg_i -) {
for (reg_j = 0; reg_j <reg_i; reg_j + +) {
reg_aj = a [reg_j];
reg_aj1 = a [reg_j +1];
if (reg_aj> reg_aj1) {
reg_temp = a [reg_j];
a [reg_j] = a [reg_j +1];
a [reg_j +1] = reg_temp
}
}
}
On average, 2 + (4 / 2) = 4 array access
one step away! WE DO NOT NEED SO MUCH!
2
Remove 2 of 4 references to an array of internal
three exchanges.
for (reg_i = num; reg_i> 0; reg_i -) {
for (reg_j = 0; reg_j <reg_i; reg_j + +) {
reg_aj = a [reg_j];
reg_aj1 = a [reg_j +1];
if (reg_aj> reg_aj1) {
a [reg_j] = reg_aj1;
a [reg_j +1] = reg_aj
}
}
}
3
Remove one of the two memory accesses
outside the exchange.
for (reg_i = num; reg_i> 0; reg_i -) {
reg_aj = a [0];
for (reg_j1 = 1; reg_j1 <= reg_i; reg_j1 + +) {
reg_aj1 = a [reg_j1]; //!!!
if (reg_aj> reg_aj1) {
a [reg_j1] = reg_aj1;
a [reg_j1-1] = reg_aj;
};
else reg_aj = reg_aj1;
}
}
Now, at each step, we appeal to
array average of 2 times. Only.
Only? Think hard!
WHY NOT JUST 1! Why this mess
exchanges, if we just need to drag
maximum values in the array??
Enough to exchange a maximum value
of the last cell - and we will
the same!
4
Take away the exchange to apply to mass
Sivu only 1 time for each step. At the same time
decrement disappears. Obtain a sort
direct search.
for (reg_i = num; reg_i> 0; reg_i -) {
reg_j = 0; / / current max index
reg_aj = a [0]; / / current max number
for (reg_j1 = 1; reg_j1 <= reg_i; reg_j1 + +) {
reg_aj1 = a [reg_j1];
if (reg_aj> reg_aj1) {
reg_j = reg_j1; / / current max index
reg_aj = reg_aj1; / / current max number
};
};
a [reg_j] = a [reg_i];
a [reg_i] = reg_aj; / / current max number
}
Total we have received over the first
primary method of acceleration in the eight (8)
times the number of accesses to the array ((num-1) *
* (Num-1) / 2) and 2 (two) times the number of CPA
vneny (too (num-1) * (num-1) / 2).
True, we do not take into account that each element
nte array can be (and usually is) still
any of the information, except for values
(Value), by which we sort. Eg
measures to build the Huffman tree elements
Options should include the frequency (this will be
value) and - as a makeweight - code symbols
la. For the Z-sorting of polygons value - it
Z-coordinate, and the remaining coordinates - up
plumb. Wherever you have "moving"
or "exchange" element refers to variables
displaced all of the information contained in
elements. The above programs will be
only work if the comparison operation
compares the values of elements, and the operation
assignment copies the element entirely. But
then reg-variables will not compile
as registers, and as variables in memory -
it is slow!
5
Speed up:
for (reg_i = num; reg_i> 0; reg_i -) {
reg_j = 0; / / current max index
reg_aj = a [0]. value; / / current max number
for (reg_j1 = 1; reg_j1 <= reg_i; reg_j1 + +) {
reg_aj1 = a [reg_j1]. value;
if (reg_aj> reg_aj1) {
reg_j = reg_j1; / / current max index
reg_aj = reg_aj1; / / current max number
};
};
swap (a [reg_j], a [reg_i])
}
When implementing this algorithm on Assos
mblere, in the case of a common sort is maximal
FIR arrays, we can consider that at the moment
swap team we already have in the registers
value of the element a [reg_j].
6
If we are sure that num is sufficiently
face, we can use more sophisticated
algorithms.
For example, the algorithm heap sort (if
is not the best of the algorithms with internal
rtirovki, then, in any case, it is easier and
faster than the well-known quick sort) there is
two stages:
1) becomes an array in an almost complete bi
nary tree where each parent is not less
above the child. Requires up to (num / 2) * log2 (num / 2)
passes, each of which has a 2.5 CPA
vneny, 2, array access, 2 increment
the one and one multiplication by 2.
2) For j = num-1 to 1 repeat the following
operation: sharing the first element of the array
j-m (removed from the tree), then corrected
tion of the resulting tree. Each corrected
tion requires up to log2 ((j-1) / 2) passes
the same form as in the first stage.
Total needed somewhere to
num * (log2 (num) -1)
passages of this type.
Let num = 32. Then to heap sort triangle
buetsya to 256 calls of an array of up to 320
comparisons to the 256 + and increments to 128 mind
multiplication by 2. And for the old algorithm (see
paragraph 5) - 496 visits to the array, 496
comparisons and 496 + increments.
Here's an article about the heap sort of the journal
Pixelate # 5 (translating from English wills
but correcting and supplementing). Author - Robert J
Ohannessian.
Heap, used heap sort, - once
novidnost binary tree, which
left-complete (ie, to fill up on the left
right, and the transition to a new tier is not about
proceeds until it is filled with previous). Each
dy heap'a node must contain a value
(Value) not less than each of 2 of his
descendants (if any).
Example:
76
/
45 34
/ /
6 12 8
As we see here every parent does not change
nshe child. Also shows that the tree leftcomplete, because the
last stage filled varies from left to right, and all previous
floor completely zapolneny.Tak that we face a typical
LIMITED heap.
To generate this initial
heap, we have several times used
algorithm called 'reheapification'
(See below). We assume that our array has
transferred to the heap.
How to place a heap in memory, not ISPO
lzuya pointers and other dregs? And here's how.
Simply an array, tier over tier:
Array: 76 45 34 6 12 8
Position: 0 1 2 3 4 5
Note that when you add in
an array of new items we heap remains
left-complete - the last stage is filled with
left to right. Another note that
child nodes of node number i are
cells i * 2 +1 and i * 2 +2. However, the question arises
growing up: how can we ensure that the value
parents no less than his descendants?
Take the same example. Suppose that we
added 102 in the end heap'a, that is to
Finally the array:
76 45 34 6 12 8 102
which corresponds to the following tree:
76
/
45 34
/ /
6 12 8 102
This is not a heap. To make it heap'om,
try to exchange the 102 with its parent
(34). We obtain the following tree:
76
/
45 102
/ /
6 12 8 34
Is closer, but still no heap. Repeat
sured the same operation, and we get:
102
/
45 76
/ /
6 12 8 34
Now it's heap.
If you're wondering, the program realized
realizes the above-described, as follows:
/ * Adds a 'value' in a heap,
lying in the array 'array'. We must follow
to 'array' is not overflowed * /
void add_to_heap (int * array,
int * size,
int value) {
int i = * size;
/ * Writing value to the array, ie in
the first blank cell heap'a * /
array [* size] = value;
(* Size) + +;
/ * Until the mass heap, move the value
up * /
while (i> 0''array [(i-1) / 2] = len)
break;
else if ((right> = len)
| | (Array [left]> array [right]))
max = left;
else
max = right;
if (array [k]> array [max])
break;
SWAP (array [k], array [max]);
k = max;
}
/ * Sorts a list of ints using Heap Sort * /
void sort_ints (int * array, int length) {
int i, k;
/ * Build heap from an array * /
for (i = length / 2; i> = 0; i -)
SORT_DOWN (i, length);
for (i = length - 1; i> 0; i -) {
/ * Move to the root of the sorted part * /
SWAP (array [i], array [0]);
/ * Fix heap of unsorted parts * /
SORT_DOWN (0, i);
}
return;
}
In the book "Data Structures for the person
lnyh computers "(J. Lengsam, M. Ogenstayn, A. Te
nenbaum. - M.: Mir, 1989), this algorithm
called the "heapsort".
The authors offer a source in BASIC. About
pay attention to the differences from vysheprive
excited sishnogo sources:
1. The initial tree is not built from the bottom
upwards and downwards (using vysheizlo
adjoint algorithm add_to_heap, which Sievers anymore.) This
requires a double more passes, and although the shorter passages
(Their lengths increase with the filling
heap'a), on average, a loss.
2. In reheapification instead of the chain
swap'ov (4 array access at each
step) to use a chain of simple set group
ivan (2 treatment to the array on each
step), the parent pre-
memorized and put into an array in the latter
nyuyu turn. This is a good win.
3. There are a number of extra increments, which
rye can be optimized.
4. Lines 5210-5250 in fact repeat
lines 5290-5320, only with fewer
calculations - especially for the root.
5050 for k = 2 to n 'we have an array x (1 .. n)
5060 'insert x (k) into an existing
'Pyramid of size k-1
5070 i = k
5080 y = x (k)
5090 j = int (i / 2) 'j is the father of i
5100 if j <= 0 then goto 5160
5110 if y <= x (j) then goto 5160
5120 x (i) = x (j)
5130 i = j
5140 j = int (i / 2)
5150 goto 5100
5160 x (i) = y
5170 next k
5180 ', we remove x (1) and put it in
'Array in the position corresponding
'Its value, and then reconstructing
'Pyramid
5190 for k = n to 2 step -1
5200 y = x (k)
5210 x (k) = x (1)
5220 'reordering of the pyramid
'Of order k-1; moving y to the bottom
'Pyramid in place, appropriate
'Its value
5230 i = 1
5240 j = 2
5250 if (k-1> = 3) and (x (3)> x (2)) then j = 3
5260 'j is a great son i in
'Pyramid of size k-1
5270 if j> k-1 then goto 5340
5280 if x (j) <= y then goto 5340
5290 x (i) = x (j)
5300 i = j
5310 j = 2 * j
5320 if j +1 <= k-1
then if x (j +1)> x (j) then j = j +1
5330 goto 5260
5340 x (i) = y
5350 next k
The next time I might write about
merge sort, which, in my opinion I
Niya, most convenient for the sort of names
files.
Other articles:
Similar articles:
В этот день... 26 April