Áp dụng các mẫu thiết kế hướng đối tượng trong việc thiết lập các thuật toán tổ hợp

44 Chương 3 Thiết lập một số thuật giải sắp xếp Chương 3 của luận văn trình bày về việc thiết lập một số thuật giải sắp xếp cơ bản. Việc thiết lập này dựa trên tư tưởng đưa các thuật giải sắp xếp về dạng chia để trị của Merritt [20] và vận dụng khung thuật giải chia để trị đã trình bày ở chương 2 để tổng quát hóa. Đồng thời mục 3.4 của luận văn cũng đề xuất một cách phân loại cải tiến, phân cấp hơn phân loại của Dzung&Wong [8]. 3.1 Họ thuật giải sắp xếp Các thuật giải sắp xếp là một trong những thuật giải cơ bản được nghiên cứu từ rất lâu đối với ngành Khoa học máy tính. Trong các giáo trình cấu trúc dữ liệu truyền thống (Knuth-1973), các thuật giải này được xếp thành 3 nhóm dựa vào quá trình thao tác trên các phần tử: đổi chổ, chọn hoặc chèn mà các thuật giải đại diện là ℎ , và . Trong đó, các thuật giải phức tạp hơn như ℎ , và được biểu diễn như là sự tối ưu hóa từ các thuật giải cơ bản trên. Riêng thì được xem như sự phân loại thứ tư. 45 Năm 1985, Merritt đã trình bày một phương pháp phân loại mới cho các thuật giải sắp xếp [20] được gọi là “phân loại nghịch”. Trong đó các thuật giải sắp xếp được chia thành hai nhóm: dễ tách / khó ghép và khó tách / dễ ghép. Đại diện chính của nhóm dễ tách / khó ghép là thuật giải sắp xếp trộn ( ), còn đại diện chính của nhóm khó tách / dễ ghép là thuật giải sắp xếp nhanh ( ). Các thuật giải , được xem như các biến thể của còn các thuật giải , sẽ thuộc nhánh (xem Hình 3-1). Sự “khó” hay “dễ” ở đây biểu thị việc hoàn thành giai đoạn sắp xếp của các thuật giải. Nhóm thuật giải “khó ghép” hoàn thành việc sắp xếp ở giai đoạn ghép còn nhóm thuật giải “khó tách” thì hoàn thành việc sắp xếp ở giai đoạn tách. Hình 3-1 Phân loại các thuật giải sắp xếp Phương pháp phân loại này hiện nay đang được chấp nhận một cách rộng rãi, nhất là khi các tác giả Dzung và Wong cài đặt chúng theo mô hình cài đặt hướng đối tượng [8]. Các mục còn lại của chương 3 cũng dựa trên phương pháp phân loại này và cung cấp một giải pháp tổng quát hóa tương đối đầy đầy đủ và phân cấp hơn. 3.2 Thuật giải sắp xếp và phương pháp chia để trị Nhắc lại, việc tổng quát hóa các thuật giải sắp xếp dựa trên nhận xét rằng chúng có thể biểu diễn dưới dạng thuật giải chia để trị như hay . Khi đó, một thuật giải sắp xếp sẽ là lặp liên tục hai thủ tục sau: “tách” danh sách thành 46 hai danh sách con và “ghép” hai danh sách con này lại. Sự khác nhau trong việc “tách” và “ghép” sẽ tạo ra được những thuật giải sắp xếp khác nhau. Hình 3-2 Minh họa sự hoạt động của MergeSort và QuickSort Ví dụ ở thuật giải , việc sắp xếp hoàn tất ở thủ tục ghép hai danh sách con đã được sắp xếp còn thủ tục tách chỉ đơn giản là chia đôi danh sách làm hai phần. Trong khi đó, ở thuật giải , việc sắp xếp hoàn tất ở thủ tục tách hai danh sách con còn thủ tục ghép chỉ đơn giản nối hai danh sách con đã sắp xếp. Minh họa việc thực hiện hai thuật giải này ở Hình 3-2. Các thuật giải sắp xếp còn lại cũng có thể được xây dựng lại dựa vào việc thay đổi hai thủ tục này: sẽ tách danh sách thành hai phần với danh sách bên trái gồm 1 phần tử và là phần tử nhỏ nhất; cũng thực hiện tương tự nhưng khác ở cách đưa phần tử nhỏ nhất vào danh sách con bên trái; là một trường hợp của với tỉ lệ chia là (1, − 1)… Nhờ những nhận xét trên, ta hoàn toàn có thể xây dựng một thuật giải sắp xếp tổng quát và hơn nữa việc này sẽ dựa trên khung thuật giải chia để trị tổng quát. Thủ tục “tách” sẽ là thủ tục () và thủ tục “ghép” sẽ là thủ tục () của khung thuật giải chia để trị. Do đó, ta có thể xây dựng lớp kế thừa từ sẽ đại diện cho tất cả các thuật giải sắp xếp. Trong đó, các hook 47 () và () đã được cài đặt sẵn còn () và () sẽ được thi công ở các lớp thuật giải con cụ thể. Hình 3-3 thể hiện sự thừa kế giữa và các lớp thuật giải sắp xếp. Việc xây dựng thuật giải tổng quát này sẽ được trình bày trong mục 3.3 tiếp theo. Hình 3-3 Thuật giải sắp xếp tổng quát 3.3 Thuật giải sắp xếp tổng quát 3.3.1 Xây dựng khung thuật giải sắp xếp Đầu tiên trong việc xây dựng khung thuật giải cho các thuật giải sắp xếp là đặc tả lại bài toán. Không mất tính tổng quát khi chúng ta chỉ xét bài toán sắp xếp trên mảng được cài đặt bởi mảng một chiều. Do đó, đầu vào của bài toán là một danh sách các phần tử có thể so sánh được bởi một toán tử so sánh. Kết quả của bài toán là danh sách đó đã được sắp xếp lại theo thứ tự. Ta nhận thấy cấu trúc dữ liệu tương tự của đầu bài và kết quả, nên có thể sử dụng chung một lớp đối tượng để cùng mô tả cả hai. Bảng 3-1 Đặc tả bài toán sắp xếp public class ArraySortDesc implements DivConqProblem, DivConqSolution { 48 public ArraySortDesc(Object[] A, int lo, int hi, Comparator comp) { this.A = A; this.lo = lo; this.hi = hi; this.comp = comp; } protected int lo, hi; protected Object[] A; protected Comparator comp; } Tiếp theo, ta xây dựng lớp biểu diễn thuật giải sắp xếp tổng quát kế thừa từ thuật giải chia để trị. Lớp sẽ thi công hai hàm hook () và (). Hai hàm hook còn lại () và () sẽ nhượng quyền cho các lớp con là các thuật giải sắp xếp cụ thể. Bảng 3-2 Thuật giải sắp xếp tổng quát public class AbtractSort implements DivConqStrategy { @Override public final boolean isSimple(Problem problem) { ArraySortDesc p = (ArraySortDesc)problem; return p.lo >= p.hi; } @Override public Solution simplySolve(Problem problem) { return (Solution)problem; } @Override public final Problem[] divide(Problem problem) { ArraySortDesc p = (ArraySortDesc)problem; int mid = divide(p); return new ArraySortDesc[] { new ArraySortDesc(p.A, p.lo, mid, p.comparator), new ArraySortDesc(p.A, mid+1, p.hi, p.comparator) }; } @Override public final Solution combine(Problem p, Solution[] ss) { return combine((ArraySortDesc)p); 49 } public abstract int divide(ArraySortDesc p); public abstract ArraySortDesc combine(ArraySortDesc p); } isSimple(): Bài toán sắp xếp được gọi là đơn giản khi dãy cần xếp chỉ có một phần tử. simplySolve(): Lời giải của bài toán trong trường hợp đơn giản chỉ gồm một phần tử cũng chính là dãy đó. Do cách tổ chức dữ liệu, ta đặt lớp ArraySortDesc mô tả cả Problem và Solution nên hàm này chỉ cần ép kiểu từ Problem sang Solution và trả về kết quả. 3.3.2 Các thuật giải sắp xếp cụ thể Từ khung thuật giải sắp xếp trên, khi cài đặt một thuật giải sắp xếp cụ thể, ta sẽ tạo một lớp kế thừa từ và thi công hai hàm () và (). Bảng 3-3 và bảng 3-4 dưới đây là minh họa thuật giải sắp xếp chèn và thuật giải sắp xếp chọn kế thừa từ thuật giải sắp xếp tổng quát. Bảng 3-3 Thuật giải sắp xếp chèn public class InsertionSort extends AbstractSort { @Override public ArraySortDesc combine(ArraySortDesc p) { int j = p.hi; Object key = p.A[p.hi]; while (p.lo < j && p.comparator.isLessThan(key, p.A[j-1])){ p.A[j] = p.A[j-1]; p.A[j-1] = key; j = j - 1; } return p; } @Override public int divide(ArraySortDesc p) { return p.hi - 1; } } 50 Bảng 3-4 Thuật giải sắp xếp chọn public class SelectionSort extends AbstractSort { @Override public ArraySortDesc combine(ArraySortDesc p) { return p; } @Override public int divide(ArraySortDesc p) { int s = p.lo; for (int i = p.lo+1; i <= p.hi; i++) { if (p.comparator.isLessThan(p.A[i], p.A[s])) s = i; } Object min = p.A[s]; p.A[s] = p.A[p.lo]; p.A[p.lo] = min; return p.lo; } } Và từ đó, các thuật giải sắp xếp còn lại hoàn toàn có thể được cấu trúc lại theo phương pháp này. Thuật giải () () Merge Sort Trả về (lo+hi)/2 Trộn 2 danh sách con Insertion Sort Trả về hi Chèn A[hi] vào đúng vị trí Quick Sort Chia hai danh sách con bên trái nhỏ hơn và bên phải lớn hơn phần tử cầm canh, trả về vị trí cầm canh Không thực hiện gì Selection Sort Đổi chổ phần tử lớn nhất và A[hi], trả về hi Không thực hiện gì Bubble Sort Nổi bọt phần tử lớn nhất về A[hi], trả về hi Không thực hiện gì Heap Sort Đổi chổ A[lo] và A[hi], trả về hi Không thực hiện gì Radix Sort Chia hai danh sách con dựa vào số bit từ trái sang, trả về vị trí chia Không thực hiện gì Distribution Sort Chia hai danh sách con dựa vào số bit từ phải sang, trả về vị trí chia Trộn hai danh sách con Hình 3-4 Các thuật giải sắp xếp cụ thể 51 3.4 Một khung thuật giải sắp xếp phân cấp hơn Mục 3.3 đã cho ta được một khung thuật giải sắp xếp tổng quát mà từ đó các thuật giải khác có thể thừa kế được chiến thuật chia để trị từ lớp cơ sở và chỉ cài đặt lại hai thủ tục “tách” và “ghép”. Tuy nhiên, sự phân cấp này tương đối phẳng, ta không thấy được sự liên hệ giữa các thuật giải sắp xếp với nhau ví dụ như và mặc dù hai thuật giải này có sự tương đồng về mặt giải pháp. Do đó, ta cần đưa ra một mô hình tổng quát hóa các thuật giải sắp xếp phân cấp hơn, trong đó những thuật giải nào có sự tương đồng về giải pháp sẽ được kế thừa từ một thuật giải tổng quát “trung gian”. Những thuật giải tổng quát “trung gian” này cũng được kế thừa từ thuật giải sắp xếp tổng quát. Trước tiên, ta có một số nhận xét như sau: · , và : là những thuật giải sắp xếp chia danh sách cần sắp thành hai danh sách con dựa vào việc so sánh giá trị các phần tử và luôn đảm bảo rành buộc: các phần tử của danh sách con bên trái luôn nhỏ hơn các phần tử của danh sách con bên phải. Cụ thể hơn, các thuật giải này sẽ lần lượt đổi chổ các phần tử làm ảnh hưởng đến ràng buột trên. dựa vào phần tử cầm canh để chia danh sách sao cho danh sách bên trái nhỏ hơn và danh sách bên phải lớn hơn phần tử cầm canh. Trong trường hợp danh sách con chỉ gồm một phần tử thì sẽ biến thể thành . Còn là một phiên bản “in-place” của . Do vậy, ta có thể gom chung 3 thuật giải này vào một nhóm gọi là nhóm thuật giải sắp xếp bằng cách chia danh sách theo giá trị. · và : dễ dàng nhận thấy điểm chung của hai thuật giải này là trộn hai danh sách con đã được sắp, sự khác nhau chủ yếu là vị trí phân chia khi tách danh sách thành hai danh sách con. chia theo tỉ lệ ( , ) còn chia theo tỉ lệ (1, − 1). Do vậy, ta 52 có thể gom chung 2 thuật giải này vào một nhóm gọi là nhóm thuật giải sắp xếp bằng cách chia sách theo vị trí. · và : về mặt bản chất rõ ràng hai thuật giải này dựa trên giá trị bộ phận của phần tử nên ta gom chung vào nhóm thuật giải sắp xếp theo giá trị bộ phận. Như vậy, các thuật giải sắp xếp sẽ được phân thành 3 nhóm: sắp xếp bằng cách chia danh sách theo vị trí, sắp xếp bằng cách chia danh sách theo giá trị và sắp xếp bằng cách chia danh sách theo giá trị bộ phận theo mô hình ở Hình 3-5. Hình 3-5 Phân loại các thuật giải sắp xếp theo logic