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

Phạm Văn Việt

doi:10.34238/tnu-jst.10781

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

Thông tin bài báo

Ngày nhận bài: 17/07/24 Ngày hoàn thiện: 30/09/24 Ngày đăng: 30/09/24

Các tác giả

Phạm Văn Việt , Trường Đại học Kỹ thuật Lê Quý Đôn

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.

Từ khóa

Các cấu trúc dữ liệu và thuật toán; Các thuật toán sắp xếp; Thuật toán sắp xếp vun đống; Sắp xếp X + Y; Phân tích thuật toán

Toàn văn:

PDF

Tài liệu tham khảo

[1] E. Demaine, J. Erickson, and J. O'Rourke, "Problem 41: Sorting X + Y (Pairwise Sums)," The Open Problems Project, 20 August 2006. [Online]. Available: https://topp.openproblem.net/p41. [Accessed May 01, 2024].

[2] S. Skiena, "4.4 War Story: Give me a Ticket on an Airplane," in The Algorithm Design Manual, 2nd ed., Springer, 2008, pp. 118-120.

[3] D. A. Klip, "New Algorithms for Polynomial Multiplication," SIAM Journal on Computing, vol. 8, no. 3, pp. 326-343, 1979.

[4] D. S. Johnson, A. S. LaPaugh, and R. Y. Pinter, "Minimizing channel density by lateral shifting of components," in the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, Virginia, USA, 1994, pp. 122-131.

[5] A. Grønlund and S. Pettie, "Threesomes, Degenerates, and Love Triangles," in IEEE 55th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, USA, 2014, pp. 621-630.

[6] M. T. El-Melegy and A. T. Kamal, "Color Image Processing Using Reduced Biquaternions With Application to Face Recognition in a PCA Framework," in the IEEE International Conference on Computer Vision, 2017, pp. 3039-3046.

[7] M. T. El-Melegy, A. T. Kamal, K. F. Hussain, and H. M. El-Hawary, "Classification by Principal Component Regression in the Real and Hypercomplex Domains," Arab J. Sci. Eng., vol. 48, pp. 10099-10108, 2023.

[8] P. Kreitzberg, K. Lucke, and O. Serang, "Selection on X₁ + X₂ + ... + X_m with layer-ordered heaps," arXiv preprint, 2020, doi: 10.48550/arXiv.1910.11993.

[9] O. Serang, "Optimally selecting the top k values from X + Y with layer-ordered heaps," PeerJ Computer Science, vol. 7, 2021, Art. no. e501.

[10] H. Kaplan, L. Kozma, O. Zamir, and U. Zwick, "Selection from heaps, row-sorted matrices and X + Y using soft heaps," arXiv preprint, 2018, doi: 10.48550/arXiv.1802.07041.

[11] J.-L. Lambert, "Sorting the sums (x_i + y_j) in O(n²) comparisons," Theoretical Computer Science, vol. 103, no. 1, pp. 137-141, 1992.

[12] D. M. Kane, S. Lovett, and S. Moran, "Near-optimal linear decision trees for k-SUM and related problems," arXiv preprint, 2017, doi: 10.48550/arXiv.1705.01720.

[13] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Section 6 Heap sort," in Introduction to Algorithms, 4th ed., The MIT Press, 2022, pp. 161-172.

DOI: https://doi.org/10.34238/tnu-jst.10781

Các bài báo tham chiếu

Hiện tại không có bài báo tham chiếu



Ghi nhớ