Bài giảng Cấu trúc dữ liệu và giải thuật: Các giải thuật sắp xếp - Lê Thị Ngọc Hạnh

Chương này trình bày một số nội dung chính như: giới thiệu bài toán sắp xếp, các phương pháp sắp xếp, đổi chỗ trực tiếp – interchange sort, interchange sort – thuật toán, interchange sort – cài đặt, interchange sort – đánh giá, sắp xếp chọn – selection sort, selection sort – ý tưởng,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Các giải thuật sắp xếp - Lê Thị Ngọc Hạnh CÁC GIẢI THUẬT SẮP XẾP GV: LÊ THỊ NGỌC HẠNH 19/4/2015 Data structure & Algorithms GIỚI THIỆU BÀI TOÁN SẮP XẾP Bài toán sắp xếp: Là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử. Lưu ý: Thứ tự đề cập ở đây là một thứ tự tổng quát. Ví dụ: Danh sách trước khi sắp xếp: {1, 25, 6, 5, 2, 37, 40} Danh sách sau khi sắp xếp: {1, 2, 5, 6, 25, 37, 40}9/4/2015 Data structure & Algorithms 2 GIỚI THIỆU BÀI TOÁN SẮP XẾP Khái niệm “Nghịch thế”Xét một mảng các số a0, a1, …, anNếu có iaj thì ta gọi đó là một nghịchthế.Mảng chưa sắp xếp sẽ có nghịch thếMảng đã có thứ tự sẽ không chứa nghịch thế9/4/2015 Data structure & Algorithms 3 CÁC PHƯƠNG PHÁP SẮP XẾP Selection sort  Quick sort Insertion sort  Merge sort Interchange sort  Radix sort Shaker sort Bubble sort  Radix sort Shaker sort … Binary Insertion sort…9/4/2015 Data structure & Algorithms 4 ĐỔI CHỖ TRỰC TIẾP – INTERCHANGE SORT Ý tưởng:Xuất phát từ đầu dãy, tìm tất cả nghịch thế chứaphần tử này triệt tiêu chúng bằng cách đổi chỗphần tử này tử này với phần tử tương ứng trongcặp nghịch thế.Lặp lại xử lý trên với các phần tử tiếp theo trongdãy.9/4/2015 Data structure & Algorithms 5 INTERCHANGE SORT – THUẬT TOÁNBước 1: Khởi tạo i=0 // bắt đầu từ đầu dãyBước 2: j = i+1; //tìm các cặp a[j]IBước 3: Trong khi j INTERCHANGE SORT – VÍ DỤ9/4/2015 Data structure & Algorithms 7 INTERCHANGE SORT – VÍ DỤ9/4/2015 Data structure & Algorithms 8 INTERCHANGE SORT – VÍ DỤ9/4/2015 Data structure & Algorithms 9 INTERCHANGE SORT – CÀI ĐẶTVoid InterchangeSort(int a[], int n){ int i, j; for(i = 0 ; iINTERCHANGE SORT – ĐÁNH GIÁSố lượng các phép so sánh xảy ra không phụthuộc vào tình trạng của dãy số ban đầu.Số lượng phép hoán vị thực hiện tùy thuộc vàokết quả so sánh9/4/2015 Data structure & Algorithms 11SẮP XẾP CHỌN – SELECTION SORT9/4/2015 Data structure & Algorithms 12 SELECTION SORT – Ý TƯỞNG Chọn phần tử nhỏ nhất đặt vào vị trí đầu tiên Chọn phần tử nhỏ nhất trong số n-1 phần tử còn lại đặt vào vị trí thứ 2. Lặp lại quá trình cho đến khi mảng chỉ còn 1 phần tử.9/4/2015 Data structure & Algorithms 13 SELECTION SORT – THUẬT TOÁN Bước 1: Khởi tạo i = 0. Bước 2: Khởi đầu min = i, j = i+1 Bước 3: Nếu a[j] SELECTION SORT – VÍ DỤ9/4/2015 Data structure & Algorithms 15 SELECTION SORT – VÍ DỤ9/4/2015 Data structure & Algorithms 16 SELECTION SORT – VÍ DỤ9/4/2015 Data structure & Algorithms 17 SELECTION SORT – VÍ DỤ9/4/2015 Data structure & Algorithms 18 SELECTION SORT – CÀI ĐẶTvoid SelectionSort(int a[],int n){ int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành for(int i=0; i SELECTION SORT – ĐÁNH GIÁSố phép so sánh: Tại lượt i bao giờ cũng cần (n-i-1) số lần so sánh Không phụ thuộc vào tình trạng dãy số ban đầu Số phép so sánh:9/4/2015 Data structure & Algorithms 20