Thuật toán sắp xếp
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (465.19 KB, 23 trang )
Bài thuyết trình: Thuật toán sắp xếp
Bài thuyết trình: Thuật toán sắp xếp
Học sinh trường THPT Nguyễn Thượng Hiền:
Trần Đỗ Đăng Khoa
Trong khoa học máy tính và trong toán học, một thuật toán sắp xếp
là một thuật toán sắp xếp các phần tử của một danh sách [hoặc một
mảng theo thứ tự (tăng hoặc giảm)]. Người ta thường xét trường
hợp các phần tử cần sắp xếp là các số.
Phân loại thuật toán sắp xếp
Phân loại thuật toán sắp xếp
1. Sắp xếp ổn định
Một thuật toán sắp xếp được gọi là sắp xếp ổn định nếu sau khi tiến
hành sắp xếp vị trí tương đối giữa các phần tử bằng nhau không bị thay
đổi.
2. Sắp xếp so sánh
Một thuật toán sắp xếp được gọi là sắp xếp so sánh nếu trong quá
trình thực hiện thuật toán ta tiến hành so sánh các khoá và đổi chỗ
các phần tử cho nhau. Đa số các thuật toán sắp xếp dưới đây là sắp
xếp so sánh, riêng sắp xếp đếm phân phối không phải là sắp xếp so
sánh.
Một số thuật toán sắp xếp
Một số thuật toán sắp xếp
Sắp xếp nổi bọt
Sắp xếp nổi bọt
bubble sort !"
#$%$& '"()*+,-, .&+/0)12$&,
3,,34#5 5,34&6 7 8 $&)
9: ';+";5 <,3=>$ $ ?+/0)&22
@&"!;5&,3, $%%A B , 7/&)Sắp xếp chèn
Sắp xếp chèn
Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp rất hiệu quả với
các danh sách nhỏ. Nó lần lượt lấy các phần tử của danh sách chèn
vào vị trí thích hợp trong một danh sách mới đã được sắp.
Sắp xếp chọn
Sắp xếp chọn (select sort) là phương pháp sắp xếp bằng cách chọn
phần tử bé nhất xếp vào vị trí thứ nhất, tương tự với các phần tử
nhỏ thứ hai, thứ ba,
Sắp xếp trộn
Sắp xếp trộn (merge sort) cùng với sắp xếp nhanh là hai thuật toán sắp
xếp dựa vào tư tưởng "chia để trị" (divide and conquer). Thủ tục cơ
bản là việc trộn hai danh sách đã được sắp xếp vào một danh sách
mới theo thứ tự. Nó có thể bắt đầu trộn bằng cách so sánh hai phần
tử một (chẳng hạn phần tử thứ nhất với phần tử thứ hai, sau đó thứ
ba với thứ tư ) và sau khi kết thúc bước 1 nó chuyển sang bước 2.
Ở bước 2 nó trộn các danh sách hai phần tử thành các danh sách
bốn phần tử. Cứ như vậy cho đến khi hai danh sách cuối cùng được
trộn thành một.
Sắp xếp nhanh
Sắp xếp nhanh (quicksort) là một thuật toán theo tư tưởng chia để
trị, nó dựa trên thủ tục phân chia như sau: để chia một dãy ta
chọn một phần tử được gọi là "chốt" (pivot), chuyển tất cả các
phần tử nhỏ hơn chốt về trước chốt, chuyển tất cả các phần tử
lớn hơn chốt về sau nó. Thủ tục này có thể thực hiện trong thời
gian tuyến tính. Tiếp tục phân chia các dãy con đó như trên cho
đến khi các dãy con chỉ còn một phần tử.
Điểm khác biệt giữa sắp xếp nhanh và sắp xếp trộn là trong sắp
xếp trộn việc xác định thứ tự được xác định khi "trộn", tức là
trong khâu tổng hợp lời giải sau khi các bài toán con đã được
giải, còn sắp xếp nhanh đã quan tâm đến thứ tự các phần tử khi
phân chia một danh sách thành hai danh sách con.
Sắp xếp vun đống
Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp
chọn. Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc
nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với
phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong
thời gian O(n
2
). Nhưng heapsort đã giảm độ phức tạp này bằng cách
sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap).
Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc
bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã
được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ
giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun
đống chạy trong thời gian O(n log n).
Sắp xếp theo cơ số
Sắp xếp theo cơ số (radix sort) dựa trên tính chất "số" của các khóa.
Trong giải thuật sắp xếp theo cơ số, ta không chỉ so sánh giá trị của
các khóa, mà so sánh các thành phần của khóa. Giả sử các khóa là
các số biểu diễn theo hệ ghi số cơ số M. Khi đó sắp xếp theo cơ số
sẽ so sánh từng k
Chúng ta mô tả cách sắp này khi cơ số M=10. Giả sử phải sắp các hồ
sơ đánh số bởi 3 chữ số thập phân. Đầu tiên ta chia các hồ sơ vào
các đống có cùng chữ số hàng trăm (đồng thới xếp các đống theo
thứ tự của chữ số hàng trăm), trong mỗi đống con lại phân chia theo
chữ số hàng chục, cuối cùng trong mỗi đống có cùng chữ số hàng
trăm và hàng chục, sắp xếp theo thứ tự của chữ số hàng đơn vị.
Trong máy tính, đương nhiên việc sắp xếp theo cơ số nhị phân (cơ số
2) hoặc cơ số là lũy thừa của 2 là thuận lợi nhất. Trong trường hợp
cơ số 2, việc phân hoạch tương tự như phân hoạch trong Quick Sort,
chỉ khác ở chỗ cách chọn phần tử chốt.
Sắp xếp đếm phân phối
Sắp xếp đếm phân phối là phương pháp sắp xếp có độ phức tạp tuyến tính
trong trường hợp các khóa nhận hữu hạn giá trị trong khoảng cho trước. Để
đơn giản ta giả sử các phần tử của danh sách a[1 n] nhận các giá trị tự
nhiên trong khoảng [1 M].
Sắp xếp đếm phân phối đầu tiên đếm các phần tử thuộc danh sách nhận giá trị
k với . Các giá trị đếm được được ghi vào mảng Counter[1 M]. Sau đó khi
duyệt theo k từ 1 đến M, ta lần lượt xếp Counter[k] phần tử của vào danh
sách a[1 n].
Ta có thể cải tiến thuật toán, để có thể sắp xếp được cả số âm, bằng cách xác
định giá trị MIN của mảng cần sắp xếp, rồi tiến hành trừ tất cả các phần tử
cho MIN trước khi "xử lý đếm vào mảng Counter[]". Khi ta chép ngược từ
mảng Counter[] -> mảng cần sắp xếp, ta sẽ cộng thêm MIN vào khóa k (k=1
-> k=M).
H
A
N
K
y
O
U
F
O
R
Y
O
U
R
L
I
S
T
E
N
I
N
G
