TAILIEUCHUNG - Cấu trúc dữ liệu : Một số phương pháp sắp xếp part 1

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 = jN 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. | 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 l 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 i Ỗ Ò o 0 1 5 I I r 8

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• tài liệu Cấu trúc dữ liệu
• đề cương Cấu trúc dữ liệu
• giáo trình Cấu trúc dữ liệu
• bài giảng Cấu trúc dữ liệu
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• bài tập cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp