N i dungộ
•Gi i thu t th hai có đ ph c t p ả ậ ứ ộ ứ ạ O(n2) là Bubble
sort
–Áp d ng chi n l c ng c v i insertion sortụ ế ượ ượ ớ
•Ta s kh o sátẽ ả :
–Gi i thu t và ví d minh h aả ậ ụ ọ
–Th i gian th c hi nờ ự ệ
•Tr ng h p x u nh t ườ ợ ấ ấ
•T t nh t ố ấ
•Trung bình (gi i thi u v ngh ch th )ớ ệ ề ị ế
–T ng k t và th o lu nổ ế ả ậ
Bubble Sort
•Gi s ta có dãy d li u ch a đ c s p:ả ử ữ ệ ư ượ ắ
–Xu t phát t đ u, duy t trên dãy,tìm ph n t l n ấ ừ ầ ệ ầ ử ớ
nh t, n i b t nó (ấ ổ ọ bubble) v đ nh.ề ỉ
–V i m i b c l p ti p theo, tìm ph n t l n nh t k ớ ỗ ướ ặ ế ầ ử ớ ấ ế
ti p và ếbubble nó v h ng đ nh c a dãyề ướ ỉ ủ .
Bubble Sort
•B t đ u t ph n t đ u tiên, gi s r ng đây là ắ ầ ừ ầ ử ầ ả ử ằ
ph n t l n nh tầ ử ớ ấ .
•So sánh nó v i ph n t th haiớ ầ ử ứ :
–N u ph n t th nh t l n h n, hoán đ i hai ph n tế ầ ử ứ ấ ớ ơ ổ ầ ử
–Ng c l i, ta gi s r ng ph n t th hai là ph n t ượ ạ ả ử ằ ầ ử ứ ầ ử
l n nh tớ ấ
•Ti p t c đi v cu i dãy, ho c là hoán đ i ho c là ế ụ ề ố ặ ổ ặ
đ nh nghĩa l i ph n t l n nh tị ạ ầ ử ớ ấ .
Bubble Sort
•Sau m t l n duy t, ph n t l n nh t ph i v trí ộ ầ ệ ầ ử ớ ấ ả ở ị
cu i cùng c a dãyố ủ .
•B t đ u l i t đ uắ ầ ạ ừ ầ :
–L n duy t th hai s đem ph n t l n th hai v v trí ầ ệ ứ ẽ ầ ử ớ ứ ề ị
cu i cùng th hai c a dãyố ứ ủ
•L p l i ặ ạ n – 1 l n, sau đó, m i ph n t s đúng ầ ọ ầ ử ẽ ở
v trí c a nóị ủ .
Bubble Sort: minh h aọ
•Hãy xem dãy ch a đ c s p ư ượ ắ
bên tay ph i.ả
•Chúng ta b t đ u t ph n t ắ ầ ừ ầ ử
đ u tiên và di chuy n xuôi ầ ể
xu ng:ố
–N u ph n t hi n hành và ế ầ ử ệ
ph n t k có th t , ti p t c ầ ử ế ứ ự ế ụ
v i ph n t ti p theo; n u ớ ầ ử ế ế
ng c l iượ ạ
–Hoán đ i hai ph n tổ ầ ử