KrNews #16 29 июля 2003

Программирование

Coding - Algorithms and Data Structures.

________________________


                 Tsoding

               _________________________



    Just scared to call this zalipen
coding'om, well, just tsoding.


    I wanted to sink a little bit of ruleza
Wirth (Wirth rulez! Viner rulez!). AAAA,
Yes, and again did not have time. And it you want?
E-mail, if necessary. Generally he has a
entire book:

[A]. Wirth N. Algorithms and Data Structures: Trans. from 
English. 2 nd ed., Corr. - SPb.: Nevsky Dialect, 2001. -352c.: 
Ill. 


    RULEZ! from cover to cover! See -
seize without hesitation!


    Just do not hunt me rewrite
thence, so even on the AFM to shift:)


    In general, go to the application, where all
sources in XAS'e and txt with commentaries and an explanatory 
memorandum (under Speccy and dot matrix printer) kursovika in

sort by topic. Then just do not want
ACM convertible to 40 characters, eerie
thing happens.


    And to suggest that priming results
of this prog-comparison of the two sorting methods (by the way 
in the frame Any methods can test the software):




    4 Results of the study


    Items in the table oanachayut the following:
- Number of elements to sort (by

    2 bytes each);
- Method of filling sorted array,

   -Ordered (already sorted)

   The inverse (reverse ordered)

   -Random (for RND)

   + Random-ordered (in the ordered
    disordered array of random addresses

    entered a random number, their number
    honors dosed in the main menu

    as 1 / 2, 1 / 4 etc);
- The number of comparisons made;
- Number of movements (exchange);
- The time of sorting (in increments of 0.02 sec).



    4.1 Results Sort by direct selection (one of the 
'conventional' methods): 


Count method count count time
 e-s-west, I compared the first AC-th sec


    64 ordered. 2016 0.20 0

        back. 2016 1024 0.24

        case. 2016 186 0.20

        yn. + cl. 2016 162 0.22


   256 ordered. 32640 0 3.18

        back. 32640 16384 3.96

        case. 32640 1088 3.24

        yn. + cl. 32640 1027 3.22


  1,024 ordered. 523776 0 50.78

        back. 523776 262144 63.72

        case. 523776 5770 51.18

        yn. + cl. 523776 5166 50.76


  4,096 ordered. 8386560 0 715.70

        back. 8386560 4194304 896.20

        case. 8386560 27806 716.88

        yn. + cl. 8386560 26703 716.82



    4.2 Results of sorting on a tree:

Count method count count time
 e-s-west, I compared the first AC-th sec


    64 ordered. 593 457 0.12

        back. 525 383 0.10

        case. 578 425 0.10

        yn. + cl. 523 371 0.10


   256 ordered. 3452 2355 0.64

        back. 3106 2025 0.56

        case. 3281 2194 0.62

        yn. + cl. 3009 1978 0.54


  1,024 ordered. 18060 11503 3.24

        back. 16407 10077 2.88

        case. 17305 10858 3.8

        yn. + cl. 17225 10803 4.3


  4,096 ordered. 88835 54503 15.56

        back. 82304 48673 13.86

        case. 85671 51633 14.72

        yn. + cl. 85811 51777 14.82


ps / / Yes, I just fell out, when some
rotten sort of some 4096 elements (8K) worked 800 sec.! (I 
initially wanted to sort the whole page, ie, 16 KB - 8192 
elements), even had simulation done (see sortsy)


    But I fell even more, when sorting by a certain tree (I'm 
still in the principle of its long vezhal) worked 30 times 
faster! 



    3. Brief theoretical information

    3.1 Sorting


    3.1.1 In processing the data is important
know the information data field and placing them in the car. 
Distinguish between internal and external sorting: 

    - Internal sorting, sorting
in memory;

    - External sorting, sorting of
external memory.

    Sorting is the location of the data
in memory in a regular form of their keys.
Regularity is considered as an increase (decrease) key value 
from the beginning by the end of the array.


    If the sorted records occupy
large amount of memory, then move them
costly. To
reduce them, sorting is in
address table keys, make a permutation of pointers, ie, array 
itself is not moved. This method of sorting table addresses.


    When sorting may occur
the same keys. In this case, it is desirable to place after 
sorting Sorting the same keys in the same manner as the 
original file. This is a stable sort. 

    The effectiveness of sorting can be viewed from several 
criteria: 

    - The time spent on sorting;

    - Amount of RAM required for sorting;

    - The time spent by the programmer
to write programs.

    Select the first criterion, since
we consider only the sorting methods "in the same place," that 
is not reserving for the sorting process extra memory. 
Equivalent spent on sorting time can be considered number of 
comparisons in the performance of sorting, and number of 
movements, although this is a very rough estimate. Therefore, 
you should also make a direct measurement of time spent on 
sorting, in these particular circumstances. 

    Distinguish the following sorting methods:

    - Strict (direct) methods, which
is a simple sort of direct elections;

    - Improved methods, which include sorting through the tree.

    Rigorous methods of demonstrating a natural human behavior, 
they are most simple, but very slowly because

their efficiency decreases proportionally
square of the number of elements-f (n ^ 2). At the
While improved methods for this expression is close to f (n * 
log n), although they more complex and more difficult to 
understand and control.



    3.2 Sorting with direct selection


    3.2.1 This method is based on the following principles:

    - Select the element with the smallest
