tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Bùi Tiến Lên

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 4: Các thuật toán sắp xếp" cung cấp cho người đọc các kiến thức: Bài toán sắp xếp, các phương pháp sắp xếp, selection sort, insertion sort, nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Bùi Tiến Lên CÁC THUẬT TOÁN SẮP XẾP Bùi Tiến Lên 01/01/2017 Bài toán sắp xếp I Sắp xếp một danh sách các đối tượng theo một thứ tự nào đó là một trong những công việc phổ biến I Sắp xếp là một yêu cầu không thể thiếu trong việc viết phần mềm ứng dụng I Do đó, nghiên cứu các phương pháp sắp xếp là cần thiết cho những ai học lập trình Spring 2017 Data structure & Algorithm 2 Bài toán sắp xếp (cont.) Định nghĩa 1 Cho một dãy a có n phần tử có thứ tự. Hãy sắp xếp dãy {a0 , a1 , ., an−1 } theo thứ tự tăng dần. Spring 2017 Data structure & Algorithm 3 Các phương pháp sắp xếp Có rất nhiều phương pháp sắp xếp khác nhau. Mỗi phương pháp có những đặc điểm riêng I Phương pháp Selection Sort I Phương pháp Insertion Sort I Phương pháp Bubble Sort I Phương pháp Shell Sort I Phương pháp Heap Sort I Phương pháp Merge Sort I Phương pháp Quick Sort I Phương pháp Radix Sort I Phương pháp Counting Sort Spring 2017 Data structure & Algorithm 4 SELECION SORT Selection Sort Ý tưởng của thuật toán như sau: Giả sử dãy a được chia làm hai phần: phần trên trái đã sắp xếp s và phần bên phải chưa sắp xếp u 1. s = ∅ và u = a 2. Tìm phần tử nhỏ nhất xm của u 3. Loại xm ra khỏi u thêm vào cuối của s 4. Nếu u vẫn còn phần tử thì quay lại bước 2 Spring 2017 Data structure & Algorithm 6 Selection Sort (cont.) 1 void SelectionSort (int a[], int n) 2 { 3 int min; 4 for (int i = 0; i < n; i++) 5 { 6 min = i; 7 for (int j = i + 1; j < n; j++) 8 if (a[j] < a[min ]) 9 min = j; 10 if .