(insertion sort) . : , , (. 1.1).
Insertion-Sort, [1..] ( n, ). length[A].
. 1. Insertion-Sort = (5,2,4,6,1,3). j .
, (in place): . Insertion-Sort .
1 for (j=2;j<=n;j++){
2 key=A[j];
3 i=j-1;
4 while (i>0 && A[i]>key){
5 A[i+1]=A[i];
6 i=i-1;
7 }
8 A[i+1]=key;
9 }
. 1.2 = (5,2,4,6,1,3). A[1.. j-1 ] , a A[j + 1..n] . for j . A[j] ( 2 ) ( (j-1)-) , ( 3-6). 8 A[j] .
, , ( , ), . , , . (random-access machine, RAM), .
: . : , . . (, , : , .)
(input size)? . (, ). , . , (, ).
|
|
(running time) , , . , ( - x-). (call) ( ) (execution), .
, Insertion-Sort ( ) , . j 2 n ( n = length[A] ) , 4, tj. (, , , .)
Insertion-Sort(A)
1 for(j=2;j<=n;j++){ c1 n
2 key=A[j]; c2 n-1
3 i=j-1; c3 n-1
4 while (i>0 && A[i]>key){ c4 ∑j=2ntj
5 A[i+1]=A[i]; c5 ∑j=2n(tj-1)
6 i=i-1; c6 ∑j=2n(tj-1)
7 }
8 A[i+1]=key; c8 n-1
9 }
, m , cm . ( !) ,
T(n)=c1n+c2(n-1) +c3(n-1)+c4∑j=2ntj+c5∑j=2n(tj-1)+c6∑j=2n(tj-1)+c8(n-1)
, n, , n . Insertion-Sort , . 4 ( [i]≤key i=j-1), tj 1,
T(n)=c1n+c2(n-1) +c3(n-1)+c4(n-1) +c8(n-1)= (c1+2+3+4+ 8)n - (2+3+4+ 8).
, (n), , (linear function) n, .. (n) = n-b b. ( 1,...,8.)
() , : A[j] [1],..., A[j-1]. tj=j.
∑j=2nj=n(n+1)/2-1, ∑j=2n(j-1)=n(n-1)/2,
,
()=1+2(-1) +3(-1) + 4 (n(n+1)/2-1)+c5+c6)(n(n-1)/2)+c8(n-1)= 0.5(c4+c5+c6)n2+(c1+c2+c3+0.5(c4-c5-c6+c8)n-(c2+c3+c4+c8).
(n) (quadratic function), .. ()=an2 + bn + . ( , b c c1,...,8.)