tailieunhanh - Cấu trúc dữ liệu nâng cao P2

Một số phương pháp sắp xếp | Bài 2 Một số phương pháp sắp xếp I. Thuật toán sắp xếp nhanh - Quick Sort Ý tưởng Có dãy số a1 a2 . an Giải thuật Quicksort làm việc như sau Chọn x là một phần tử làm biên thường chọn là phần tử ở giữa dãy số. Phân hoạc dãy thành 3 dãy con 1. ak x với k 2. ak x với k 3. ak x với k Ak x Ak x Ak x Nếu số phần tử trong dãy con 1 3 lớn hơn 1 thì ta tiếp tục phân hoạch dãy 1 3 theo phương pháp trên. Ngược lại thì dừng. Giải thuật phân hoạch dãy am am 1 . an thành 2 dãy con Bước 1 Chọn tùy ý một phần tử a k trong dãy là giá trị biên m k n x a k i m j n Bước 2 Phát hiện và hiệu chỉnh cặp phần tử a i a j nằm sai vị trí Bước 2a Trong khi a i x i Bước 2b Trong khi a j x j-- Bước 2c Nếu i j 1 a i x a j x mà a j đứng sau a i Hoán vị a i a j i j-- Bước 3 Nếu i j Lặp lại Bước 2. chưa xét hết mảng Ngược lại Dừng Có thể phát biểu giải thuật sắp xếp Quicksort một cách đệ qui như sau Bước 1 Phân hoạch dãy am . an thành các dãy con - Dãy con 1 am. aj x - Dãy con 2 aj 1. ai-1 x - Dãy con 1 ai. an x Bước 2 Nếu m j dãy con 1 có nhiều hơn 1 phần tử Phân hoạch dãy am. aj Nếu i n dãy con 3 có nhiều hơn 1 phần tử Phân hoạch dãy ai. ar Ví dụ Cho dãy số a 12 2 8 5 1 6 4 15 Phân hoạch đoạn 1 1 r 8 x A 4 5 2 Phân hoạch đoạn 1 1 r 3 X A 2 2 Phân hoạch đoạn 1 5 r 8 X A 6 6