Home
Công nghệ thông tin
Lập trình
QuickSort, TimSort hay Insertion Sort? Đâu là thuật toán sắp xếp nhanh nhất
QuickSort, TimSort hay Insertion Sort? Đâu là thuật toán sắp xếp nhanh nhất
QuickSort, TimSort hay Insertion Sort? Đâu là thu t toán s p x pậ ắ ế
nhanh nh tấ
L i nói đ uờ ầ
Thu còn ng i trên gh tr ng h c đ i h c, khi h c môn “C u trúc D ở ồ ế ườ ọ ạ ọ ọ ấ ữ
li u & Gi i thu t” hay là lúc đi ph ng v n 1 công ty ABC, XYZ nào đó, ệ ả ậ ỏ ấ ở
mà cũng có th đ n t n lúc ng i trà đá bàn lu n v i anh em đ ng nghi p ể ế ậ ồ ậ ớ ồ ệ
chuy n ngh , chuy n nghi p … thì ch c h n đã t ng có l n anh em Dev ệ ề ệ ệ ắ ẳ ừ ầ
chúng ta đ c h i ho c là nghe th y câu h i: “Thu t toán s p x p nào là ượ ỏ ặ ấ ỏ ậ ắ ế
nhanh nh t?” Và bài vi t này c a mình s ph n nào giúp các b n tìm ra ấ ế ủ ẽ ầ ạ
đáp án cho câu h i trên.ỏ
Câu tr l i là QuickSort, TimSort hay Insertion Sort nh ?ả ờ ỉ
Xem nào, nghe câu ch thì đã th y th ng Quick Sort có v là nhanh r i ữ ấ ằ ẻ ồ
(Quick là nhanh mà), và th c t , thì Quick Sort cũng là đáp án đ c nhi u ự ế ượ ề
ng i l a ch n nh t khi đ c h i câu h i trên. Nh ng th c t , thì l i ườ ự ọ ấ ượ ỏ ỏ ư ự ế ạ
không ph i v y, ph n l n m i ng i đã sai khi l a ch n Quick Sort là câu ả ậ ầ ớ ọ ườ ự ọ
tr l i c a mình. V y đáp án là Tim Sort ? hay Insertion Sort nh Cùng ả ờ ủ ậ ư ỉ
nhìn vào b ng th ng kê đ ph c t p trung bình c a các thu t toán s p x pả ố ộ ứ ạ ủ ậ ắ ế
Nhìn vào
b ng trên thì rõ ràng Quick Sort có đ ph c t p trung bình là O(n log(n)), ả ộ ứ ạ ơ
ch ng ph i d a vào k t qu này thì Quick Sort là nhanh nh t còn gì n a? ẳ ả ự ế ả ấ ữ
Ch m l i 1 chút, chúng ta hãy th đ t câu h i ng c l i đây xem sao ậ ạ ử ặ ỏ ượ ạ ở
nhé: “N u QuickSort là nhanh nh t thì t i sao l i còn ph i đ ra ti t các ế ấ ạ ạ ả ẻ ỉ
lo i thu t toán s p x p khác làm cái l gì nh ?”ạ ậ ắ ế ề ỉ
Ti p theo, chúng ta s xem t c đ s p x p c a các thu t toán d a theo d ế ẽ ố ộ ắ ế ủ ậ ự ữ
li u đ u vào, d li u đây có các case t d li u Random đ n Nearly ệ ầ ữ ệ ở ừ ữ ệ ế
Sorted hay c vi c Reversed D li uả ệ ữ ệ
Nhìn vào th ng kê phía trên, có th th y v i m i ki u d li u khác nhau thìố ể ấ ớ ỗ ể ữ ệ
l i có 1 ki u s p x p chi m u th riêng, ví d v i d li u Nearly Sorted ạ ể ắ ế ế ư ế ụ ớ ữ ệ
thì Insertion Sort là nhanh nh t nh ng khi v i nh ng ki u d li u ph c t p ấ ư ớ ữ ể ữ ệ ứ ạ
h n thì Insertion Sort l i không ph i là nhanh nh t. Nh v y, t nh ng ơ ạ ả ấ ư ậ ừ ữ
th ng kê trên chúng ta đã d n d n hình dung ra đáp án cho câu h i “Thu t ố ầ ầ ỏ ậ
toán s p x p nào là nhanh nh t” r i nhắ ế ấ ồ ỉ
V y câu tr l i đúng là gì?ậ ả ờ
=> “Không có 1 b t kỳ thu t toán s p x p nào c th c , nó còn ph thu cấ ậ ắ ế ụ ể ả ụ ộ
vào nhi u y u t ” Và “ph thu c vào nhi u y u t ” cũng là lý do mà có ề ế ố ụ ộ ề ế ố
r t nhi u lo i thu t toán s p x p khác nhau ra đ i. Chúng ta nhìn vào 1 vài ấ ề ạ ậ ắ ế ờ
ví d c th d i đây đ th y nh ng y u t nào s nh h ng vi c l a ụ ụ ể ướ ể ấ ữ ế ố ẽ ả ưở ệ ự
ch n thu t toánọ ậ
Quick Sort s là t t nh t n u …ẽ ố ấ ế
1. Không lo l ng v các case đ u vào k c tr ng h p x u nh t (tr t ắ ề ầ ể ả ườ ợ ấ ấ ậ
t nói chung là ng u nhiên)ự ẫ
2. Không quan tâm đ n dung l ng b nh , b nh là hoàn toàn lý ế ượ ộ ớ ộ ớ
t ng và phù h p đâyưở ợ ở
N u d li u đã đ c s p x p s n, thì nên ch n Insertion Sort ho c ế ữ ệ ượ ắ ế ẵ ọ ặ
Shell Sort s t t h n.ẽ ố ơ
N u chúng ta th c s ph i lo i b case x u nh t, có th s d ng ế ự ự ả ạ ỏ ấ ấ ể ử ụ
Heap (ho c ít nh t là Quick3) v i đ ph c t p NlogNặ ấ ớ ộ ứ ạ
Tim Sort s có đ ph c t p th p h n Quick Sort c Best Case l n ẽ ộ ứ ạ ấ ơ ở ả ẫ
Worse Case, Tim Sort là s k t h p c a Merge Sort và Insertion Sort. ự ế ợ ủ
Python s d ng thu t toán s p x p này là m c đ nh c a hử ụ ậ ắ ế ặ ị ủ ọ
Trong tr ng h p, d li u r t ít ph n t (10-20 ph n t ), l a ch n ườ ợ ữ ệ ấ ầ ử ầ ử ự ọ
Selection Sort s nhanh h n Quick SortTóm l i 1 l n n a , v lý ẽ ơ ạ ầ ữ ề
thuy t thì Quick Sort th t s là thu t toán s p x p nhanh nh t trong ế ậ ự ậ ắ ế ấ
ph n l n các tr ng h p. Tuy nhiên, trên th c t , vi c l a ch n thu tầ ớ ườ ợ ự ế ệ ự ọ ậ
toán s p x p d a vào nhi u y u t nh d li u đ u vào s l ng ắ ế ự ề ế ố ư ữ ệ ầ ố ượ
nh th nào, có s p x p s n hay không, dung l ng b nh ra sao, ư ế ắ ế ẵ ượ ộ ớ
t c đ x lý CPU…ố ộ ử
Thu t toán và bài h c cu c s ngậ ọ ộ ố
Mình v n th ng hay nói đùa r ng: “Code không bao gi l a d i chúng ta ẫ ườ ằ ờ ừ ố
c ”. Và th c s thì khi Code mình cũng chiêm nghi m ra nhi u bài h c ả ự ự ệ ề ọ
cu c s ng cho chính mình luôn. đây, t m t câu h i thu t toán s p x p ộ ố Ở ừ ộ ỏ ậ ắ ế
vô cùng đ n gi n nh ng chúng ta có th rút ra đ c r t nhi u bài h c th c ơ ả ư ể ượ ấ ề ọ ự
t :ế
Hãy h c cách đ t l i câu h i cho v n đ đang đ c h i, đ t đó ọ ặ ạ ỏ ấ ể ượ ỏ ể ừ
phân tích tìm ra câu tr l i chính xác nh t. Đôi khi làm d án th c t , ả ờ ấ ự ự ế
khách hàng s đ a ra nh ng yêu c u m h , thay vì c p đ u vào tìm ẽ ư ữ ầ ơ ồ ắ ầ
gi i pháp, hay code thì chúng ta hãy h i rõ khách hàng, làm rõ v n đ ả ỏ ấ ề
đó tr c đãướ
Trong cu c s ng, không có gì là hoàn h o c hãy nhìn đ t v n đ ộ ố ả ả ặ ấ ề
g p ph i d i nhi u góc nhìn khác nhau, đ cân nh c và l a ch n ặ ả ướ ề ể ắ ự ọ
gi i pháp cho h p lýả ợ
có thể bạn quan tâm
Mách bạn mẹo hay nhổ lông vịt nhanh và sạch nhất
4
992
255
Mẹo vặt trong nấu ăn
4
(New)
Tải ảnh từ Instagram về một cách nhanh chóng nhất
14
946
248
Tài liệu CNTT khác
14
(New)
Hướng dẫn doanh nghiệp tra cứu hóa đơn nhanh nhất
6
677
216
Kế toán, kiểm toán
6
(New)
Làm thế nào để Google Index website của bạn nhanh nhất có thể
5
613
257
Tài liệu CNTT khác
5
(New)
.png)
Mẹo chữa khản giọng mất tiếng, nhanh nhất tại nhà
4
910
266
Bệnh thường gặp
4
(New)
Format USB, Ổ cứng HDD và SSD trên MacOs như thế nào nhanh, đơn giản n...
7
979
247
Tài liệu CNTT khác
7
(New)
Trình bày chi tiết về bài toán lựa chọn đơn vị trong tổng hợp ghép nối...
69
809
360
Kỹ thuật
69
(New)
Luận văn: Công nghệ phần mềm tuyển sinh- Xử lý nhanh một số yêu cầu nh...
34
763
314
Kỹ thuật
34
(New)
thông tin tài liệu
Thuật toán sắp xếp nào là nhanh nhất?” Và bài viết này của mình sẽ phần nào giúp các bạn tìm ra đáp án cho câu hỏi trên.
Mở rộng để xem thêm
từ khóa liên quan
tài liệu mới trong mục này
tài liệu hot trong mục này
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
xem nhiều trong tuần
Tâm lý xã hội VÀ Hệ tư tưởng
Tham khảo 12 bài tập nguyên lý thống kê có lời giải
4 đề thi học sinh giỏi Toán lớp 2, có đáp án kèm theo
Trắc nghiệm kinh tế
Địa lý 12 Phát triển cây công nghiệp lâu năm Tây Nguyên
Mẫu slide về các môn thể thao
yêu cầu tài liệu
Giúp bạn tìm tài liệu chưa có
×
