, 1976 -. :
a) ;
b) .
. . :
a) ;
b) () ;
c) ;
d) ;
e) . (, ) ;
f) , , . , , .
, , , , . , . while if.
, . , .
. :
a) ;
b) .
- FALSE TRUE.
:
a) : , - ;
b) : , - , - ;
c) : , .
. :
Insertion_Sort(A)
1 for j 2 to length[ A ]
2 do key A [ j ]
3 i j 1
4 while i > 0 A [ i ] > key
5 do A [ i + 1] A [ i ]
6 i i 1
7 A [ i + 1] key
8 endfor
:
|
|
1. . , .
:
1 for j 2 to length[ A ]
2 do key A [ j ]
2 i j 1
3 4 while i > 0 A [ i ] > key
5 do A [ i + 1] A [ i ]
6 i i 1
7 A [ i + 1] key
8 end for
length[ A ] ó N.
( 1).
1 Insertion_Sort
2. . :
a) ;
b) ;
c) .
, 6.
3. , :
1: 1-8 // N > 1,
2: 1-2-3-7-8 // N > 1
3: 1-2-3-4-7-8 // N > 1,
4: 1-2-3-4-5-6-7-8 // N = 1
5: 1-2-3-4-5-6-7-1-8 // N > 3
6: 1-2-3-4-5-6-3--7-8 // N > 1
4. ():
1: : N = 1, A = {5} .
: A = {5}; .
2: : N = 5, A = {5, 10, 1, 18, 6} 2 N .
: A = {1, 5, 6, 10, 18}; .
3: : N = 5, A = {5, 10, 1, 18, 6} ( 2 N) (i > 0).
: A = {1, 5, 6, 10, 18}; .
4: : N = 7, A = {1, 2, 3, 5, 6, 9, 29} 2 N .
: A = {1, 2, 3, 5, 6, 9, 29}; .
5: : N = 5, A = {5, 10, 1, 18, 6} ( 2 N) (i i 1).
: A = {1, 5, 6, 10, 18}; .
6: : N = 4, A = {99, 78, 2, 41} i, i 3.
: A = {2, 41, 78, 99}; .