Tổng hợp các thuật toán sắp xếp cơ bản
T ng h p các thu t toán s p x p c b nổ ợ ậ ắ ế ơ ả
Ch c h n ng i trên gh gi ng đ ng đ i h c thì ai cũng s đ c làm quenắ ẳ ồ ế ả ườ ạ ọ ẽ ượ
v i thu t toán. Nghe thì th t là tr u t ng và m h , nh ng đ t i u hóa ớ ậ ậ ừ ượ ơ ồ ư ể ố ư
nh ng bài toán đ t ra thì b t bu c các b n ph i h c đ n nó. Mình xin chia ữ ặ ắ ộ ạ ả ọ ế
s 1 chút lí thuy t mà mình h c đ c v các thu t toán s p x p đ n gi n, ẻ ế ọ ượ ề ậ ắ ế ơ ả
mong là có th giúp các b n áp d ng vào bài toán th c t c a mình!ể ạ ụ ự ế ủ
/S p x p n i b t ( bubble sort)ắ ế ổ ọ
Ý t ngưở
Đây có l là lo i s p x p quen thu c nh t v i m i ng i. Ý t ng c a ẽ ạ ắ ế ộ ấ ớ ọ ườ ưở ủ
thu t toán s p x p n i b t nh sau: cho ch s i ch y t 0, 1, …, n-1, n u ậ ắ ế ổ ọ ư ỉ ố ạ ừ ế
hai ph n t k nhau không đúng tr t t , có nghĩa là A[i].key > A[i+1].key ầ ử ề ậ ự
thì ta tráo đ i hai ph n t A[i] và A[i+1]. C ti p t c làm nh v y thì ta s ổ ầ ử ứ ế ụ ư ậ ẽ
đ y d li u có khóa l n nh t lên v trí sau cùng là A[n-1].ẩ ữ ệ ớ ấ ị
Ví dụ
Gi s ta có m ng s nguyên A[0..4] = (7, 2, 8, 4, 6). K t qu th c hi n ả ử ả ố ế ả ự ệ
vi c tráo đ i s đ c th c hi n trong b ng sau:ệ ổ ẽ ượ ự ệ ả
A[0] A[1] A[2] A[3] A[4] Chú thích
7 2 8 4 6 Vì 7 > 2, tráo đ i A[0] v i A[1]ổ ớ
2 7 8 4 6 Vì 8 > 4, tráo đ i A[2] v i A[3]ổ ớ
2 7 4 8 6 Vì 8 > 6, tráo đ i A[3] v i A[4]ổ ớ
2 7 4 6 8
L p l i quá trình trên v i m ng A[0, …, n-2] đ đ y ph n t l n nh t lên ặ ạ ớ ả ể ẩ ầ ử ớ ấ
v trí A[n-2], khi đó ta có A[n-2].key <= A[n-1].key. Ti p t c l p nh v y ị ế ụ ặ ư ậ
v i các đo n đ u A[0..i], v i i = n-3, …., 1, ta s thu đ c m ng đ c s p.ớ ạ ầ ớ ẽ ượ ả ượ ắ
Ta s d th y th i gian ch y c a thu t toán này là O(n2) Tuy nhiên gi ta ẽ ễ ấ ờ ạ ủ ậ ờ
cũng có th c i ti n thu t toán s p x p n i b t b ng cách thêm 1 bi n ể ả ế ậ ắ ế ổ ọ ằ ế
booblean là check, bi n này tr vế ả ề true n u A[0..i] đã đ c s p x p và ế ượ ắ ế
ng c l i. N u check nh n giá tr true thì vòng for đ u tiên s d ng l i. ượ ạ ế ậ ị ầ ẽ ừ ạ
M c đích là l n l p đ u tiên, n u đ n ch s i nào đó mà đo n đ u ụ ở ệ ặ ầ ế ế ỉ ố ạ ầ
A[0..i] đã đ c s p x p thì ta có th d ng không l p n a, gi m thi u đ cượ ắ ế ể ừ ặ ữ ả ể ượ
th i gian ch y.ờ ạ
/S p x p l a ch n (selection sort)ắ ế ự ọ
Ý t ngưở
Ý t ng c a thu t toán này cũng đ n gi n không kém s p x p n i b t: ưở ủ ậ ơ ả ắ ế ổ ọ
Gi s ta ch n đ c thành ph n có khóa nh nh t trên m ng là A[k]. Tráo ả ử ọ ượ ầ ỏ ấ ả
đ i A[0] v i A[k], v y thì lúc này ta s nh n đ c A[0] là ph n t có khóa ổ ớ ậ ẽ ậ ượ ầ ử
nh nh t. Gi s đ n b c th i ta đã có A[0].key <= A[1].key <= … <= ỏ ấ ả ử ế ướ ứ
A[i-1].key. Bây gi ta c n tìm thành ph n có khóa nh nh t trong các ph n ờ ầ ầ ỏ ấ ầ
t t A[i] đ n A[n-1]. Gi s thành ph n đó là A[k] sao cho i <= k <= n-1. ử ừ ế ả ử ầ
Ta l i tráo đ i A[i] v i A[k], ta có A[0].key <= A[1].key <= … <= A[i-1].keyạ ổ ớ
<= A[i].key. L p l i cho t i i = n-1, ta có m ng A đ c s p x pặ ạ ớ ả ượ ắ ế
Ví dụ
Ta lại xét mảng A ở ví dụ trên A[0..4] = [7, 2, 8, 4, 6]. Kết quả được thể hiện trong bảng sau: Chọn phần tử
có khóa nhỏ nhất là A[0]
A[0] A[1] A[2] A[3] A[4] i k
7 2 8 4 6 0 1
2 7 8 4 6 1 3
2 4 8 7 6 2 4
2 4 6 7 8
Th i gian ch y c a thu t toán này cũng t ng t nh thu t toán s p x p ờ ạ ủ ậ ươ ự ư ậ ắ ế
n i b t là O(n2).ổ ọ
/S p x p xen vào (insertion sort)ắ ế
Đây là thu t toán cu i cùng mà mình s gi i thi u bài ngày hôm nay.ậ ố ẽ ớ ệ ở
Ý t ngưở
Cái tên c a thu t toán cũng giúp mình hình dung đ c ph n nào ý t ng ủ ậ ượ ầ ưở
c a thu t toán. Gi s đo n đ u c a m ng A[0..i-1] (v i i >= 1) đã đ c ủ ậ ả ử ạ ầ ủ ả ớ ượ
s p x p, nghĩa là ta đã có A[0].key <= A[1].key <= … <= A[i-1].key. Ta xen ắ ế
A[i] vào v trí thích h p trong đo n đ u A[0..i-1] đ nh n đ c A[0..i] ị ợ ạ ầ ể ậ ượ
đ c s p x p. V i i = 1 thì coi nh đo n đã đ c s p x p. L p l i quá ượ ắ ế ớ ư ạ ượ ắ ế ặ ạ
trình đó v i i = 2, …, n-1 đ có đ c m ng s p x p. Vi c s p x p s đ cớ ể ượ ả ắ ế ệ ắ ế ẽ ượ
ti n hành nh sau: Cho ch s k ch y t i, n u A[k].key < A[k-1].key thì ta ế ư ỉ ố ạ ừ ế
tráo đ i v trí c a A[k] và A[k-1] r i gi m k đi 1.ổ ị ủ ồ ả
Ví dụ
Ta có 1 mảng số nguyên A[0..5] = (1, 3, 7, 2, 8, 4) và đoạn đầu A[0..2] = (1, 3, 7) đã được sắp xếp Đầu Dên
ta sẽ chọn i = 3 ( vì giá trị từ 0 đến 2 đã được sắp xếp) và k = i = 3. Nhận thấy A[3] < A[2] nên ta tráo đổi
A[3] và A[2], ta có:
A[0] A[1] A[2] A[3] A[4] A[5]
132784
Đến đây thì ta có k = 2, A[2] < A[1] nên ta lại tráo A[2] cho A[1]:
A[0] A[1] A[2] A[3] A[4] A[5]
123784
Lúc này k = 1 và A[1] >= A[0] nên ta d ng l i và ta đã có đo n đ u A[0..3] ừ ạ ạ ầ
đ c s p x p L p l i các b c trên v i i = 4, 5 ta s đ c m ng s p x p ượ ắ ế ặ ạ ướ ớ ẽ ượ ả ắ ế
tăng d n.ầ
Thu t toán s p x p này cũng có th i gian ch y là O(n2) Bài này mình xin ậ ắ ế ờ ạ
phép d ng t i đây. Bài sau mình s gi i thi u thêm 1 s thu t toán s p x p ừ ạ ẽ ớ ệ ố ậ ắ ế
ít đ c s d ng h n nh ng l i có th i gian ch y nhanh h n h n 3 thu t ượ ử ụ ơ ư ạ ờ ạ ơ ẳ ậ
toán trên.
/S p x p nhanh (Quick Sort)ắ ế
1. Gi i thi uớ ệ
S p x p nhanh (Quick Sort) còn có m t tên g i khác là s p x p phân chia ắ ế ộ ọ ắ ế
(Part Sort) d a trên ý t ng thu t toán. Nó đ c phát minh l n đ u b i ự ưở ậ ượ ầ ầ ở
C.A.Hoare vào năm 1960. Có l đây là thu t toán đ c nghiên c u và s ẽ ậ ượ ứ ử
d ng r ng rãi nh t trong các thu t toán s p x p. Quick sort cũng là thu t ụ ộ ấ ậ ắ ế ậ
toán đ quy. Ng c v i Mergesort g i đ quy r i m i x lý, Quick sort x ệ ượ ớ ọ ệ ồ ớ ử ử
lý xong m i g i đ quy.ớọệ
Ý t ng c a thu t toán này d a trên ph ng pháp chia đ tr , nghĩa là chia ưở ủ ậ ự ươ ể ị
dãy c n s p x p thành 2 ph n, sau đó th c hi n vi c s p x p cho m i ầ ắ ế ầ ự ệ ệ ắ ế ỗ
ph n đ c l p nhau. Đ làm vi c này thì ta c n ph i làm các b c sau:ầ ộ ậ ể ệ ầ ả ướ
1. Ch n ng u nhiên m t ph n t nào đó c a dãy làm ph n t khóa (pivot) ọ ẫ ộ ầ ử ủ ầ ử
Kĩ thu t ch n ph n t khóa r t quan tr ng vì n u không may b n có th b ậ ọ ầ ử ấ ọ ế ạ ể ị
r i vào vòng l p vô h n đ i v i các tr ng h p đ c bi t. T t nh t là ch n ơ ặ ạ ố ớ ườ ợ ặ ệ ố ấ ọ
ph n t v trí trung tâm c a dãy. Khi đó sauầ ử ở ị ủ l n phân chia ta s ầ ẽ
đ t t i kích th c danh sách b ng 1. Tuy nhiên đi u đó r t khó. Có các ạ ớ ướ ằ ề ấ
cách ch n ph n t khóa nh sau:ọ ầ ử ư
Ch n ph n t đ ng đ u ho c đ ng cu i làm ph n t khóa.ọ ầ ử ứ ầ ặ ứ ố ầ ử
Ch n ph n t đ ng gi a danh sách làm ph n t khóa.ọ ầ ử ứ ữ ầ ử
Ch n ph n t trung gian trong 3 ph n t đ ng đ u, đ ng gi a và ọ ầ ử ầ ử ứ ầ ứ ữ
đ ng cu i làm ph n t khóa.ứ ố ầ ử
Ch n ph n t ng u nhiên làm ph n t khóa. (Cách này có th d n ọ ầ ử ẫ ầ ử ể ẫ
đ n kh năng r i vào các tr ng h p đ c bi t)ế ả ơ ườ ợ ặ ệ
2. X p các ph n t nh h n ph n t ch t phía tr c ph n t khóaế ầ ử ỏ ơ ầ ử ố ở ướ ầ ử
3. X p các ph n t l n h n ph n t ch t phía sau ph n t khóa Đ có ế ầ ử ớ ơ ầ ử ố ở ầ ử ể
đ c s phân lo i này thì 2 b c trên, các ph n t s đ c so sánh v i ượ ự ạ ở ướ ầ ử ẽ ượ ớ
khóa và hoán đ i v trí cho nhau ho c cho khóa n u nó l n h n khóa mà l i ổ ị ặ ế ớ ơ ạ
n m tr c khóa, ho c nh h n mà l i n m sau khóa. Áp d ng kĩ thu t nhằ ướ ặ ỏ ơ ạ ằ ụ ậ ư
trên cho m i đo n đó và ti p t c làm v y cho đ n khi m i đo n ch còn 2 ỗ ạ ế ụ ậ ế ỗ ạ ỉ
ph n t . Khi đó toàn b dãy đã đ c s p x pầ ử ộ ượ ắ ế
Quick sort là m t thu t toán d cài đ t, hi u qu trong h u h t các tr ng ộ ậ ễ ặ ệ ả ầ ế ườ
h p và tiêu t n ít tài nguyên h n so v i các thu t toán khác. Đ ph c t p ợ ố ơ ớ ậ ộ ứ ạ
trung bình c a gi i thu t làủ ả ậ O(NlogN).
2. Các b c th c hi n gi i thu tướ ự ệ ả ậ
Giả sử ta có một dãy các phần tử như sau:
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
28 16 56 30 17 32 24 18
leR = 0; right = 7; Ở ví dụ này ta lấy một phần tử làm khóa, ở đây mình chọn phần tử khóa là A[(0+7)/2] =
A[3] = 30 Cho i chạy từ trái sang phải, bắt đầu từ vị trí 0 Cho j chạy từ phải sang trái, bắt đầu từ vị trí 7
Quá trình duyệt từ bên trái với biến duyệt i sẽ dừng lại ở 56 (i=2), vì đây không phải là phần tử nhỏ hơn
khóa. Quá trình duyệt từ bên phải với biến duyệt j sẽ dừng lại ở 18 (j=7) vì đây là phần tử nhỏ hơn khóa.
Tiến hành đổi chỗ 2 phần tử cho nhau.
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
28 16 18 30 17 32 24 56
Quá trình duyệt Dếp tục. Khóa ở đây vẫn là 30. Ta Dếp tục tăng biến duyệt i và giảm biến duyệt j, nhận
thấy biến duyệt i chạy đến 30 (i=3), còn biến duyệt j dừng lại ở 24 (j=6). Tiến hành đổi chỗ 2 phần tử cho
nhau.
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
28 16 18 24 17 32 30 56
Quá trình duyệt Dếp tục. Khóa ở đây vẫn là 30. Tiếp tục tăng biến duyệt i và giảm biến duyệt j, nhận thấy
biến duyệt i chạy đến 32 (i=5), còn biến duyệt j dừng lại ở 30(j=6). Tiến hành đổi chỗ 2 phần tử cho nhau.
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
28 16 18 24 17 30 32 56
Quá trình duyệt Dếp tục. Khóa ở đây vẫn là 30. Tiếp tục tăng biến duyệt i và giảm biến duyệt j, nhận thấy
biến duyệt i và j cùng chạy đến 30. Lúc này ta sẽ chia mảng trên ra làm 2 mảng con A[0..4] và A[5..7], vì ta
thấy A[5..7] đã được sắp xếp tăng dần rồi nên ta sẽ xét A[0..4] A[0..4] = [28, 16, 18, 24, 17] Lặp lại những
bước trên với phần tử được chọn là khóa là A[(0+4)/2] = A[2] = 18 leR = 0; right = 4; Cho i chạy từ trái
sang phải bắt đầu từ vị trí 0 Cho j chạy từ phải sang trái bắt đầu từ vị trí 4 Quá trình duyệt từ bên trái với
biến duyệt i sẽ dừng lại ở 28(i=0) vì đây không phải là phần tử nhỏ hơn khóa. Quá trình duyệt từ bên
phải với biến duyệt j sẽ dừng lại ở 17 (j=4) vì đây là phần tử không lớn hơn khóa. Tiến hành đổi chỗ 2
phần tử cho nhau.
A[0] A[1] A[2] A[3] A[4]
17 16 18 24 28
Quá trình duyệt Dếp tục. Tăng biến duyệt i và giảm biến duyệt j. Lúc này i = j nên ta sẽ chia mảng trên ra
làm 2 mảng con A[0..1] và A[2..4]. Ta thấy A[2..4] đã được sắp xếp tăng dần rồi, nên ta chỉ xét A[0..1], vì
A[0] > A[1] nên ta đổi chỗ 2 phần tử cho nhau và được mảng sắp xếp tăng dần cuối cùng:
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
16 17 18 24 28 30 32 56
3. Cài đ t gi i thu tặ ả ậ
Nh đã nói trên, Quick sort cũng là m t thu t toán đ quy, bao g m vi c ư ở ộ ậ ệ ồ ệ
chia m ng thành 2 m ng con th a mãn yêu c u trên, sau đó th c hi n l i ả ả ỏ ầ ự ệ ờ
g i đ quy v i 2 m ng con v a t o đ c.ọ ệ ớ ả ừ ạ ượ
4. Phân tích
Nh c đi m c a Quick Sort là không hi u qu trên nh ng dãy đã đ c s pượ ể ủ ệ ả ữ ượ ắ
x p s n. Khi đó ta ph i m t N l n g i đ quy và m i l n ch lo i đ c 1 ế ẵ ả ấ ầ ọ ệ ỗ ầ ỉ ạ ượ
có thể bạn quan tâm
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)
Tổng hợp một số thuật toán mã hóa phổ biến
7
830
259
An ninh, bảo mật
7
(New)
TỔNG QUAN MỘT SỐ KĨ THUẬT ĐIỀU CHẾ SỐ, TỔNG QUAN MỘT SỐ KĨ THUẬT ĐIỀU...
66
853
440
Kỹ thuật
66
(New)
Tổng hợp thủ thuật bảo vệ máy tính của bạn an toàn khỏi các cuộc tấn c...
8
911
198
An ninh, bảo mật
8
(New)
Luận văn thạc sỹ kỹ thuật điện: Tổng quan về kỹ thuật WiMAX và giải ph...
93
774
364
Thạc sĩ cao học
93
(New)
Tìm hiểu về thuật toán và thuật giải
97
2.152
442
Cơ sở dữ liệu
97
(New)
Tổng hợp các thủ thuật Facebook hữu ích
14
704
190
Tài liệu CNTT khác
14
(New)
Tổng hợp thủ thuật máy tính
3
598
255
Tài liệu CNTT khác
3
(New)
thông tin tài liệu
Bài viết chia sẻ lí thuyết về các thuật toán sắp xếp đơn giản, mong là có thể giúp các bạn áp dụng vào bài toán thực tế của mình!
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!
×
