"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 6: Sắp xếp nhanh - Quick Sorts" trình bày thuật toán QuickSort, ví dụ về QuickSort, hoạt động của QuickSort, hiệu quả của QuickSort. Mời các bạn cùng tham khảo bài giảng để nắm chi tiết nội dung kiến thức. | Cấu trúc dữ liệu và giải thuật Bài 6. Sắp xếp nhanh - Quick Sorts Lecturer PhD. Ngo Huu Phuc Tel 0438 326 077 Mob 098 5696 580 Email ngohuuphuc76@ 1 Ngo Huu Phuc Le Quy Don Technical University Bài 6. Quick Sorts Nội dung . Thuật toán QuickSort 6 . Ví dụ về QuickSort 7 . Hoạt động của QuickSort 6 . Hiệu quả của QuickSort 6 Tham khảo 1. Intro to Algorithms Chapter 8 2. Lecture 5 3. Quick 4. Bài giảng của TS Nguyễn Nam Hồng 2 Ngo Huu Phuc Le Quy Don Technical University . Thuật toán QuickSort 1 6 Giải thuật Quick-sort là phương pháp sắp xếp dựa trên chiến lược chia để trị. x Giải thuật gồm các bước Phép chia chọn ngẫu nhiên một phần tử x làm khóa chia tập dữ liệu S ban đầu thành 3 phần x L chứa các phần tử nhỏ hơn x E chứa các phần tử bằng x L E G G chứa các phần tử lớn hơn x Bước lặp sắp xếp 2 tập L và G Hiệu chỉnh lại các tập L E x và G 3 Ngo Huu Phuc Le Quy Don Technical University . Thuật toán QuickSort 2 6 Các bước cơ bản của thuật toán Chia tập dữ liệu ban đầu thành 2 tập con sao cho tất cả các phần tử bên trái nhỏ hơn tất cả các phần tử bên phải. Sắp xếp 2 tập con một cách độc lập và nối chúng lại với nhau như vậy ta được dãy đã sắp xếp. 4 Ngo Huu Phuc Le Quy Don Technical University . Thuật toán QuickSort 3 6 Với mỗi tập con trên mỗi tập chia thành 02 tập con nếu có thể như vậy ta có tối đa 04 tập con. tập các phần tử nhỏ nhất ở bên trái cùng tập các phần tử lớn nhất ở bên phải cùng. Lặp lại quá trình trên cho đến khi tập chỉ có 1 phần tử nối tất cả các tập với nhau ta được dãy đã sắp xếp. 5 Ngo Huu Phuc Le Quy Don Technical University . Thuật toán QuickSort 4 6 Ta chia t ập dữ liệu ban đầu như sau Trên tập S lấy mỗi phần tử y được lấy ra khỏi tập Đưa phần tử y vào tập L E hay G tùy thuộc vào phép so sánh với khóa x Với mỗi phép lấy 1 phần tử và đưa chúng vào tập tương ứng độ phức tạp của phép toán đó là O 1 . Như vậy phép chia dữ liệu của thuật toán QuickSort có độ phức tạp O n . 6 Ngo .
