Bài giảng môn học Cấu trúc Dữ liệu và Giải thuật: Phần 2

Phần 2 "Bài giảng môn học Cấu trúc Dữ liệu và Giải thuật" gồm nội dung chương 3 và chương 4. Nội dung phần 2 gồm có: Sắp xếp (sorting), các cấu trúc dữ liệu cơ bản. Mời bạn đọc tham khảo bài giảng để hiểu các nội dung trên.
Nội dung trích xuất từ tài liệu:
Bài giảng môn học Cấu trúc Dữ liệu và Giải thuật: Phần 2Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuậtChương 3: Sắp xếp (Sorting)1. Bài toán sắp xếp Sắp xếp được xem là một trong những lĩnh vực nghiên cứu cổ điển của khoa họcmáy tính. Trước khi đi vào các thuật toán chi tiết chúng ta cần nắm vững một số khái niệmcơ bản sau: · Một trường (field) là một đơn vị dữ liệu nào đó chẳng hạn như tên, tuổi, số điện thoại của một người ... · Một bản ghi (record) là một tập hợp các trường · Một file là một tập hợp các bản ghi Sắp xếp (sorting) là một quá trình xếp đặt các bản ghi của một file theo một thứ tựnào đó. Việc xếp đặt này được thực hiện dựa trên một hay nhiều trường nào đó, và cácthông tin này được gọi là khóa xắp xếp (key). Thứ tự của các bản ghi được xác định dựatrên các khóa khác nhau và việc sắp xếp đối được thực hiện đối với mỗi khóa theo các thứtự khác nhau. Chúng ta sẽ tập trung vào các thuật toán xắp xếp và giả sử khóa chỉ gồm 1trường duy nhất. Hầu hết các thuật toán xắp xếp được gọi là các thuật toán xắp xếp sosánh: chúng sử dụng hai thao tác cơ bản là so sánh và đổi chỗ (swap) các phần tử cần sắpxếp. Các bài toán sắp xếp đơn giản được chia làm hai dạng. Sắp xếp trong (internal sorting): Dữ liệu cần sắp xếp được lưu đầy đủ trong bộ nhớtrong để thực hiện thuật toán sắp xếp. Sắp xếp ngoài (external sorting): Dữ liệu cần sắp xếp có kích thước quá lớn vàkhông thể lưu vào bộ nhớ trong để sắp xếp, các thao tác truy cập dữ liệu cũng mất nhiềuthời gian hơn. Trong phạm vi của môn học này chúng ta chỉ xem xét các thuật toán sắp xếp trong.Cụ thể dữ liệu sắp xếp sẽ là một mảng các bản ghi (gồm hai trường chính là trường dữ liệuvà trường khóa), và để tập trung vào các thuật toán chúng ta chỉ xem xét các trường khóacủa các bản ghi này, các ví dụ minh họa và cài đặt đều được thực hiện trên các mảng sốnguyên, coi như là trường khóa của các bản ghi.2. Sắp xếp gián tiếp Khi các bản ghi có kích thước lớn việc hoán đổi các bản ghi là rất tốn kém, khi đó đểgiảm chi phí người ta có thể sử dụng các phương pháp sắp xếp gián tiếp. Việc này có thểđược thực hiện theo nhiều cách khác nhau và môt trong những phương pháp đó là tạo ramột file mới chứa các trường khóa của file ban đầu, hoặc con trỏ tới hoặc là chỉ số của cácbản ghi ban đầu. Chúng ta sẽ sắp xếp trên file mới này với các bản ghi có kích thước nhỏ vàsau đó truy cập vào các bản ghi trong file ban đầu thông qua các con trỏ hoặc chỉ số (đây làcách làm thường thấy đối với các hệ quản trị cơ sở dữ liệu). Ví dụ: chúng ta muốn sắp xếp các bản ghi của file sau đây: Index Dept Last First Age ID number 1 123 Smith Jon 3 234-45-4586 - 19 -Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuật 2 23 Wilson Pete 4 345-65-0697 3 2 Charles Philip 9 508-45-6859 4 45 Shilst Greg 8 234-45-5784 Sau khi sắp xếp xong để truy cập vào các bản ghi theo thứ tự đã sắp xếp chúng tasử dụng thứ tự được cung cấp bởi cột index (chỉ số). Trong trường hợp này là 3, 2, 4, 1.(chúng ta không nhất thiết phải hoán đổi các bản ghi ban đầu).3. Các tiêu chuẩn đánh giá một thuật toán sắp xếp Các thuật toán sắp xếp có thể được so sánh với nhau dựa trên các yếu tố sau đây: · Thời gian thực hiện (run-time): số các thao tác thực hiện (thường là số các phép so sánh và hoán đổi các bản ghi). · Bộ nhớ sử dụng (Memory): là dung lượng bộ nhớ cần thiết để thực hiện thuật toán ngoài dung lượng bộ nhớ sử dụng để chứa dữ liệu cần sắp xếp. o Một vài thuật toán thuộc loại “in place” và không cần (hoặc cần một số cố định) thêm bộ nhớ cho việc thực hiện thuật toán. o Các thuật toán khác thường sử dụng thêm bộ nhớ tỉ lệ thuận theo hàm tuyến tính hoặc hàm mũ với kích thước file sắp xếp. o Tất nhiên là bộ nhớ sử dụng càng nhỏ càng tốt mặc dù việc cân đối giữa thời gian và bộ nhớ cần thiết có thể là có lợi. · Sự ổn định (Stability):Một thuật toán được gọi là ổn định nếu như nó có thể giữ được quan hệ thứ tự của các khóa bằng nhau (không làm thay đổi thứ tự của các khóa bằng nhau). Chúng ta thường lo lắng nhiều nhất là về thời gian thực hiện của thuật toán vì cácthuật toán mà chúng ta bàn về thường sử dụng kích thước bộ nhớ tương đương nhau. Ví dụ về sắp xếp ổn định: Chúng ta muốn sắp xếp file sau đây dự trên ký tự đầu củacác bản ghi và dưới đây là kết quả sắp xếp của các thuật toán ổn định và không ổn định: - 20 -Bài giảng môn học: Cấu ...