ÿþD r A l e k s a n d e r K l o s o w
P W S Z L e g n i c a , 2 0 0 3
w w w . s t r o n y . w p . p l / w p / k l o s o v /
A l g o r y t m y i S t r u k t u r y D a n y c h
W y k Ba d 4
S O R T O W A N I E
P O W T Ó R Z E N I E
F u n k c j a n a z y w a s i r e k u r e n c y j n , j e |e l i w t r a k c i e
w y k o n a n i a o d w o Bu j e s i d o s a m e j s i e b i e
I s t n i e j r ó |n e t y p y r e k u r e n c j i :
- N a t u r a l n a ;
- T e r m i n a l n a ;
- Z p a r a m e t r e m ;
- W i e l o k r o t n a i i n n e .
D e r e k u r s y w a c j n a z y w a m y p r o c e s p r z e k s z t a Bc e n i a p r o g r a m u r e k u r e n c y j n e g o
n a p r o g r a m i t e r a c y j n y
! R o z w i z a s a m o d z i e l n i e :
- W s p o s ó b r e k u r e n c y j n y o d w r ó c i k o l e j n o [ e l e m e n t ó w w t a b l i c y T [ N ]
- Z n a l e z s u m e l e m e n t ó w t a b l i c y T [ N ] w s p o s ó b r e k u r e n c y j n y
S O R T O W A N I E
S O R T O W A N I E
D e f i n i c j a
- S o r t o w a n i e m n a z y w a m y p r o c e s u s t a w i a n i a z b i o r u o b i e k t ó w
w o k r e [l o n y m p o r z d k u .
M o t y w a c j a
- U Ba t w i w y s z u k i w a n i e d a n y c h
W y m a g a n i e
- O s z c z d n e k o r z y s t a n i e z p a m i c i
( n . p . , s o r t u j c t a b l i c l i c z b n i e m o |n a k o r z y s t a z d o d a t k o w e j t a b l i c y )
K L A S Y F I K A C J A M E T O D S O R T O W A N I A
S o r t o w a n i e p r o s t e S o r t o w a n i e s z y b k i e
- P r o s t e w y b i e r a n i e ( s e l e c t i o n s o r t ) - M e t o d a S h e l l ' a
- P r o s t e w s t a w i a n i e ( i n s e r t i o n s o r t ) ( m a l e j c y c h p r z y r o s t ó w )
- P r o s t a z a m i a n a ( e x c h a n g e s o r t ) - S c a l a n i e c i g ó w
- K o p c o w a n i e ( s t o g o w e , h e a p s o r t )
- Q u i c k s o r t ( s o r t o w a n i e p r z e z p o d z i a B)
Z a l e t y p r o s t y c h m e t o d :
1 ) P r o g r a m y s k r ó t k i e , Ba t w e d o z r o z u m i e n i a , z a j m u j m n i e j p a m i c i
2 ) S s z y b s z e d l a m a Be j l i c z b y e l e m e n t ó w
3 ) L e p i e j n a d a j s i d o w y j a [n i e n i a z a s a d s o r t o w a n i a
M I A R A E F E K T Y W N O ZC I S O R T O W A N I A
K r y t e r i u m : o s z c z d n e z u |y c i e c z a s u
M i a r a : l i c z b a k o n i e c z n y c h p o r ó w n a D + l i c z b a k o n i e c z n y c h p r z e s u n i
P O + P R
M e t o d y p r o s t e O ( n 2 )
M e t o d y s z y b k i e O ( n l o g 2 ( n ) )
O ( ) - f u n k c j a z Bo |o n o [c i t e o r e t y c z n e j a l g o r y t m ó w z a s y m p t o t y c z n g r a n i c g ó r n
. . . i s t n i e j r ó w n i e | :
˜( ) - . . . z a s y m p t o t y c z n g r a n i c g ó r n o r a z d o l n
o ( ) - . . . z g ó r n g r a n i c a s y m p t o t y c z n i e n i e d o k Ba d n a
Z AO {O N O Z T E O R E T Y C Z N A A L G O R Y T M Ó W
D o k Ba d n a l i c z b o p e r a c j i p o r ó w n a n i a o r a z p r z e p i s a n i a s t a n o w i
p r a k t y c z n z Bo |o n o [ a l g o r y t m u T ( n ) .
T y p f u n k c j i m a t e m a t y c z n e j , k t ó r a w n a j w i k s z y m s t o p n i u w y z n a c z a w i e l k o [
T ( n ) n a z y w a m y z Bo |o n o [c i t e o r e t y c z n O ( f ( n ) )
T ( n ) O ( ) - k l a s a a l g o r y t m u
2 n + 5 O ( n )
5 n + 8 O ( n )
2 n 2 + 3 n + 2 O ( n 2 )
a n 3 + 2 n 2 + 8 O ( n 3 )
2 n + n 2 + 2 O ( 2 n )
S O R T O W A N I E m e t o d p r o s t e j z a m i a n y
b b e l k o w e
2 5 4 1 3 6
1 . S p r a w d z a m y c a B t a b l i c o d p o c z t k u d o k o Dc a , p o r ó w n u j c z a w s z e d w a
s s i e d n i e e l e m e n t y
2 . J e |e l i t r a f i m y n a p a r e l e m e n t ó w , w k t ó r e j w i k s z y p o p r z e d z a m n i e j s z y t o
z a m i e n i a m y j e m i e j s c a m i .
3 . C z y n n o [ p o w t a r z a m y t a k d Bu g o a | p o d c z a s s p r a w d z a n i a c a Be j t a b l i c y , n i e
z a j d z i e a n i j e d n a z a m i a n a e l e m e n t ó w
S O R T O W A N I E m e t o d p r o s t e j z a m i a n y
R e a l i z a c j a k l a s y c z n a - C
v o i d b u b b l e _ s o r t ( i n t * t a b , i n t n )
{ i n t z m i a n a ;
d o {
z m i a n a = 0 ; / / b r a k z m i a n
f o r ( i n t i = 1 ; i < n ; i + + )
i f ( t a b [ i - 1 ] > t a b [ i ] )
{ / / z a m i a n a s s i e d n i c h e l e m e n t ó w
i n t t m p = t a b [ i - 1 ] ;
t a b [ i - 1 ] = t a b [ i ] ;
t a b [ i ] = t m p ;
z m i a n a = 1 ; / / j e s t z m i a n a
}
} w h i l e ( z m i a n a ) ;
}
S O R T O W A N I E m e t o d p r o s t e j z a m i a n y
R e a l i z a c j a z m o d y f i k o w a n a - P a s c a l
p r o c e d u r e b u b b l e _ s o r t ( v a r t a b : a r r a y [ 1 . . n ] o f i n t e g e r ) ;
v a r i , j , t m p : i n t e g e r ;
b e g i n f o r i : = 2 t o n d o
b e g i n f o r j : = n d o w n t o i d o
i f t a b [ j - 1 ] > t a b [ j ] t h e n
b e g i n
t m p : = t a b [ j - 1 ] ;
t a b [ j - 1 ] : = t a b [ j ] ;
t a b [ j ] : = t m p ;
e n d
e n d
e n d
S O R T O W A N I E m e t o d p r o s t e j z a m i a n y
A n a l i z a z Bo |o n o [c i
P O P R T ( n )
m i n 0 . 5 ( n 2 - n ) 0 0 . 5 ( n 2 - n )
[r 0 . 5 ( n 2 - n ) 0 . 7 5 ( n 2 - n ) 1 . 2 5 ( n 2 - n )
m a x 0 . 5 ( n 2 - n ) 1 . 5 ( n 2 - n ) 2 ( n 2 - n )
Z Bo |o n o [ t e o r e t y c z n a : O ( n 2 )
S O R T O W A N I E m e t o d p r o s t e g o w y b i e r a n i a
2 5 4 1 3 6
1 . W y b i e r a m y n a j m n i e j s z y e l e m e n t t a b l i c y
2 . W y m i e n i a m y g o z p i e r w s z y m e l e m e n t e m
3 . P o w t a r z a m y o p e r a c j e 1 - 2 d l a p o z o s t a By c h n - 1 e l e m e n t ó w , n a s t p n i e d l a n - 2 i
t . d . a | p o z o s t a n i e 1 e l e m e n t .
S O R T O W A N I E m e t o d p r o s t e g o w y b i e r a n i a
R e a l i z a c j a - P a s c a l
p r o c e d u r e p r o s t e _ w y b i e r a n i e ( v a r t a b : a r r a y [ 1 . . n ] o f i n t e g e r )
v a r i , j , k , m i n : i n t e g e r ;
B E G I N f o r i : = 1 t o n - 1 d o
b e g i n
k : = i ; / / p o z y c j a n a j m n i e j s z e g o e l e m e n t u
m i n : = a [ i ] ; / / n a j m n i e j s z y e l e m e n t
f o r j : = i + 1 t o n d o / / p t l a w y z n a c z a j c a n a j m n i e j s z y e l e m e n t
i f a [ j ] < m i n t h e n
b e g i n
k : = j ;
m i n : = a [ j ] ;
e n d ;
a [ k ] : = a [ i ] ; / / w y m i a n a p i e r w s z e g o z n a j m n i e j s z y m
a [ i ] : = m i n ;
e n d
E N D
S O R T O W A N I E m e t o d p r o s t e g o w y b i e r a n i a
A n a l i z a z Bo |o n o [c i
P O P R T ( n )
m i n 0 . 5 ( n 2 - n ) 3 ( n - 1 ) 0 . 5 n 2 + 2 . 5 n - 3
[r 0 . 5 ( n 2 - n ) n ( l n ( n ) + 0 . 5 7 ) 0 . 5 n 2 + n ( l n ( n ) + 0 . 0 7 )
m a x 0 . 5 ( n 2 - n ) 0 . 2 5 n 2 + 3 ( n - 1 ) 0 . 7 5 n 2 + 2 . 5 n - 3
Z Bo |o n o [ t e o r e t y c z n a : O ( n 2 )
S O R T O W A N I E m e t o d p r o s t e g o w s t a w i a n i a
2 5 4 1 3 6
1 . E l e m e n t y s p o d z i e l o n e u m o w n i e n a c i g w y n i k o w y o r a z c i g zr ó d Bo w y
2 . W k a |d y m k r o k u p o c z w s z y o d i = 2 i z w i k s z a j c i o j e d e n , i - t y e l e m e n t
c i g u zr ó d Bo w e g o p r z e n o s i s i d o c i g u w y n i k o w e g o , w s t a w i a j c g o w
o d p o w i e d n i e m i e j s c e .
3 . P r o c e s p r z e n o s z e n i a i - g o e l e m e n t u k o Dc z y s i k i e d y :
a ) z n a l e z i o n o j - t y e l e m e n t m n i e j s z y n i | i - t y e l e m e n t
b ) o s i g n i t o l e w y k o n i e c c i g u w y n i k o w e g o
S O R T O W A N I E m e t o d p r o s t e g o w s t a w i a n i a
R e a l i z a c j a - P a s c a l
p r o c e d u r e p r o s t e _ w s t a w i a n i e ( v a r t a b : a r r a y [ 1 . . n ] o f i n t e g e r )
v a r i , j , t m p : i n t e g e r ;
B E G I N
f o r i : = 2 t o n d o
b e g i n t m p : = a [ i ] ; / / e l e m e n t w s t a w i a n y
a [ 0 ] : = t m p ; / / w a r t o w n i k
j : = i - 1 ; / / e l e m e n t c i g u w y n i k o w e g o
w h i l e t m p < a [ j ] d o
b e g i n
a [ j + 1 ] : = a [ j ] ; / / p r z e s u n i c i e w p r a w o
j : = j - 1 ; / / n a s t p n y e l e m e n t
e n d ;
a [ j + 1 ] : = t m p ; / / w s t a w i e n i e e l e m e n t u
e n d
E N D
S O R T O W A N I E m e t o d p r o s t e g o w s t a w i a n i a
A n a l i z a z Bo |o n o [c i
P O P R T ( n )
m i n n - 1 2 ( n - 1 ) 3 ( n - 1 )
[r 0 . 2 5 ( n 2 + n - 2 ) 0 . 2 5 ( n 2 + 9 n - 1 0 ) 0 . 5 ( n 2 + 5 n - 6 )
m a x 0 . 5 ( n 2 + n ) - 1 0 . 5 ( n 2 + 3 n - 4 ) n 2 + 2 n - 3
Z Bo |o n o [ t e o r e t y c z n a : O ( n 2 )
P O R Ó W N A N I E M E T O D S O R T O W A N I A P R O S T E G O
M e t o d a s o r t o w a n i a K l a s a N a j l e p s z y w y n i k N a j g o r s z y w y n i k
T ( 1 0 0 ) T ( 1 0 0 )
P r o s t a z a m i a n a O ( n 2 ) 9 9 5 0 1 9 8 0 0
P r o s t e w y b i e r a n i e O ( n 2 ) 5 2 4 7 7 7 4 7
P r o s t e w s t a w i a n i e O ( n 2 ) 2 9 7 1 0 1 9 7
M e t o d a s o r t o w a n i a K l a s a N a j l e p s z y w y n i k N a j g o r s z y w y n i k
T ( 1 0 ) T ( 1 0 )
P r o s t a z a m i a n a O ( n 2 ) 4 5 1 8 0
P r o s t e w y b i e r a n i e O ( n 2 ) 7 2 9 7
P r o s t e w s t a w i a n i e O ( n 2 ) 2 7 1 1 7
J A K P O L I C Z Y Z AO {O N O Z P R A K T Y C Z N ?
v o i d b u b b l e _ s o r t ( i n t * t a b , i n t n )
{ i n t z m i a n a ; i n t p o = 0 , p r = 0 ;
d o {
p r + + , z m i a n a = 0 ;
f o r ( p r + + , i n t i = 1 ; p o + + , i < n ; i + + )
i f ( p o + + , t a b [ i - 1 ] > t a b [ i ] )
{ p r + = 4 ;
i n t t m p = t a b [ i - 1 ] ;
t a b [ i - 1 ] = t a b [ i ] ;
t a b [ i ] = t m p ;
z m i a n a = 1 ;
}
} w h i l e ( p o + + , z m i a n a ) ;
}
W N I O S K I
1 . N a j s z y b s z j e s t m e t o d a p r o s t e g o w y b i e r a n i a
2 . M e t o d a b b e l k o w a j e s t n a j p o w o l n i e j s z a w w i k s z o [c i w y p a d k a c h
3 . M e t o d a p r o s t e g o w s t a w i a n i a j e s t n a j l e p s z a d l a c z [c i o w o l u b c a Bk o w i c i e
u p o r z d k o w a n y c h c i g ó w
4 . M e t o d a b b e l k o w a n a j l e p i e j s i n a d a j e d l a c i g ó w d Bu g o [c i < 3 0
Wyszukiwarka
Podobne podstrony:
AiSD w4 sortowanie2F2 W4 dielektrykiw4ML1 W4 1 (2)W4 MECH ENW4 PODSTAWY PROJEKTOWANIA KONSTRUKCJI NSW4 Wymiana gospodarcza z zagranicaFinanse w4W4 ZIP Podstawy metrologii elektPrzykład do W4hih w4pca w4TSZ MBM w4notatki W4W4 3therawchef com the raw chef Lime amp Ginger Mascarpone IceCreamC w4 funkcje mem lancuchyw4więcej podobnych podstron