intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 5 - Trịnh Anh Phúc

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:99

Thêm vào BST
Báo xấu
29
lượt xem 5
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và thuật toán - Chương 5: Các thuật toán xắp xếp" cung cấp cho người học các kiến thức: Bài toán sắp xếp, ba thuật toán sắp xếp cơ bản, sắp xếp trộn, sắp xếp nhanh, sắp xếp vun đống,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 5 - Trịnh Anh Phúc

  1. Chương 5 : Các thuật toán sắp xếp Trịnh Anh Phúc 1 1 Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường Đại Học Bách Khoa Hà Nội. Ngày 5 tháng 3 năm 2014 CuuDuongThanCong.com Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 1 / 92
  2. Giới thiệu 1 Bài toán sắp xếp 2 Ba thuật toán sắp xếp cơ bản 3 Sắp xếp trộn 4 Sắp xếp nhanh 5 Sắp xếp vun đống 6 Cận dưới cho bài toán sắp xếp 7 Tổng kết 8 Các phương pháp sắp xếpCuuDuongThanCong.com đặc biệt Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 2 / 92
  3. Bài toán sắp xếp Định nghĩa bài toán sắp xếp Sắp xếp (Sorting) là quá trình tổ chức lại họ các dữ liệu theo thứ tự giảm dần hoặc tăng dần (ascending or descending order). Dữ liệu cần sắp xếp có thể là : Số nguyên (Intergers) Xâu ký tự (String) Đối tượng (Object) Ta cần có khóa sắp xếp (sort key) dùng để phân biệt các dữ liệu với nhau. Khóa này duy nhất cho từng dữ liệu và được dùng để sắp xếp. Lưu ý, không có khóa trùng lặp cho hai dữ liệu phân biệt chính bởi vậy các giải thuật sắp xếp mới thực hiện được. CuuDuongThanCong.com Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 3 / 92
  4. Bài toán sắp xếp Lưu ý khi biểu diễn bài toán sắp xếp trong máy tính Việc sắp xếp tiến hành trực tiếp trên bản ghi dữ liệu đòi hỏi các thao tác di chuyển tốn kém. Vì vậy người ta thường xây dựng một bảng khóa gồm các bản ghi chỉ gồm hai trường là (khóa, con trỏ) : I trường "khóa" chứa giá trị khóa I trường "con trỏ" chứa địa chỉ trỏ đến các bản ghi dữ liệu tương ứng Việc sắp xếp theo khóa trong bảng khóa trên không đòi hỏi di chuyển các bản ghi dữ liệu - trong bảng chính, nhưng trình tự các bản ghi trong bảng khóa cho phép xác định trình tự các bản ghi dữ liệu trong bản chính. CuuDuongThanCong.com Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 4 / 92
  5. Bài toán sắp xếp Mô tả giải thuật của bài toán sắp xếp Đầu vào : Dãy gồm n khóa A = (a1 , a2 , · · · , an ) Đầu ra : Một hoán vị của dãy A là dãy A0 = (a10 , a20 , · · · , an0 ) sao cho dãy thỏa mãn a10 ≤ a20 ≤ · · · ≤ an0 Độ quan trọng của thuật toán sắp xếp 40% thời gian hoạt động của máy tính là dành cho việc sắp xếp - D.Knuth CuuDuongThanCong.com Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 5 / 92
  6. Bài toán sắp xếp (tiếp) Phân loại Sắp xếp trong (internal sort) : Đòi hỏi họ dữ liệu đc đưa toàn bộ vào bộ nhớ trong của máy tính Sắp xếp ngoài (external sort) : Họ dữ liệu không thể cũng lúc đưa toàn bộ vào bộ nhớ trong, nhưng có thể đọc vào từng bộ phận từ bộ nhớ ngoài Đặc trưng Tại chỗ (in place) : nếu không gian nhớ phụ mà thuật toán đòi hỏi là O(1), nghĩa là chặn bởi hằng số không phụ thuộc vào độ dài của dãy cần sắp xếp Ổn định (stable) : nếu các phần tử có cùng giá trị vẫn giữ nguyên thứ tự tương đối của chúngCuuDuongThanCong.com như trước khi sắp xếp Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 6 / 92
  7. Bài toán sắp xếp (tiếp) Hai phép toán cơ bản mà thuật toán sắp xếp thường sử dụng Đổi chỗ (swap) : thời gian thực hiện là O(1), ví dụ mã nguồn cài đặt trên C void swap(datatype &a, datatype &b){ datatype temp = a; a=b; b=temp; } So sánh (compare) : hàm compare(a,b) trả lại true nếu a ở vị trí trước b theo thứ tự cần sắp xếp và false nếu trái lại. CuuDuongThanCong.com Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 7 / 92
  8. 1 Bài toán sắp xếp 2 Ba thuật toán sắp xếp cơ bản 3 Sắp xếp trộn 4 Sắp xếp nhanh 5 Sắp xếp vun đống 6 Cận dưới cho bài toán sắp xếp 7 Tổng kết 8 Các phương pháp sắp xếp đặc biệt CuuDuongThanCong.com Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 8 / 92
  9. Ba thuật toán sắp xếp cơ bản Sắp xếp chèn - insertion sort Phỏng theo cách làm của người chơi bài, mỗi khi có một quân bài mới người chơi sẽ tìm vị trí thích hợp trong bộ bài đang cầm trên tay để chèn lá bài mới này vào sao cho giá trị quân bài tăng dần đều. CuuDuongThanCong.com Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 9 / 92
  10. Ba thuật toán sắp xếp cơ bản Sắp xếp chèn (tiếp) Thuật toán Tại bước thứ k = 1, 2, · · · , n đưa phần tử thứ k trong mảng A đã cho vào đúng vị trí trong dãy gồm k phần tử. Kết quả sau mỗi bước k là k phần tử đầu tiên được sắp xếp đúng thứ tự. CuuDuongThanCong.com Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà5 Nội. tháng) 3 năm 2014 10 / 92
  11. Ba thuật toán sắp xếp cơ bản Sắp xếp chèn (tiếp) Mã giả của giải thuật sắp xếp chèn Procedure Insertion-Sort(A,n) 1 for i ← 2 to n do 2 last ← A[i] 3 j←i 4 while (j>1 and A[j-1] > last) do 5 A[j] ← A[j-1] 6 j ← j-1 7 endwhile 8 A[j] ← last 9 endfor CuuDuongThanCong.com End Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà5 Nội. tháng) 3 năm 2014 11 / 92
  12. Ba thuật toán sắp xếp cơ bản Minh họa với dãy không được sắp xếp gồm 8 phần tử A = {42, 20, 17, 13, 28, 14, 23, 15} i=2 42 20 17 13 28 14 23 15 i=3 20 42 17 13 28 14 23 15 i=4 17 20 42 13 28 14 23 15 i=5 13 17 20 42 28 14 23 15 i=6 13 17 20 28 42 14 23 15 i=7 13 14 17 20 28 42 23 15 i=8 13 14 17 20 23 28 42 15 CuuDuongThanCong.com 13 14 15 17 20 23 28 42 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà5 Nội. tháng) 3 năm 2014 12 / 92
  13. Ba thuật toán sắp xếp cơ bản Cấu trúc dữ liệu và giải thuật Minh họa với dãy không được sắp xếp gồm 8 phần tử A = {42, 20, 17, 13, 28, 14, 23, 15} 2014-03-05 Ba thuật toán sắp xếp cơ bản i=2 i=3 42 20 20 42 17 17 13 13 28 28 14 14 23 23 15 15 i=4 17 20 42 13 28 14 23 15 Sắp xếp chèn i=5 13 17 20 42 28 14 23 15 i=6 13 17 20 28 42 14 23 15 Ba thuật toán sắp xếp cơ bản i=7 13 14 17 20 28 42 23 15 i=8 13 14 17 20 23 28 42 15 13 14 15 17 20 23 28 42 Các phép gán A[j] ← A[j-1] được biểu diễn bằng các mũi tên một chiều. Giá trị last ← A[i] được tô mầu xanh sẽ được gán cuối cùng tại vị trí A[j] được tô mầu cam CuuDuongThanCong.com
  14. Ba thuật toán sắp xếp cơ bản Sắp xếp chèn (tiếp) Các đặc tính của sắp xếp chèn Sắp xếp chèn là tại chỗ và ổn định. Nói cách khác nó luôn đúng và kết thúc. Thời gian của thuật toán I Trường hợp tốt nhất : 0 có hoán đổi hay dãy cho vào đã được sắp xếp rồi. I Trường hợp tồi nhất : Có n2 /2 hoán đổi và so sánh, khi dãy đầu vào có thứ tự ngược với chiều cần sắp xếp. I Trường hợp trung bình : Cần n2 /4 hoán đổi và so sánh. Rõ ràng thuật toán có thời gian tính tốt nhất trong trường hợp tốt nhất Là thuật toán tốt với dãy đã gần được sắp xếp, nghĩa là phần tử đưa CuuDuongThanCong.com vào gần với vị trí cần sắp xếp. Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà5 Nội. tháng) 3 năm 2014 13 / 92
  15. Ba thuật toán sắp xếp cơ bản Sắp xếp lựa chọn - selection sort Thuật toán lặp gồm đúng i = 1, 2, · · · , n − 1 vòng lặp 1 Tìm phần tử nhỏ nhất đưa vào vị trí 1 2 Tìm phần tử nhỏ thứ hai đưa vào vị trí 2 3 Tìm phần tử nhỏ thứ ba đưa vào vị trí 3 .... CuuDuongThanCong.com Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà5 Nội. tháng) 3 năm 2014 14 / 92
  16. Ba thuật toán sắp xếp cơ bản Sắp xếp lựa chọn (tiếp) Mã giả của giải thuật sắp xếp chọn Procedure Selection-Sort(A,n) 1 for i ← 1 to n-1 do 2 min ← i 3 for j ← i+1 to n do 4 if (A[j]
  17. Ba thuật toán sắp xếp cơ bản Minh họa với dãy không được sắp xếp gồm 8 phần tử A = {42, 20, 17, 13, 28, 14, 23, 15} i=1 42 20 17 13 28 14 23 15 i=2 13 20 17 42 28 14 23 15 i=3 13 14 17 42 28 20 23 15 i=4 13 14 15 42 28 20 23 17 i=5 13 14 15 17 28 20 23 42 i=6 13 14 15 17 20 28 23 42 i=7 13 14 15 17 20 23 28 42 CuuDuongThanCong.com 13 14 15 17 20 23 28 42 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà5 Nội. tháng) 3 năm 2014 16 / 92
  18. Ba thuật toán sắp xếp cơ bản Cấu trúc dữ liệu và giải thuật Minh họa với dãy không được sắp xếp gồm 8 phần tử A = {42, 20, 17, 13, 28, 14, 23, 15} 2014-03-05 Ba thuật toán sắp xếp cơ bản i=1 i=2 42 13 20 20 17 17 13 42 28 28 14 14 23 23 15 15 i=3 13 14 17 42 28 20 23 15 Sắp xếp lựa chọn i=4 i=5 13 13 14 14 15 15 42 17 28 28 20 20 23 23 17 42 Ba thuật toán sắp xếp cơ bản i=6 i=7 13 13 14 14 15 15 17 17 20 20 28 23 23 28 42 42 13 14 15 17 20 23 28 42 Các A[i] được tô mầu cam sẽ hoán đổi vị trí cho các A[min] tô mầu xanh tại mỗi bước lặp i. Mũi tên hai chiều chỉ phép đổi chỗ swap(A[i],A[min]) theo giải thuật. CuuDuongThanCong.com
  19. Ba thuật toán sắp xếp cơ bản Sắp xếp lựa chọn (tiếp) Phân tích thuật toán Trường hợp tốt nhất : 0 đổi chỗ, n2 /2 phép so sánh Trường hợp tồi nhất : n − 1 phép đổi chỗ và n2 /2 phép so sánh Trường hợp trung bình : O(n) phép đổi chỗ và n2 /2 phép so sánh Ưu điểm của sắp xếp lựa chọn là đổi chỗ ít. CuuDuongThanCong.com Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà5 Nội. tháng) 3 năm 2014 17 / 92
  20. Ba thuật toán sắp xếp cơ bản Sắp xếp nổi bọt - bubble sort Sắp xếp nổi bọt là phương pháp sắp xếp đơn giản thường được sử dụng như trong giáo trình nhập môn công nghệ thông tin. Thuật toán được trình bầy như sau : 1 Bắt đầu duyệt từ đầu dãy, ta so sánh phần tử tại vị trí hiện tại với phần tử ở vị trí kế tiếp đi sau nó, nếu chúng không đúng thứ tự thì đổi chỗ cho nhau. 2 Tiếp tục duyệt cho tới khi không còn phải đổi chỗ trong một lần duyệt, hay dãy đã đc sắp xếp xong. Tuy đơn giản nhưng đây là thuật toán sắp xếp kém hiệu quả nhất trong số ba thuật toán sắp xếp cơ bản. CuuDuongThanCong.com Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà5 Nội. tháng) 3 năm 2014 18 / 92
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2