Bài Giảng điện tử Phân tích và thiết kế giải thuật. Tiến sĩ Dương Tuấn Anh. Chương 2: Phân tích độ phức tạp của một số giải thuật sắp thứ tự và tìm kiếm. Xét những phương pháp sắp thứ tự một tập tin gồm các mẫu tin có chứa khoá. Khoá mà lại 1 phần của mẫu tin, được dùng để điều khiển việc sắp thứ tự.
Ch ng Ph n t#ch ph c t p c a m t s gi i thu t s p th t v% t'm ki m N i dung V%i ph ng ph p s p th t c n b n Quicksort X p th t d a v%o c s X p th t b ng ph ng ph p tr n X p th t ngo i V%i ph ng ph p t'm ki m c n b n Nguy n t c v s p th t X t nh ng ph ng ph#p s p th t m t t p tin g m c#c m u tin (record) c% ch a kh%a (key) Kh%a m' l' m t ph n c d)ng i u n vi c s p th t c a m u tin, M c ti+u: s p x p c#c m u tin cho c#c tr kh%a c a ch-ng c% th t theo m t qui lu t th t n'o % c s p th t c% th ch a b nh N u c#c t p tin ch.nh th/ gi i thu t s p th t c g i l' s p th t n i (internal sorting) Vi c s p th t t p tin l u t ngo i (external sorting) b nh ph c g i l' s p th Hai nh m ph ng ph p s p th t Ch-ng ta quan t m n th i gian t.nh to#n c a c#c gi i thu t s p th t M t nh%m g m ph ng ph#p c n b n 1i h i th i gian t.nh to#n t l v i N s p th t N ph n t C#c ph ng ph#p ti+n ti n h n c% th s p th t N ph n t th i gian ch y t l v i NlgN M t c t.nh c a ph ng ph#p s p th t l' t.nh n nh (stability) M t ph ng ph#p s p th t c g i l' n nh c th t t ng i c a c#c ph n t n% b o to'n c)ng tr kh%a t p tin Nh m ph ng ph p c n b n V i nh m n y, c hai ph ch n kh o s# t: ng ph p s p th t c - s p th t b ng ph ng ph# p ch n (selection sort) - s p th t b ng ph ng ph# p ch2n (insertion sort) V i m c ch t p trung v o kh.a c nh gi i thu t ta s l' m vi c v i c c ph ng ph# p m' n ch s p th t c# c m ng s nguy+n theo th t l n d n c a s S p th t b ng ph ng ph p ch n t ng: Tr c ti+n t m ph n t nh nh t m ng v ho#n i n% v i ph n t ang v tr th nh t m ng ' r i t/m ph n t nh th nh/ m ng v' ho#n i n% v i v' c th cho ph n t ang v tr th nh/ m n to'n m ng c s p th t 390 205 182 45 235 205 182 390 235 205 390 235 390 235 Gi i thu t s p th t b ng ph ng ph p ch n procedure selection; var i, j, min, t: integer; begin for i :=1 to N-1 begin :=i; for j :=i+1 to N if a[j] v begin a[j] := a[j-1]; // pull down j:= j-1 end; a[j]:=v; end; end; 10 X p th merg t ngo i b ng p.p tr n External Sor K thu t th9ng d ng nh t s p th t ngo i l gi i thu t s p th t ngo i b ng ph ng ph#p tr n (external sort-merge algorithm) Ph ng ph#p s p th t ngo i n'y g m b c: t o c#c run tr n run M: s trang (page) c a b buffer) m b nh ch.nh (memory- 42 X p th Trong b sau: i = 0; repeat t ngo i b ng p.p tr n c 1, m t s run c th t c t o b ng c#ch blocks of the file, or the rest of the file, whichever is smaller; sort the in-memory part of the file; write the sorted data to the run file Ri; i = i+1; until the end of the file Trong b #c run c tr n l i 43 Tr n run Tr ng h p c bi t: s s r < M Ta c th d nh trang c a b m cho m i run v d nh ch b nh c1n l i ch a m t trang c a k t qu xu t Gi i thu t ph n tr n run nh sau: ead one block of each of the N files Ri into a buffer page in memory; repeat choose the first record (in sort order) among all buffer pages; write the tuple to the output, and delete it from the buffer page; if the buffer page of any run Ri is empty and not end-of-file(Ri) then read the next block of Ri into the buffer page; until all buffer pages are empty 44 Tr n run ng h p t ng qu T#c v tr n l' s kh#i qu#t h%a c a ph p tr n hai ng (two-way merge) c d)ng b i gi i thu t s p th t n i b ng ph ng ph#p tr n N% tr n N run, % n% c g i l' tr n nhi u ng (n-way merge) Tr ng h p t ng qu#t: V t ng qu#t, n u t p tin l n h n s c ch a c a b m N>M th/ kh9ng th d'nh m t trang b m cho m i run b c tr n Trong tr ng h p n'y, s tr n ph i tr i qua nhi u chuy n (passes) V/ ch c% M-1 trang c a b m d'nh cho c#c u v'o, s tr n c% th ti p nh n M-1 runs nh l' c#c u v'o 45 Tr n run [tr ng h p t ng qu t] tt Chuy n tr n u ti+n l m vi c nh sau: M-1 run u ti+n c tr n l i th nh m t run cho chuy n k ti p R i th M-1 runs s c tr n theo c#ch t ng t v' c th cho n t t c c#c run u ti+n u c gi i quy t T i i m n'y, t ng s run c gi m i m t th a s M-1 N u s run c gi m i n'y v n c1n M, m t chuy n n as c th c thi v i c#c run c t o b i chuy n u ti+n l'm u v'o M i chuy n l'm gi m t ng s run m t th a s M : C#c chuy n c l p l i nhi u nh c n thi t cho n t ng s run nh h n M; chuy n cu i c)ng s t o k t qu l' m t t p tin c% th t 46 M t th# d c a th t ngo i b ng p.p tr n s : i) m t m u tin chi m v a m t kh i ii) b m chi m trang Trong giai o n tr n, hai trang c d)ng l'm v' m t trang c d)ng ch a k t qu u v'o Giai o n tr n 1i h i hai chuy n 47 a 19 d 31 a 19 d 31 c 33 b 14 e 16 r 16 d 21 m3 p d a 14 a b c d e b 14 c 33 e 16 d 31 m r 16 a 14 d d 21 m3 p r 16 a 14 d 17 p T o run 19 14 33 31 16 tr n pass a 14 a 19 b 14 c 33 d d 21 d 31 e 16 g 24 m3 p r 16 tr n pass 48 ph c t p c a x p th t ngo i H y t.nh s truy t kh i (block accesses) c a gi i thu t s p th t ngo i b ng ph ng ph#p tr n br : t ng s kh i c a t p tin Trong giai o n t o run, m t kh i m t t ng s 2br truy t kh i T ng s run ban u l' T ng s chuy n tr n: c c v' ghi, em l i br/M log M-1(br/M) Trong m i chuy n tr n, t ng kh i c a t p tin l n v' ghi m t l n c cm t 49 ph c t p c a x p th t ngo i T ng s truy t a cho gi i thu t s p th t ngo i b ng ph ng ph#p tr n l': 2br + 2br logM-1(br/M) t o run = 2br( logM-1 (br/M) +1) c#c chuy n tr n 50 T'm ki m tu n t Ph ng ph#p n gi n nh t t/m ki m l' l u tr c#c m u t/m ki m m t m u t uy t qua tin m t m ng ' to'n b m ng m t c#ch tu n t type node = record key, info: integer end; var a: array [0 maxN] of node; N: integer; procedure initialize; begin N: = end; function seq_search (v: integer, x: integer): integer; begin a[N+1].key: = v; /*sentinel */ if xr); if v = a[x].key then binarysearch: = x else binarysearch: = N+1 end; Ph 55 ph c t p c a gi i thu t t'm ki m chia i H th c truy h i c a gi i thu t n y l : CN CN/2 + T.nh ch t: T m ki m chia 1i kh1ng bao gi 2i h i nhi u h n lgN + so s nh cho m t s t'm ki m th#nh c1ng hay kh1ng th#nh c1ng 56 ... N-1: NCN : (N-1) CN-1 = N(N+1) : (N-1)N + 2CN-1 T % ta c NCN = (N+1)CN-1 + 2N 21 Chia c hai v v i N(N+1) ta c h th c truy h i: CN (N+1) = CN-1/N + 2/ (N+1) = CN -2 /(N-1) + 2/ N + 2/ (N+1) N 2/ (k+1)... c thi N-1 l n Tr ng h p x u nh t x y m ng c% th t o c th c thi v i t ng s ng c Khi %, v1ng l p l n sau 0y: (N-1) + (N -2 ) + + =N(N-1) /2 =O(N2) S b c chuy n = N(N-1) /2 S so s#nh = N(N-1) /2 Trung... ph n t ch2n n% v'o v tr -ng c s p th t r i 45 20 5 1 82 45 23 5 1 82 45 23 5 45 23 5 45 23 5 23 5 Gi i thu t s p th t b ng ph ng ph p ch n procedure insertion; var i; j; v:integer; begin for i: =2 to N