[̲] [] []

 

8.

8.1.

8.2.

8.2.1.

8.2.1.1.

8.2.1.2.

8.2.1.3.

8.2.1.4.

8.2.1.5.

8.2.1.6.

8.2.2.

 

8.

 

- , , , - . , , .

, .

.

 

8.1.

 

. , , , . , n a t, a t :

 

t = [1..n] t;

a: t;

 

t : {=, <>, <, >, >=, <=}.

 

, . :

 

LinSearch (a: t; x: t):

i: ; b: ;

i <- 0; b <- ;

(i<n) & Øb

i <- i+1;

b <- a[i] = x

;

b LinSearch <- i

LinSearch <- 0

;

 

LinSearch , x, , 0, . , n, O(n).

: ? ³ , . , , a[1] <= a[2] <= ... <= a[n]. , , :

x . 1, n.

, x, . x .

:

 

BinSearch (a: t; x: t):

l, r, m: ; b: ;

l <- 1; r <- n; b <- ;

(l<=r) & Øb

m <- (l+r) div 2; { }

a[m]=x b <

a[m]<x l <- m+1 { }

r <- m-1 { }

;

b BinSearch <- m

BinSearch <- 0

;

 

l , r . , . , x, 2 , log2n, O(log2n).

. , , , , , x, .

 

BinSearch2 (a: t; x: t):

l, r, m: ;

l <- 1; r <- n;

l<r

m <- (l+r) div 2;

a[m]<x l <- m+1

r <- m

;

a[l]=x BinSearch2 <- l

BinSearch2 <- 0

;

 

, log2n n, , , . . , .

 

8.2.

 

. .

