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, | CÁC THUẬT TOÁN SẮP XẾP Bùi Tiến Lên 01 01 2017 https tailieudientucntt 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 amp Algorithm https tailieudientucntt 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 amp Algorithm https tailieudientucntt 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 amp Algorithm https tailieudientucntt 4 SELECION SORT https tailieudientucntt 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 amp Algorithm https tailieudientucntt 6 Selection Sort cont. 1 void SelectionSort int a int n 2 3 int min 4 for int i 0 i lt n i 5 6 min i 7 for int j i 1 j lt n j 8 if a j lt a min 9 min j 10 if a min lt a i 11 Swap a min a i 12 13 Spring 2017 Data structure amp Algorithm https tailieudientucntt 7 Đánh giá Phân tích chi phí thực hiện theo n số lượng phần tử của mảng Trường hợp O g n tốt nhất trung bình xấu nhất Spring 2017
