H ng d n chi ti t các gi i thu t tìm ki mướ ẫ ế ả ậ ế
Merge sort
Nguyên t c :ắ
VD ta có
12 13 45 32 100 34 65 10
Ta có trên là 8 ph n t c n đ c s p x p :ở ầ ử ầ ượ ắ ế
Ý t ng c a merge sort là thay vì s p x p 8 ph n t (khó s p ) thì ta chia đôi dãy đó ra làmưở ủ ắ ế ầ ử ắ
đôi (s ph n t nh h n --> s p d h n ) và s p x p các dãy con r i ghép 2 dãy con l iố ầ ử ỏ ơ ắ ễ ơ ắ ế ồ ạ
( g i là merge 2 dãy con )ọ
V y ta làm nh sau:ậ ư
Chia đôi --> đ c hai dãy con m i là 12 13 45 32 và 100 34 65 10ượ ớ
s p 2 dãy con l i : 12 13 45 32 g i là dãy Aắ ạ ọ
100 34 65 10 g i là dãy Bọ
+ Mu n s p A ta cũng làm y nh trênố ắ ư
Chia đôi A , đ c 2 dãy m i là A11 = { 12 13 } A12 = {45 32 }ượ ớ
Chia đôi B đ c 2 dãy m i là B11 = {100 34} B12 = {65 10 }ượ ớ
+ S p x p A11, B11 , A12 , B12ắ ế
+ Mu n s p x p A11 thì ta cũng chia đôi đ n khi s p đ cố ắ ế ế ắ ượ
ta có 2 dãy con là A21 = {12} A22 = { 13}
S p 2 dãy con trên đ c ( đ n gi n vì ch có m t ph n t ) là A21 = {12 } A22 = {13}ắ ượ ơ ả ỉ ộ ầ ử
S p xong thì ta merge l i thành A11 = { 12 13 }ắ ạ
+ T ng t s p x p cho B11 , A12 , B12 ta cũng cóươ ự ắ ế
B11 = {34 100} B12 = {10 65 } A12 = {32 45 }
+S p x p xong , ta s merge l i A11 , A12 thành A = { 12 13 32 45 }ắ ế ẽ ạ
B11 , B12 thành B = { 10 34 65 100 }
S p xong A , B , ta s merge chúng l i thành dãy ban đ u :ắ ẽ ạ ầ
{10 12 13 32 34 45 65 100 }
Ph ng pháp merge:ươ
VD A = { 12 13 32 45 }
B = { 10 34 65 100}
Đ u tiên l y ph n t đ u tiên c a A và B : 12 và 10ầ ấ ầ ử ầ ủ
10 < 12 nên ta l y 10 b vào m ng k t qu là C = {10}ấ ỏ ả ế ả
Gi l i s 12 , và l y ti p ph n t thay th 10 trong m ng B là 34ử ạ ố ấ ế ầ ử ế ả
So sánh 12 và 34 . 12 < 34 , l y 12 ra và b vào C = {10 12}ấ ỏ
Gi l i 34 . L y ph n t k ti p đ thay cho 12 trong m ng A là 32ử ạ ấ ầ ử ế ế ể ả
So sánh 32 và 34 ch n 32 b v o C = { 10 12 32 }ọ ỏ ả
........ Làm t ng t ......ươ ự
Đ n b c cu i cùng A h t ph n t B còn l i B = { 65 100}ế ướ ố ế ầ ử ạ
Ta s b toàn b m ng B vào C . K t qu C đã đ c merge và có th tẽ ỏ ộ ả ế ả ượ ứ ự
Gi i thu tả ậ cho tr ng h p dùng list đ ch a các ph n t c n sort)ườ ợ ể ứ ầ ử ầ
Sortable_List là m t l p list có đ c đi m là có hàm sortộ ớ ặ ể
Node là m t template class bi u di n cho các node trong listộ ể ễ
Record là class dùng đ bi u di n data c n s p x p . ( VD nh s p m t dãy các s nguyên ,ể ể ễ ầ ắ ế ư ắ ộ ố
hay VD là s p theo tên c a các record bao g m tên , tu i , s đi n tho i ...)ắ ủ ồ ổ ố ệ ạ
sublist là list c n s p x p ầ ắ ế
Quick sort
Ý t ng:ưở
G n gi ng nh merge sort , ta s chia đôi m ng c n x p r i s p x p các m ng con , sau đóầ ố ư ẽ ả ầ ế ồ ắ ế ả
s ghép m ng con đã s p x p thành m ng ban đ u nh ng đã s p x pẽ ả ắ ế ả ầ ư ắ ế
Đi m khác nhau: Là ch ta chia đôi m ng con theo nguyên t c riêng :ể ổ ả ắ
G i đi m mà t i đó ta chia đôi m ng ban đ u có tr là pivot (không nh t thi t là n m đúngọ ể ạ ả ầ ị ấ ế ằ
v trí chính gi a . Nh ng gi i thu t s ch y t t n u nó n m g n đi m chính gi a) và ta sị ữ ư ả ậ ẽ ạ ố ế ằ ầ ể ữ ẽ
không c n merge 2 dãy con (do đó nhìn chung s ch y nhanh h n ) , th a đi u ki n là t t cầ ẽ ạ ơ ỏ ề ệ ấ ả
nh ng ph n t bên trái pivot đ u nh h n pivot và n m bên ph i pivot thì l n h n pivotữ ầ ử ề ỏ ơ ằ ả ớ ơ
VD :
2 4 6 7 18 14 13
Ta ch n ph n t pivot = 7 ( do bên trái c a nó nh h n pivot = 7 , bên ph i l n h n pivot =ọ ầ ử ủ ỏ ơ ả ớ ơ
7 ) (Th c ra ta ph i tìm pivot , do đây làm b ng tay nên d th y )ự ả ở ằ ễ ấ
Chia đôi : A = { 2 4 6 } B = { 18 14 13 }
+ S p Aắ
+ Trong dãy A ta cũng ch n ph n t pivot là 4ọ ầ ử
+ Đ c 2 dãy con là A11 = {2 } A12 = {6}ượ
+ S p A11 ( s p s n r i )ắ ắ ẵ ồ
+ S p A12 ( s p s n r i )ắ ắ ẵ ồ
+ T o l i m ng A = { A11 đ c s p , pivot , A12 đ c s p } = {2 4 6 }ạ ạ ả ượ ắ ượ ắ
+S p B . Trong B ta không th y đ c pivot do ch n cái nào ta cũng không th y th a .ắ ấ ượ ọ ấ ỏ
Nh ng m c tiêu c a quick sort là làm sao ta đ c dãyư ụ ủ ượ
<C= dãy có tr nh h n pivot > pivot < D= dãy có tr l n h n pivot >ị ỏ ơ ị ớ ơ
S p 2 dãy con C , D r i ghép l i ta đ c dãy s p th t .ắ ồ ạ ượ ắ ứ ự
Vì v y áp d ng m t gi i thu t tìm pivot trong B( s trình bày sau ) ta s đ c C = { 13} Dậ ụ ộ ả ậ ẽ ẽ ượ
= {18} và pivot là 14 .
+ S p dãy con C , D ( do ch có m t ph n t nên không s p , ho c tìm pivot)ắ ỉ ộ ầ ử ắ ặ
+ Ghép l i t o thành m ng B đ c s p B = { 13 14 18 }ạ ạ ả ượ ắ
+Ghép A và B đ t o thành m ng đ c s p x p ban đ uể ạ ả ượ ắ ế ầ
PS : Hi u qu c a gi i thu t quicksort ph thu c r t nhi u vào vi c ch n cho đ c pivotệ ả ủ ả ậ ụ ộ ấ ề ệ ọ ượ
t t ( t c n u pivot n m g n chính gi a thì đ t g n t i u ) ố ứ ế ằ ầ ữ ạ ầ ố ư
Heap Sort
Heap là m t c u trúc d li u , có th đ c bi u di n thông qua 2 cách :ộ ấ ữ ệ ể ượ ể ễ
-D ng th 1: D ng cây nh phân có đ c đi m là node cha thì l n h n 2 node con tr c ti pạ ứ ạ ị ặ ể ớ ơ ự ế
c a nó .ủ
-D ng th 2: n u ta đánh s các node theo th t t trên xu ng và t trái qua . B t đ u làạ ứ ế ố ứ ự ừ ố ừ ắ ầ
node root = 0 , thì ta có th đ nh nghĩa heap thông qua m ng m t chi u , có đ c đi m làể ị ả ộ ề ặ ể
ph n t th k s l n h n các ph n t th 2k+1 và 2k+2 . Ta có th d nh n th y là phàn tầ ử ứ ẽ ớ ơ ầ ử ứ ể ễ ậ ấ ử
th 0 s t ng ng v i root trong cây cách bi u di n th 1ứ ẽ ươ ứ ớ ở ể ễ ứ
Nguyên t c s p x p c a heap sortắ ắ ế ủ
D a vào tính ch t c a heap trong cách bi u di n th 1 và th 2 , ta có th th y ph n t đ uự ấ ủ ể ễ ứ ứ ể ấ ầ ử ầ
tiên trong cách bi u di n theo m ng s là ph n t l n nh t ---> cách s p x p đ n gi n là : (ể ễ ả ẽ ầ ử ớ ấ ắ ế ơ ả
G i m ng ban đ u là A )ọ ả ầ
Kh i t o : T o heap t m ng ban đ u đã cho (m ng A )ở ạ ạ ừ ả ầ ả
1. L y ph n t đ u tiên trong m ng ra b vào m ng k t quấ ầ ử ầ ả ỏ ả ế ả
2. T o l i heap t m ng Aạ ạ ừ ả
3.Quay l i b c 1ạ ướ
VD : Ta l y m t m ng đã đ c t o thành m t heap :ấ ộ ả ượ ạ ộ
y r p d f b k a c
L y ph n t đ u tiên là y b vào m ng k t qu C = { y }ấ ầ ử ầ ỏ ả ế ả
khi này A = r p d f b k a c
T o heap A = r f p d c b k aạ
L y ph n t đ u tiên ra là r b vào m ng C = { r y }ấ ầ ử ầ ỏ ả
Khi này A = { f p d c b k a }
T o heap cho A = { p f k d c b a}ạ
L y ph n t đ u tiên ra là p b vào m ng C = { p r y }ấ ầ ử ầ ỏ ả
Khi này A = { f k d c b a }
T o heap cho A = { k f b d c a}ạ
L y ph n t đ u tiên ra là k b vào m ng C = { k p r y }ấ ầ ử ầ ỏ ả
Khi này A = { f b d c a }
T o heap cho A = { f d b a c}ạ
L y ph n t đ u tiên ra là f b vào m ng C = { f k p r y }ấ ầ ử ầ ỏ ả
Khi này A = { b d c a }
T o heap cho A = { d c b a}ạ
L y ph n t đ u tiên ra là d b vào m ng C = {d f k p r y }ấ ầ ử ầ ỏ ả
Khi này A = { c b a }
T o heap cho A = { c a b }ạ
L y ph n t đ u tiên ra là c b vào m ng C = {c d f k p r y }ấ ầ ử ầ ỏ ả
Khi này A = { b a }
T o heap cho A = { b a }ạ
L y ph n t đ u tiên ra là b b vào m ng C = {b c d f k p r y }ấ ầ ử ầ ỏ ả
Khi này A = { a }
T o heap cho A = { a }ạ
K t thúc ta có đ c m ng C đã có th t .ế ượ ả ứ ự
C i ti n:ả ế
Ta có th h n ch vi c s d ng thêm m ng C b ng cách t n d ng luôn m ng A ban đ u .ể ạ ế ệ ử ụ ả ằ ậ ụ ả ầ
Ta làm nh sauư
A = y r p d f b k a c
B c 1 :ướ
L y y raấ
L y c raấ
B y vào ch c a c .ỏ ổ ủ
B c vào ch c a yỏ ỗ ủ
Khi ta b y vào ch c a c thì gi ng nh ta b y v o m ng C .ỏ ỗ ủ ố ư ỏ ả ả
Khi này m ng A s coi nh g m 2 ph n A = c r p d f b k a ---- yả ẽ ư ồ ầ
B c 2 : t o heap cho ph n đ ng tr c c a A là c r p d f b k aướ ạ ầ ứ ướ ủ
Ph n sau là ch a y đ nguyênầ ứ ể
Ta s có A m i là : r f p d c b k a -- yẽ ớ
Quay l i b c 1 : L y r , a ra và swap r và aạ ướ ấ
A s thành A= a f p d c b k -- r yẽ
T o heap cho A = p f k d c b a -- r yạ
...........
Làm t ng t đ n khi k t thúcươ ự ế ế
Qua VD ta th y r ng ph n quan tr ng nh t là làm sao sinh ra heap t m t m ng cho tr cấ ằ ầ ọ ấ ừ ộ ả ướ
Sau đây là ph n code cho ph n c i ti nầ ầ ả ế
Gi i thu tả ậ
Post Condition : Dùng đ ph c h i l i heap .ể ụ ồ ạ
Pre Condition :
Ta s có A m i là : r f p d c b k a -- yẽ ớ
Quay l i b c 1 : L y r , a ra và swap r và aạ ướ ấ
A s thành A= a f p d c b k -- r yẽ
T o heap cho A = p f k d c b a -- r yạ
Thì khi này current chính là a
low là 0
high là 7
Insertion Sort
VD :
A = { 5 8 6 3 10 }
Insertion sort làm nh sau :ư
Chia m ng A làm 2 ph n sorted và unsortedả ầ
Ban đ u sorted là B = { 5 }ầ
Unsorted là C = { 8 6 3 10 }
L n làm th nh t :ầ ứ ấ
L y ph n t đ u tiên c a C là 8 ra---> C = { 6 3 10 }ấ ầ ử ầ ủ
Tìm v trí c a s 8 trong m ng B ---> B = { 5 8 }ị ủ ố ả
L n làm th hai :ầ ứ
L y ph n t đ u tiên c a C là 6 ra---> C = { 3 10 }ấ ầ ử ầ ủ
Tìm v trí c a s 6 trong m ng B ---> B = { 5 6 8 }ị ủ ố ả
L n làm th ba :ầ ứ
L y ph n t đ u tiên c a C là 3 ra---> C = { 10 }ấ ầ ử ầ ủ
Tìm v trí c a s 3 trong m ng B ---> B = { 3 5 6 8 }ị ủ ố ả
L n làm th t :ầ ứ ư
L y ph n t đ u tiên c a C là 10 ra---> C = { }ấ ầ ử ầ ủ
Tìm v trí c a s 10 trong m ng B ---> B = { 3 5 6 8 10}ị ủ ố ả
K t thúc thu t toánế ậ