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

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 sắp xếp gồm các nội dung chính được trình bày như sau: 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, cận dưới cho bài toán sắp xếp, các phương pháp sắp xếp đặc biệt,..
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 5Chương 5 : Các thuật toán sắp xếpTrịnh Anh Phúc1 Bộ1mô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 20 tháng 4 năm 2016Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 4 năm 2016Ngày 20 tháng1 / 92Giới thiệu1Bài toán sắp xếp2Ba thuật toán sắp xếp cơ bản3Sắp xếp trộn4Sắp xếp nhanh5Sắp xếp vun đống6Cận dưới cho bài toán sắp xếp7Các phương pháp sắp xếp đặc biệt8Tổng kếtTrịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 4 năm 2016Ngày 20 tháng2 / 92Bài toán sắp xếpĐịnh nghĩa bài toán sắp xếpSắp xếp (Sorting) là quá trình tổ chức lại họ các dữ liệu theo thứ tự giảmdần hoặc tăng dần (ascending or descending order). Dữ liệu cần sắp xếpcó 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ảithuật sắp xếp mới thực hiện được.Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 4 năm 2016Ngày 20 tháng3 / 92Bài toán sắp xếpLưu ý khi biểu diễn bài toán sắp xếp trong máy tínhViệ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 thaotá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ỏ) :trường khóa chứa giá trị khóatrường con trỏ chứa địa chỉ trỏ đến các bản ghi dữ liệu tương ứngViệc sắp xếp theo khóa trong bảng khóa trên không đòi hỏi di chuyểncác bản ghi dữ liệu - trong bảng chính, nhưng trình tự các bản ghitrong bảng khóa cho phép xác định trình tự các bản ghi dữ liệu trongbản chính.Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 4 năm 2016Ngày 20 tháng4 / 92Bài toán sắp xếpMô 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 A = (a1 , a2 , · · · , an ) sao chodãy thỏa mãna1 ≤ a2 ≤ · · · ≤ anĐộ quan trọng của thuật toán sắp xếp40% thời gian hoạt động của máy tính là dành choviệc sắp xếp - D.KnuthTrịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 4 năm 2016Ngày 20 tháng5 / 92