MỘT THUẬT TOÁN GIÚP GIẢM THIỂU SỐ PHÉP SO SÁNH CHO BÀI TOÁN SẮP XẾP X + Y

Tóm tắt

Bài báo này đề xuất một thuật toán hiệu quả để giảm thiểu số lượng phép so sánh cho bài toán sắp xếp X + Y. Thuật toán đề xuất trước hết sắp xếp riêng các tập X và Y, sau đó tiến hành chọn từng cặp phần tử từ tập X và tập Y và thêm vào tập X + Y theo thứ tự tổng tăng dần của các cặp. Thuật toán được thiết kế với kỹ thuật có khả năng hạn chế số cặp phải xét trong mỗi lần chọn. Kỹ thuật có khả năng hạn chế số phần tử thuộc X được xét và chỉ xét duy nhất một phần tử thuộc Y để ghép cặp với mỗi phần tử thuộc X để chọn ra cặp có tổng nhỏ nhất trong các cặp chưa được chọn. Cấu trúc đống được sử dụng để lưu trữ và cập nhật lại các cặp được xét giúp các thao tác trong lựa chọn một cặp phần tử chỉ cần chạy trong thời gian O(log(n)) và tổng thời gian chạy của thuật toán là O(n²log(n)). Kết quả thực nghiệm cho thấy số lượng phép so sánh và thời gian chạy của thuật toán đề xuất nhỏ hơn đáng kể so với các giá trị số này của cách tiếp cận dựa trên thuật toán sắp xếp vun đống truyền thống.