Chương 4: Các thuật toán sắp xếp (new) Cô Võ Thị Hường
Gửi bởi: Võ Thị Hường 10 tháng 9 2020 lúc 9:56:53 | Được cập nhật: 20 giờ trước (6:57:54) Kiểu file: PDF | Lượt xem: 332 | Lượt Download: 0 | File size: 1.233226 Mb
Nội dung tài liệu
Tải xuống
Link tài liệu:
Các tài liệu liên quan
Có thể bạn quan tâm
Thông tin tài liệu
Môn học
Cấu trúc dữ liệu và
giải thuật
GV: Võ Thị Hường
LOGO
THUẬT TOÁN SẮP XẾP
Khái niệm sắp xếp
Các thuật sắp xếp đơn giản
Các thuật toán sắp xếp nhanh
KHÁI NIỆM SẮP XẾP
Đặt vấn đề
Cho dãy số
21 44 52 73 81
81 52 73 21 44
81 73 52 44 21
Cho danh sách tên học sinh
Hùng
An
Thắng
Bình
An
Hoàng
Bình
Hùng
Hoàng
Thắng
KHÁI NIỆM SẮP XẾP
Khái niệm
Sắp xếp là việc biến đổi vị trí của một tập đối
tượng theo một trật tự nhất định
Mục đích
Giúp việc tìm kiếm, chọn lọc thông tin được dễ
dàng, nhanh chóng
BÀI TOÁN SẮP XẾP
BÀI
TOÁN
Đầu vào: Dãy n đối tượng, mỗi đối
tượng có một khóa sắp xếp
Đầu ra: Dãy n đối tượng được sắp
xếp theo trật tự của khóa.
Giả thiết các khóa là số nguyên được lưu trong
mảng một chiều, thứ tự sắp xếp là không giảm
CÁC THUẬT TOÁN SẮP XẾP ĐƠN GiẢN
Thuật toán sắp xếp lựa chọn (Selection Sort)
Thuật toán sắp xếp chèn (Insertion Sort)
Thuật toán sắp xếp nổi bọt (Bubble Sort)
Thuật toán sắp xếp đổi chỗ (Interchange sort)
www.themegallery.com
Company Logo
THUẬT TOÁN SẮP XẾP LỰA CHỌN
Ý tưởng thuật toán
Dựa vào thuật toán tìm MAX, MIN
Ở lần duyệt thứ i, với 1<=i K[Pos];
Company Logo
THUẬT TOÁN SẮP XẾP LỰA CHỌN
A[1]
A[2]
A[3]
A[4]
A[5]
Ban đầu
3
-1
5
7
-4
Bước 1
-4
-1
5
7
3
-1
5
7
3
3
7
5
5
7
5
7
Khóa
Bước
Bước 2
Bước 3
Bước 4
Kết quả
-4
-1
3
Cho bộ dữ liệu K = {9, 3, 10, 0, 99, 35, 25,
88, 18}
Áp dụng giải thuật insertion sort với bộ
dữ liệu K, chỉ rõ kết quả từng bước
thực hiện của giải thuật.
www.themegallery.com
Company Logo
Sắp xếp dãy gồm 10 mẩu tin có khóa là các số nguyên:
5, 6, 2, 2, 10, 12, 9, 10, 9 và 3
www.themegallery.com
Company Logo
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10]
Ban đầu 5
6
2
2
10
12
9
10
9
3
Bước 1
6
5
2
10
12
9
10
9
3
2
5
6
10
12
9
10
9
3
3
6
10
12
9
10
9
5
5
10
12
9
10
9
6
6
12
9
10
9
10
9
12
10
9
10
9
10
12
10
10
12
10
10
12
10
12
2
Bước 2
Bước 3
Bước 4
Bước 5
Bước 6
Bước 7
Bước 8
Bước 9
Kết quả 2
2
3
5
6
9
9
10
www.themegallery.com
Company Logo
THUẬT TOÁN SẮP XẾP CHÈN
Ý tưởng thuật toán
www.themegallery.com
Company Logo
THUẬT TOÁN SẮP XẾP CHÈN
Ý tưởng thuật toán :
Giả sử phần đầu của dãy là Bi-1 = {X1, ... , Xi-1} đã
được sắp xếp tăng dần
• Coi {X1} đã được sắp xếp không giảm
Kiểm tra phần tử Xi: Tìm vị trí thích hợp của Xi trong
Bi-1 và chèn Xi vào vị trí để được dãy Bi = {X1 ,..., Xi-1,
Xi} không giảm
Lặp lại với Xi+1 , ... cho đến khi i=n
THUẬT TOÁN SẮP XẾP CHÈN
Ý tưởng thuật toán :
Ở lần duyệt thứ i, với 1<=i 0)
Xj+1 = Xj;
j = j – 1;
Xj+1 = tg;
THUẬT TOÁN SẮP XẾP CHÈN
A[1]
A[2]
A[3]
A[4]
A[5]
Ban đầu
3
-1
7
-4
5
Bước 1
-1
3
Bước 2
-1
3
7
Bước 3
-4
-1
3
7
Bước 4
-4
-1
3
5
7
Kết quả
-4
-1
3
5
7
Khóa
Bước
Sắp xếp dãy gồm 10 mẩu tin đã cho
ở trên có khóa là các số nguyên:
5, 6, 2, 2, 10, 12, 9, 10, 9 và 3.
www.themegallery.com
Company Logo
Cho bộ dữ liệu K = {9, 3, 10, 0, 99, 35, 25, 88, 18}
Áp dụng giải thuật insertion sort với bộ dữ liệu K, chỉ rõ
kết quả từng bước thực hiện của giải thuật.
www.themegallery.com
Company Logo
THUẬT TOÁN SẮP XẾP NỔI BỌT
Ý tưởng thuật toán :
Ở lần duyệt thứ i, với 1<=ii
Bước 3 :
Trong khi j ≤ N thực hiện
Nếu a[j]a[j]; //xét cặp a[i], a[j]
j = j+1;
Bước 4 : i = i+1;
Nếu i< n: Lặp lại Bước 2.
Ngược lại: Dừng.
www.themegallery.com
Company Logo
THUẬT TOÁN SẮP XẾP ĐỔI CHỖ
Cài đặt thuật toán:
ProcedureInterchangeSort;
Var i, j: integer;
Begin
for i: = 1to n do
for j: =i+1 to n do
if (a[j]< a[i]) { nếu có sự
sai vị trí thì đổi chỗ}
Hoanvi(a[i],a[j]);
End;
www.themegallery.com
Company Logo
THUẬT TOÁN SẮP XẾP ĐỔI CHỖ
Ví dụ minh họa
Sắp xếp dãy gồm 10 mẩu tin có khóa là các
số nguyên: 5, 6, 2, 2, 10, 12, 9, 10, 9 và 3
www.themegallery.com
Company Logo
www.themegallery.com
Company Logo
Cho bộ dữ liệu K = {9, 3, 10, 0, 99, 35, 25,
88, 18}
Áp dụng giải thuật Quick sort với bộ
dữ liệu K, chỉ rõ kết quả từng bước
thực hiện của giải thuật.
www.themegallery.com
Company Logo
Cho bộ dữ liệu K = {32, 43, 18, 80, 60,
59, 93, 70, 55}
Áp dụng giải thuật quick sort với bộ
dữ liệu K, chỉ rõ kết quả từng bước
thực hiện của giải thuật.
www.themegallery.com
Company Logo