Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - ĐH Công nghệ Đồng Nai
lượt xem 32
download
Chương 3: Sắp xếp nội thuộc bài giảng Cấu trúc dữ liệu và giải thuật trình bày về đổi chỗ trực tiếp – Interchange Sort, chọn trực tiếp – Selection Sort, nổi bọt – Bubble Sort, chèn trực tiếp – Insertion Sort, chèn nhị phân, bài toán sắp xếp. Tài liệu này giúp ích cho quá trình học tập và giảng dạy.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - ĐH Công nghệ Đồng Nai
- CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CHƯƠNG 3 SẮP XẾP NỘI 1
- Nội Dung 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 4. Chèn trực tiếp – Insertion Sort 5. Chèn nhị phân – Binary Insertion Sort 6. Shaker Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort 2
- Bài Toán Sắp Xếp Cho danh sách có n phần tử a0, a1, a2…, an-1. Sắp xếp là quá trình xử lý các phần tử trong danh sách để đặt chúng theo một thứ tự thỏa mãn một số CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT tiêu chuẩn nào đó dựa trên thông tin lưu tại mỗi phần tử, như: Sắp xếp danh sách lớp học tăng theo điểm trung bình. Sắp xếp danh sách sinh viên tăng theo tên. … Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách trên trong bộ nhớ chính. 3
- Bài Toán Sắp Xếp (tt) a: là dãy các phần tử dữ liệu Để sắp xếp dãy a theo thứ tự (giả sử theo thứ tự tăng), ta tiến hành triệt tiêu tất cả các nghịch thế CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT trong a. Nghịch thế: • Cho dãy có n phần tử a0, a1,…,an-1 • Nếu iaj 34 3 4 8 a[0], a[1] là cặp nghịch thế Đánh giá độ phức tạp của giải thuật, ta tính Css: Số lượng phép so sánh cần thực hiện CHV: Số lượng phép hoán vị cần thực hiện 4
- Các Thuật Toán Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort 5
- Các Thuật Toán Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort 6
- Đổi Chỗ Trực Tiếp – Interchange Sort Ý tưởng: Xuất phát từ đầu dãy, tìm tất các các CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ 2 phần tử trong cặp nghịch thế. Lặp lại xử lý trên với phần tử kế trong dãy. 7
- Các Bước Tiến Hành Bước 1: i = 0; // bắt đầu từ đầu dãy Bước 2: j = i+1; //tìm các nghịch thế với a[i] Bước 3: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Trong khi j < N thực hiện Nếu a[j]
- Đổi Chỗ Trực Tiếp – Interchange Sort Cho dãy số a: 12 2 8 5 1 6 4 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT i=0 j=1 i=0 j=4 9
- CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Đổi Chỗ Trực Tiếp – Interchange Sort i=1 j=2 i=1 j=3 i=1 j=4 10
- CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Đổi Chỗ Trực Tiếp – Interchange Sort i=2 j=3 i=2 j=4 i=2 j=6 11
- Đổi Chỗ Trực Tiếp – Interchange Sort i=3 j=4 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT i=3 j=5 i=3 j=6 12
- CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Đổi Chỗ Trực Tiếp – Interchange Sort i=4 j=5 i=4 j=6 i=5 j=6 13
- CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Đổi Chỗ Trực Tiếp – Interchange Sort i=6 j=7 14
- Cài Đặt Đổi Chỗ Trực Tiếp void InterchangeSort(int a[], int N ) { int i, j; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT for (i = 0 ; i
- Minh Họa Thuật Toán j CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 i 16
- Minh Họa Thuật Toán j CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 12 2 8 5 2 6 4 15 0 0 1 2 3 4 5 6 7 i 17
- Minh Họa Thuật Toán j CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 2 4 12 8 5 6 4 15 0 1 0 2 3 4 5 6 7 i 18
- Minh Họa Thuật Toán j CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 2 4 5 12 8 6 5 15 0 1 20 3 4 5 6 7 i 19
- CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Minh Họa Thuật Toán 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 175 | 17
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 77 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 116 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 81 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 59 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 159 | 6
-
Bài giảng Cấu trúc dữ liệu - Chương 3: Cấu trúc cây
65 p | 58 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AA - Bùi Tiến Lên
30 p | 35 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 106 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây - Bùi Tiến Lên
68 p | 40 | 4
-
Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Thiều Quang Trung (2018)
44 p | 43 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên
38 p | 47 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch
24 p | 58 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 50 | 2
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