, , ( - ). , () ( , .

a1, a2, ..., an . k(ai) ai, i=1, 2, ..., n. ϳ a1, a2, ..., an ai1, ai2, ..., ain, :

 

k(ai1)<=k(ai2)<=...<=k(ain)

 

, ai aj . , , ai aj , k(ai)=k(aj) i<j, ai aj.

 

8.2.1.

 

, . O(n2) , O(nlog2n).

, , :

 

t = [1..n] t;

a: t;

 

t : {=, <>, <, >, >=, <=}.

k(a[i])=a[i], i=1, 2, ..., n. , n=8, (23,55,47,35,10,90,84,30).

 

8.2.1.1.

 

(n-1) . , i=2 i , i- 1 i, .

:

 

i <- 2 n

x <- a[i];

x a[1] ... a[i]

 

ij x a[1] ... a[i] -. x a[j] x>=a[j] . :

 

StraightInsertion ( a: t)

i, j: ; x: t; b: ;

i <- 2 n

x <- a[i]; j <- i; b <- ;

(j > 1) & Øb

b <- x>=a[j-1];

Øb a[j] <- a[j-1]; j <- j-1

;

a[j] <- x

 

.

, O(n2). ij, (n-1) , , , n div 2 .

:

23 55 47 35 10 90 84 30

i=2 23 55 47 35 10 90 84 30

i=3 23 47 55 35 10 90 84 30

i=4 23 35 47 55 10 90 84 30

i=5 10 23 35 47 55 90 84 30

i=6 10 23 35 47 55 90 84 30

i=7 10 23 35 47 55 84 90 30

i=8 10 23 30 35 47 55 84 90

 

, i- , 1 (i-1) . :

 

BinaryInsertion ( a: t)

i, j, l, r, m: ; x: t;

i <- 2 n

x <- a[i]; l <- 1; r <- i;

l<r

m <- (l+r) div 2;

a[m]<=x l <- m+1

r <- m

;

j <- i r+1 -1

a[j] <- a[j-1]

;

a[r] <- x

 

(O(nlog2n)), . , . , , ( ) , .

 

8.2.1.2.

 

, i 1 (n-1), a[i], a[i+1], ..., a[n] k, a[i] a[k].

:

 

i <- 1 n-1

k <- a[i] ... a[n];

a[i] a[k]

 

䳿 k <- a[i] ... a[n] a[i] a[k], :

 

Selection ( a: t)

i, j, k: ; x: t;

i <- 1 n-1

k <- i;

j <- i+1 n

a[j]<a[k] k <- j

;

x <- a[i]; a[i] <- a[k]; a[k] <- x

 

:

23 55 47 35 10 90 84 30

i=1 10 55 47 35 23 90 84 30

i=2 10 23 47 35 55 90 84 30

i=3 10 23 30 35 55 90 84 47

i=4 10 23 30 35 55 90 84 47

i=5 10 23 30 35 47 90 84 55

i=6 10 23 30 35 47 55 84 90

i=7 10 23 30 35 47 55 84 90

 

.

, O(n2). ij, (n-1) , , , n div 2 .

 

8.2.1.3.

 

. . . , () ( ດ ).

:

 

BubbleSort ( a: t)

i, j: ; x: t;

i <- 2 n

j <- n i -1

a[j-1]>a[j]

x <- a[j-1]; a[j-1] <- a[j]; a[j] <- x

;

 

:

23 55 47 35 10 90 84 30

i=2 10 23 55 47 35 30 90 84

i=3 10 23 30 55 47 35 84 90

i=4 10 23 30 35 55 47 84 90

i=5 10 23 30 35 47 55 84 90

i=6 10 23 30 35 47 55 84 90

i=7 10 23 30 35 47 55 84 90

i=8 10 23 30 35 47 55 84 90

 

.

, O(n2). (n-1) , , , n div 2 . , . , , (, 6, 7 8 ). .

 

ShakerSort ( a: t)

j, k, l, r: ; x: t;

l <- 2; r <- n; k <- n;

j <- r l -1

a[j-1]>a[j]

x <- a[j-1]; a[j-1] <- a[j]; a[j] <- x;

k <- j

;

l <- k+1;

j <- l r

a[j-1]>a[j]

x <- a[j-1]; a[j-1] <- a[j]; a[j] <- x;

k <- j

;

r <- k-1

l>r

 

k , .

 

( i ):

23 55 47 35 10 90 84 30 l=2, r=8

i=1 10 23 47 35 30 55 84 90 l=3, r=7

i=2 10 23 30 35 47 55 84 90 l=5, r=4

 

, O(n2) .

 

.

 

8.2.1.4.

 

a b m n c (m+n) , a b. :

 

i <- 1; j <- 1; k <- 1;

i<=n & j<=m

a[i]<b[j]

c[k] <- a[i]; i <- i+1

c[k] <- b[j]; j <- j+1

;

k <- k+1

;

i<=n

c[k] <- a[i]; i <- i+1;

k <- k+1

;

j<=m

c[k] <- b[j]; j <- j+1;

k <- k+1

;

 

, : a b. , O(n+m) .

 

i- a ( , ) Size=2i-1. Size*2 b. ϳ a b Size . , Size n. i=1 1 , a.

 

:

 

Size <- 1;

Size a b;

a <- b;

Size <- Size*2;

Size > n;

 

Size a b Merge. r1 , r2 . Size 2, n 2, Size.

 

Merge( a: t; Size: ; b: t)

i, j, k, r1, r2: ;

k <- 1;

k<=n

{ }

i <- k; r1 <- i+Size-1;

r1>n r1 <- n ;

j <- r1+1; r2 <- j+Size-1;

r2>n r2 <- n ;

{ }

i<=r1 & j<=r2

a[i]<a[j]

b[k] <- a[i]; i <- i+1

b[k] <- a[j]; j <- j+1

;

k <- k+1

;

i<=r1

b[k] <- a[i]; i <- i+1;

k <- k+1

;

j<=r2

b[k] <- a[j]; j <- j+1;

k <- k+1

;

;

;

 

a <- b , ... a b, - b a.

:

 

MergeSort ( a: t)

Merge( a: t; Size: ; b: t)

i, j, k, r1, r2: ;

k <- 1;

k<=n

{ }

i <- k; r1 <- i+Size-1;

r1>n r1 <- n ;

j <- r1+1; r2 <- j+Size-1;

r2>n r2 <- n ;

{ }

i<=r1 & j<=r2

a[i]<a[j]

b[k] <- a[i]; i <- i+1

b[k] <- a[j]; j <- j+1

;

k <- k+1

;

i<=r1

b[k] <- a[i]; i <- i+1;

k <- k+1

;

j<=r2

b[k] <- a[j]; j <- j+1;

k <- k+1

;

;

;

i, Size: ; b: t;

i <- 0; Size <- 1;

i <- i+1

i mod 2 = 1 Merge(a, Size, b)

Merge(b, Size, a) ;

Size <- Size*2;

Size >= n;

i mod 2 = 1 a <- b

;

 

:

23 55 47 35 10 90 84 30

i=1 23 55 35 47 10 90 30 84

i=2 23 35 47 55 10 30 84 90

i=3 10 23 30 35 47 55 84 90

 

, O(nlog2n). ij, ... log2n , O(n) . , , n.

 

8.2.1.5.

 

, . x a[i]>x, a[j]<x. , , x, x.

, , , ( ). :

 

QuickSort ( a: t)

Sort( l, r: )

i, j: ; x, y: t;

i <- l; j <- r;

x <- a[(l+r) div 2];

a[i]<x

i <- i+1

;

a[j]>x

j <- j-1;

;

i>j ;

y <- a[i]; a[i] <- a[j]; a[j] <- y;

i <- i+1; j <- j-1

;

l<j Sort(l,j) ;

i<r Sort(i,r) ;

;

Sort(1,n)

;

 

:

23 55 47 35 10 90 84 30

l=1 r=8 x=35 k=1 23 30 10 35 47 90 84 55

l=1 r=3 x=30 k=2 23 10 30 35 47 90 84 55

l=1 r=2 x=23 k=3 10 23 30 35 47 90 84 55

l=5 r=8 x=90 k=4 10 23 30 35 47 55 84 90

l=5 r=7 x=55 k=5 10 23 30 35 47 55 84 90

 

k , , Sort. Sort l=1, r=8 (k=2 k=4), (k=3 k=5 ).

 

, , O(nlog2n). ij, O(n), - log2n. , , n Sort.

 

8.2.1.6.

 

. , 1024, 4096 16384. ( ) Pentium-II/450 . 3 :

1)    ;

2)    , ;

3)    .

 

1024 4096 16384

StraightInsertion 0.00 0.05 0.00 0.00 0.88 0.44 0.00 14.01 6.98

BinaryInsertion 0.00 0.06 0.06 0.00 0.61 0.28 0.05 9.67 4.83

Selection 0.06 0.05 0.00 0.50 0.49 0.49 8.30 8.46 8.29

BubbleSort 0.00 0.11 0.11 0.54 1.70 1.21 8.73 27.79 19.45

ShakerSort 0.00 0.11 0.05 0.00 1.71 0.99 0.00 27.30 15.82

MergeSort 0.00 0.00 0.00 0.00 0.00 0.00 0.05 0.05 0.00

QuickSort 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.05

 

, . , , . , , , m (m<<n).

 

[̲] [] []