tailieunhanh - Giáo trình hướng dẫn kĩ thuật phân tích đánh giá giải thuật theo phương pháp tổng quan p5

Tầm quan trọng của bài toán sắp xếp Sắp xếp một danh sách các đối tượng theo một thứ tự nào đó là một bài toán thường được vận dụng trong các ứng dụng tin học. Ví dụ ta cần sắp xếp danh sách thí sinh theo tên với thứ tự Alphabet, hoặc sắp xếp danh sách sinh viên theo điểm trung bình với thứ tự từ cao đến thấp. | Giải thuật Sắp xếp BÀI TOÁN SẮP XẾP Tầm quan trọng của bài toán sắp xếp Sắp xếp một danh sách các đối tượng theo một thứ tự nào đó là một bài toán thường được vận dụng trong các ứng dụng tin học. Ví dụ ta cần sắp xếp danh sách thí sinh theo tên với thứ tự Alphabet hoặc sắp xếp danh sách sinh viên theo điểm trung bình với thứ tự từ cao đến thấp. Một ví dụ khác là khi cần tìm kiếm một đối tượng trong một danh sách các đối tượng bằng giải thuật tìm kiếm nhị phân thì danh sách các đối tượng này phải được sắp xếp trước đó. Tóm lại sắp xếp là một yêu cầu không thể thiếu trong khi thiết kế các phần mềm. Do đó việc nghiên cứu các phương pháp sắp xếp là rất cần thiết để vận dụng trong khi lập trình. Sắp xếp trong và sắp xếp ngoài Sắp xếp trong là sự sắp xếp dữ liệu được tổ chức trong bộ nhớ trong của máy tính ở đó ta có thể sử dụng khả năng truy nhập ngẫu nhiên của bộ nhớ và do vậy sự thực hiện rất nhanh. Sắp xếp ngoài là sự sắp xếp được sử dụng khi số lượng đối tượng cần sắp xếp lớn không thể lưu trữ trong bộ nhớ trong mà phải lưu trữ trên bộ nhớ ngoài. Cụ thể là ta sẽ sắp xếp dữ liệu được lưu trữ trong các tập tin. Chương này tập trung giải quyết vấn đề sắp xếp trong còn sắp xếp ngoài sẽ được nghiên cứu trong chương IV. Tổ chức dữ liệu và ngôn ngữ cài đặt Các đối tượng cần được sắp xếp là các mẩu tin gồm một hoặc nhiều trường. Một trong các trường được gọi là khóa key kiểu của nó là một kiểu có quan hệ thứ tự như các kiểu số nguyên số thực chuỗi ký tự. . Danh sách các đối tượng cần sắp xếp sẽ là một mảng của các mẩu tin vừa nói ở trên. Mục đích của việc sắp xếp là tổ chức lại các mẩu tin sao cho các khóa của chúng được sắp thứ tự tương ứng với quy luật sắp xếp. Để trình bày các ví dụ minh họa chúng ta sẽ dùng PASCAL làm ngôn ngữ thể hiện và sử dụng khai báo sau CONST N 10 TYPE KeyType integer OtherType real RecordType Record Key KeyType OtherFields OtherType end VAR a array of RecordType Nguyễn Văn Linh Trang 19 Giải thuật Sắp xếp PROCEDURE Swap