key.

    - He trades places with the first element A [1].

    - Then the process repeats with
the remaining n-1 elements, n-2 elements, etc. until then, 
until there is one very "big" item. 

    The algorithm is formulated as follows:


  FOR i: = 1 TO n-1 DO

      k: = index of min (a [i], ..., a [n]);

      swap a [i] <-> a [k];

    END;

;
; / / (C) Niklaus Wirth "Algorithms and
; / / Data structures "
; / / -> Source written on Modula-2.
/ /
; / / PROCEDURE StraightSelection;
; / / VAR i, j, k: index; x: item;
; / / BEGIN
; / / FOR i: = 1 TO n-1 DO
; / / K: = i; x: = a [i];
; / / FOR j: = i +1 TO n DO
; / / IF a [j] <x THEN
; / / K: = j; x: = a [k] END
; / / END;
; / / A [k]: = a [i]; a [i]: = x
; / / END
; / / END StraightSelection;
;


    The effectiveness of the algorithm. Number of comparisons 
of keys C, obviously, does not depend on initial order of keys. 
We can say that in this sense, the behavior of this method is 
less natural than the behavior direct connection. To C at any 
location of keys, we have: 


    C = n (n-1) / 2 (3.1)


    Order of the number of comparisons, thus, O (n ^ 2).

    Minimum number of permutations in the case initially 
ordered keys: 


    Mmin = 3 * (n-1) (3.2)


    And as if originally
keys arranged in reverse order:


    Mmax = (n ^ 2) / 4 + 3 * (n-1) (3.3)


    For randomly distributed keys
approximately [1]:


    Mavg = n * (ln (n) + g) (3.4)


    where g = 0.577216 ...- Euler's constant.


    In the worst case, sorting by direct
choice gives the order of n ^ 2, as for the number of
comparisons, and for the number of displacements.


    3.3 Sorting with tree


    3.3.1 Method of sorting through
Direct selection is based on repetitive
find the smallest key among n elements among the remaining n-1 
elements and etc. Obviously, each time it is necessary

perform K-1 comparisons, where K-the number of remaining items. 
Improve method can only leave on each pass more information 
about the structure of the array. The most convenient in this 
case is to present an array of binary tree. D. Williams was 
offered special structure of the tree-pyramid.

It is defined as a sequence
key h (L), h (L +1 ),..., h (R), such
that


  h (i) <= h (2 * i) and

  h (i) <= h (2 * i +1) for i = L, ..., R / 2


                                 (3.5)


    Ie upstream element is not always
less than the lower. In particular, the top of the tree is min 
element. 


       h1 March 3

     / / 42

   / / 6

  h2h3 426 1955
 / / / / 94
h4 h5 h6 h7 55 94 18 December 1918

                                      12


    Fig. 3.1 The Pyramid of the seven elements


    In theory it is shown that for such
structure, you can add elements to the left. Then to move the 
new element to the desired location (from top) will need a 
maximum of log (n) comparisons. 

    R. Floyd proposed a method for constructing
pyramid in the same place. " Here, h1,
..., Hn-one array, and hm, ...,
hn (where m = (n div 2) +1.) already form a pyramid, because 
the indices i, j, satisfying the conditions j = 2 * i, j = 2 * 
i +1, just does not exist. These elements form

lower level of the pyramid (Figure 3.1),
have no ordering is required. Now the pyramid is expanding to 
the left; every time and added shifts put in the proper 
position of the new element. 

    In order to obtain not only
partial, but complete ordering
among the elements necessary to do the shifting n steps, and 
after each step pushed to the top of the minimum

element.

    The algorithm is described as follows:

/ /
; / / (C) Niklaus Wirth "Algorithms and
; / / Data structures "
; / / -> Source written on Modula-2.
/ /
; / / PROCEDURE HeapSort;
; / / VAR L, R: index; x: item;
/ /
; / / PROCEDURE sift (L, R: index);
; / / VAR i, j: index; x: item;
; / / BEGIN i: = L; j: = 2 * L; x: = a [L];
; / / IF (j <R) '(a [j]  1 DO L: = L-1;
; / / Sift (L, R) END; (* R = n *)
; / / WHILE R> 1 DO x: = a [1];
; / / A [1]: = a [R]; a [R]: = x;
; / / R: = R-1; sift (L, R) END;
; / / (* L = 1 *)
; / / END HeapSort;
/ /
;

    The effectiveness of the algorithm. In the worst
If need n / 2 shear steps, they
shift the items on the log (n / 2),
log (n/2-1), ..., log (n-1) positions. Hence, the sorting phase 
requires n-1 shifts with at most log (n-1)

log (n-2), ..., 1 movement. Except
that need more n-1 displacement for seepage shifted element to 
some distance to the right. These considerations show that even 
in the worst of possible cases HeapSort require n *

log n steps. Outstanding performance in such bad cases, one of 
the attractive properties HeapSort.


    It is not clear when to expect the worst (or best) 
performance. But in general it seems that HeapSort "loves" the 
initial order in which elements are more or less sorted in 
reverse order. Therefore, its behavior is somewhat unnatural. 
If we deal with in reverse order, then the phase of generating 
a pyramid does not requires movement. The average number of 
displacements is approximately equal to (n / 2) * log (n), 
where the deviations from this value is relatively small.