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

Chương 5 - Sắp xếp. Trong chương này, người học có thể hiểu được một số kiến thức cơ bản về: Sắp xếp chèn (insertion sort), sắp xếp chọn (selection sort), sắp xếp nổi bọt (bubble sort), sắp xếp trộn (merge sort), sắp xếp nhanh (quick sort), sắp xếp vun đống (heap sort).
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 5 - Nguyễn Khánh Phương TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng coCấu trúc dữ liệu và giải thuật an th o ng Nguyễn Khánh Phương du u Computer Science department cu School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucnttNội dung khóa họcChương 1. Các khái niệm cơ bản omChương 2. Các sơ đồ thuật toán .c ngChương 3. Các cấu trúc dữ liệu cơ bản coChương 4. Cây anChương 5. Sắp xếp th o ng duChương 6. Tìm kiếm u cuChương 7. Đồ thị 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng coChương 5. Sắp xếp an th o ng Nguyễn Khánh Phương du u Computer Science department cu School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucnttBà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. om• Dữ liệu cần sắp xếp có thể là: .c – Số nguyên/thực.. (integers/float) ng – Xâu kí tự (character strings) co – …• Khóa sắp xếp (sort key) an th – Là bộ phận của bản ghi xác định thứ tự sắp xếp của bản ghi trong họ các bản ghi. o ng – Ta cần sắp xếp các bản ghi theo thứ tự của các khoá. du – Ví dụ: khóa là tong = toan + ly + hoa u typedef struct{ cu char *ma; struct{ float toan, ly, hoa, tong; } DT; }thisinh; typedef struct node{ thisinh data; struct node* next; 4 }node; CuuDuongThanCong.com https://fb.com/tailieudientucnttCác loại thuật toán sắp xếpSắ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 om• Ví dụ: .c – insertion sort (sắp xếp chèn), selection sort (sắp xếp lựa chọn), bubble sort (sắp xếp nổi bọt) ng – quick sort (sắp xếp nhanh), merge sort (sắp xếp trộn), heap sort (sắp xếp vun đống), sample co sort (sắp xếp dựa mẫu), shell sort (vỏ sò) anSắp xếp ngoài (external sort): th• Họ dữ liệu không ...