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

Khi thêm phần tử có khóa key vào bảng băm, hàm băm h(key) sẽ xác định địa chỉi trong khoảng từ 0 đến M-1.· Nếu chưa bị xung đột thì thêm phần tử mới vào địa chỉ i này.· Nếu bị xung đột thì hàm băm lại lần 1 h1 sẽ xét địa chỉ cách i là 12, nếu lạibị xung đột thì hàm băm lại lần 2 h2 sẽ xét địa chỉ cách i 22 ,… , quá trình cứ thếcho đến khi nào tìm được trống và thêm phần tử vào địa chỉ này....
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu : Một số phương pháp sắp xếp part 2Bước 3 : For i = 1 .. n do Ðặt ai vào lô Bt với t = chữ số thứ k của ai;Bước 4 : Nối B0, B1, ., B9 lại (theo đúng trình tự) thành a.Bước 5 : k = k+1; Nếu k < m thì trở lại bước 2. Ngược lại: DừngVí dụCho dãy số a:701 1725 999 9170 3252 4518 7009 1424 428 1239 8425 7013Phân lô theo hàng đơn vị:12 070111 172510 09999 91708 32527 45186 70095 14244 04283 1239 09992 8425 1725 4518 70091 7013 9170 0701 3252 7013 1424 8425 0428 1239CS A 0 1 2 3 4 5 6 7 8 9 6 Các lô B dùng để phân loạiPhân lô theo hàng chục:12 099911 700910 12399 45188 04287 17256 84255 14244 7013 04283 3252 17252 0701 7009 4518 84251 9170 0701 7013 1424 1239 3252 9170 0999CS A 0 1 2 3 4 5 6 7 8 9Phân lô theo hàng trăm:12 099911 917010 32529 12398 04287 17256 84255 1424 74 45183 7013 04282 7009 7013 3252 8425 17251 0701 7009 9170 1239 1424 4518 0701 0999CS A 0 1 2 3 4 5 6 7 8 9Phân lô theo hàng ngàn:12 099911 172510 07019 45188 04287 84256 14245 32524 12393 9170 0999 17252 7013 0701 1424 70131 7009 0428 1239 3252 4518 7009 8425 9170CS A 0 1 2 3 4 5 6 7 8 9Lấy các phần tử từ các lô B0, B1, ., B9 nối lại thành a:12 917011 842510 70139 70098 4518 87 32526 17255 14244 12393 09992 07011 0428CS A 0 1 2 3 4 5 6 7 8 9Ðánh giá giải thuật Với một dãy n số, mỗi số có tối đa m chữ số, thuật toán thựchiện m lần các thao tác phân lô và ghép lô. Trong thao tác phân lô,mỗi phần tử chỉ được xét đúng một lần, khi ghép cũng vậy. Nhưvậy, chi phí cho việc thực hiện thuật toán hiển nhiên là O(2mn) =O(n). NHẬN XÉT Thuật toán không có trường hợp xấu nhất và tốt nhất. Mọi dãy sốđều được sắp với chi phí như nhau nếu chúng có cùng số phần tửvà các khóa có cùng chiều dài. Thuật toán cài đặt thuận tiện với các mảng có khóa sắp xếp làchuỗi (ký tự hay số) hơn là khóa số như trong ví dụ do tránh đượcchi phí lấy các chữ số của từng số. Tuy nhiên, số lượng lô nhiều (10 khi dùng số thập phân, 26 khidùng chuỗi ký tự tiếng anh, ...) nhưng tổng kích thước của tất cảcác lô chỉ bằng dãy ban đầu nên ta không thể dùng mảng để biểudiễn B (B0->B9). Như vậy, phải dùng cấu trúc dữ liệu động đểbiểu diễn B => Radix sort rất thích hợp cho sắp xếp trên danh sáchliên kết. Khi sắp các dãy không nhiều phần tử, thuật toán Radix sortsẽ mất ưu thế so với các thuật toán khác. 9III. Sắp xếp cây - Heap sort1.Ý tưởng: Nhận xét: Khi tìm phần tử nhỏ nhất ở bước i, phương phápsắp xếp chọn trực tiếp không tận dụng được các thông tin đã cóđược do các phép so sánh ở bước i-1. Vì lý do trên người ta tìm cách xây dựng một thuật toán sắpxếp có thể khắc phục nhược điểm này. Mấu chôt để giải quyết vấn đề vừa nêu là phải tìm ra đượcmột cấu trúc dữ liệu cho phép tích lũy các thông tin về sự so sánhgiá trị các phần tử trong qua trình sắp xếp. Giả sử dữ liệu cần sắp xếp là dãy số : 5 2 6 4 8 1 được bố trítheo quan hệ so sánh và tạo thành sơ đồ dạng cây như sau : Trong đó một phần tử ở mức i chính là phần tử lớn trong cặpphần tử ở mức i+1, do đó phần tử ở mức 0 (nút gốc của cây) luônlà phần tử lớn nhất của dãy. Nếu loại bỏ phần tử gốc ra khỏi cây (nghĩa là đưa phần tử lớnnhất về đúng vị trí), thì việc cập nhật cây chỉ xảy ra trên nhữngnhánh liên quan đến phần tử mới loại bỏ, còn các nhánh khác đượcbảo toàn, nghĩa là bước kế tiếp có thể sử dụng lại các kết quả sosánh ở bước hiện tại. Trong ví dụ trên ta có : 10 ...