Đang chuẩn bị liên kết để tải về tài liệu:
Chương 4. SẮP XẾP THỨ TỰ

Bài toán sắp xếp thứ tự 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ử. Cho trước một dãy số a1 , a2 ,. , aN được lưu trữ trong cấu trúc dữ liệu mảng int. | Chương 4. SẮP XẾP THỨ TỰ 4.1. Bài toán sắp xếp thứ tự 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ử. Cho trước một dãy số a1 a2 . aN được lưu trữ trong cấu trúc dữ liệu mảng int A n Sắp xếp dãy số a1 a2 . aN là thực hiện việc bố trí lại các phần tử sao cho hình thành được dãy mới ak1 ak2 . akN có thứ tự giả sử xét thứ tự tăng nghĩa là aki aki_1. Mà để quyết định được những tình huống cần thay đổi vị trí các phần tử trong dãy cần dựa vào kết quả của một loạt phép so sánh. Chính vì vậy hai thao tác so sánh và gán là các thao tác cơ bản của hầu hết các thuật toán sắp xếp. Khi xây dựng một thuật toán sắp xếp cần chú ý tìm cách giảm thiểu những phép so sánh và đổi chỗ không cần thiết để tăng hiệu quả của thuật toán. Đối với các dãy số được lưu trữ trong bộ nhớ chính nhu cầu tiết kiệm bộ nhớ được đặt nặng do vậy những thuật toán sắp xếp đòi hỏi cấp phát thêm vùng nhớ để lưu trữ dãy kết quả ngoài vùng nhớ lưu trữ dãy số ban đầu thường ít được quan tâm. Thay vào đó các thuật toán sắp xếp trực tiếp trên dãy số ban đầu - gọi là các thuật toán sắp xếp tại chỗ - lại được đầu tư phát triển. Phần này giới thiệu một số giải thuật sắp xếp từ đơn giản đến phức tạp có thể áp dụng thích hợp cho việc sắp xếp nội 4.2. Sắp thứ tự nội 4.2.1. Sắp thứ tự bằng phương pháp lựa chọn trực tiếp Giải thuật Ta thấy rằng nếu mảng có thứ tự phần tử ai luôn là min ai ai 1 . an-1 . Ý tưởng của thuật toán chọn trực tiếp mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế chọn phần tử nhỏ nhất trong N phần tử ban đầu đưa phần tử này về vị trí đúng là đầu dãy hiện hành sau đó không quan tâm đến nó nữa xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu bắt đầu từ vị trí thứ 2 lặp lại quá trình trên cho dãy hiện hành. đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có N phần tử vậy tóm tắt ý tưởng thuật toán là thực hiện N-1 lượt việc đưa phần tử nhỏ