TNU Journal of Science and Technology
229(15): 29 - 34
http://jst.tnu.edu.vn 29 Email: jst@tnu.edu.vn
AN ALGORITHM HELPS REDUCE THE NUMBER OF COMPARISONS
FOR SORTING X + Y
Pham Van Viet *
Le Quy Don Technical University
ARTICLE INFO
ABSTRACT
Received:
17/7/2024
This paper proposes an efficient algorithm for comparison reduction for
sorting X + Y. The proposed algorithm first sorts set X and set Y
individually, then repeatedly selects a pair of elements from X and Y
and adds the pair into X + Y in ascending order of sums of pairs. The
algorithm is designed with a technique able to limit the number of pairs
to be considered for each selection. The technique is able to limit the
number of elements of X to be considered and considers only one
element of Y to be paired with each element of X to select the pair with
the smallest sum among the pairs that haven’t been selected. A heap
data structure used to store and update pairs to be considered helps
operations in selecting a pair only need to run in O(log(n)) time, and
the total running time of the algorithm is O(n2log(n)). The experimental
results show that the number of comparisons and the running time of
the proposed algorithm are significantly less than those of a traditional
heapsort based approach.
Revised:
30/9/2024
Published:
30/9/2024
KEYWORDS
Data structures and algorithms
Sorting algorithms
Heap sort
Sorting X + Y
Algorithm analysis
MT THUẬT TOÁN GIÚP GIẢM THIU S PHÉP SO SÁNH
CHO BÀI TOÁN SẮP XP X + Y
Phạm Văn Việt
Trường Đại hc K thuật Lê Quý Đôn
THÔNG TIN BÀI BÁO
TÓM TẮT
Ngày nhận bài:
17/7/2024
i báo y đ xut mt thut tn hiu qu đ gim thiu s ng
phép so sánh cho bài toán sp xếp X + Y. Thuật toán đ xut trước hết
sp xếp riêng c tập X Y, sau đó tiến hành chn tng cp phn t
t tập X tp Y thêm vào tp X + Y theo th t tổng tăng dn ca
c cp. Thuật tn đưc thiết kế vi k thut khả ng hạn chế s
cp phi xét trong mỗi ln chn. K thut có khả năng hạn chế s
phn t thuộc X được t và ch xét duy nhất mt phn t thuc Y đ
ghép cp vi mi phn t thuc X đ chn ra cp tng nh nht
trong các cặp chưa đưc chn. Cấu trúc đng đưc s dụng đ lưu tr
cập nht li c cặp được xét giúp các thao tác trong la chn mt
cp phn t ch cn chy trong thời gian O(log(n)) tng thi gian
chy ca thut toán O(n2log(n)). Kết qu thc nghim cho thy s
ợng phép so sánh thi gian chy ca thuật toán đ xut nh hơn
đáng k so với c giá tr s y của cách tiếp cn da tn thut tn
sp xếp vun đng truyn thng.
Ngày hoàn thiện:
30/9/2024
Ngày đăng:
30/9/2024
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
Sp xếp X + Y
Phân tích thuật toán
DOI: https://doi.org/10.34238/tnu-jst.10781
Email: v.v.pham2012@gmail.com
TNU Journal of Science and Technology
229(15): 29 - 34
http://jst.tnu.edu.vn 30 Email: jst@tnu.edu.vn
1. Gii thiu
Bài báo này đề xut thuật toán giải quyết bài toán sắp xếp X + Y. Bài toán có đầu vào là 2 tp
X Y số phn t như nhau yêu cầu đặt ra là đưa ra một tp tt c các cặp phn t gm
mt phn t thuộc X một phn t thuộc Y; các cặp này được sp xếp theo th t tng ca mi
cặp tăng dần [1]. Ví dụ ta có hai tập đầu vào là X = {0, 3, 4} và Y = {1, 5, 8} thì đầu ra là dãy các
cặp được sp xếp theo th t tổng tăng dần ca mi cặp như sau:
{0, 1}, {3, 1}, {0, 5}, {4, 1}, {0, 8}, {3, 5}, {4, 5}, {3, 8}, {4, 8}.
Đây bài toán sắp xếp nhiều ng dụng. Bài toán này thể ng dụng trong tìm kiếm
đường bay giữa hai điểm, đi qua một điểm trung gian sao cho tổng chi phí nhỏ nht [2].
Nhân hai đa thc ca mt biến duy nhất cũng thể s dng sp xếp X + Y [3]. Sp xếp X + Y
có thể ng dng trong thiết kế VLSI [4]. VLSI là quy trình tạo mạng điện tích hợp (IC) bằng cách
kết hợp hàng triệu hay hàng tỷ bóng bán dẫn vào một chíp. Trong một thuật toán trong thiết kế
VLSI, sp xếp X + Y một chương trình con tốn kém nhất. Sp xếp X + Y cũng được áp dụng
để giải bài toán 3SUM [5] hay ng dụng trong lĩnh vực x nh [6], [7]. Mt s ng dng
không nhất thiết phi sp xếp tt c các phần t trong X + Y, chỉ cn chn ra k phn t
tổng các phần t nh nhất, do đó ta còn có bài toán gần gũi với sp xếp X + Y là la chn k phn
t có tổng các phần t nh nht trong tp X1 + X2 + ... + Xm [8], [9].
Các tác giả trong [10] đã tóm tắt các nghiên cứu tiêu biểu gii quyết bài toán sp xếp X + Y.
Vi tp X Y kích thước bằng n, X + Y thể sp xếp bng thuật toán truyền thống như
thuật toán sp xếp vun đống... với độ phc tạp n2log(n). Đề xut ca Jean-Luc Lambert [11]
nói rằng có thể sp xếp X + Y vi O(n2) phép so sánh, nhưng lại dựa vào khả năng sắp xếp R - R
t tập R + R đã sắp xếp không cần phép so sánh nào. Vic sp xếp R - R thể thc hin
bng thuật toán truyền thống, trong đó việc so sánh r - r’ s - s’ không thực hiện mà thông qua
việc xác định th t của r + s’ s + r’ trong R + R. Việc xác định th t thc hin thế nào nếu
không cần so sánh không được trình bày. Nhưng tác giả kết lun th tc sp xếp R - R vẫn độ
phc tạp là n2log(n). Kane [12] đã chứng t rằng X + Y có thể sp xếp s dng O(nlog2n) phép so
sánh, nhưng cách cài đt thuật toán một cách hiệu qu cũng không được tả. Trong thc tế
không có cách tiếp cận được biết nào nhanh hơn cách tiếp cn dựa trên thuật toán sắp xếp truyn
thng với độ phc tạp là O(n2log(n2)) = O(n2log(n)) [8].
Bài báo này đề xut thuật toán để sp xếp X + Y vi mục tiêu giảm thiu s phép so sánh. Kết
qu thc nghim cho thy thuật toán đề xuất thể gim được đáng kể s phép so nh, so với
cách tiếp cn dựa trên thuật toán sắp xếp vun đống truyn thng.
Ni dung của các phn tiếp theo như sau: Phần 2 trình bày cách tiếp cn dựa trên thuật toán
sp xếp vun đống thuật toán đề xuất để giải bài toán X + Y. Phần 3 thực nghiệm đánh
giá. Phần cuối cùng đưa ra các kết lun.
2. Các thuật toán
Trong bài báo này, chúng tôi đề xut mt thuật toán mới đ sp xếp X + Y và so sánh với cách
tiếp cn dựa trên thuật toán sắp xếp vun đống truyn thng bng thc nghim. C hai cách tiếp
cn s được trình bày trong phần này.
2.1. Thuật toán sắp xếp vun đống và áp dụng sp xếp X + Y
Phần này trình bày thuật toán sắp xếp vun đống và cách sử dụng để sp xếp X + Y.
2.1.1. Thuật toán sp xếp vun đống
Thuật toán sắp xếp vun đống [13] số phép so sánh trong trường hp xu nhất là O(nlog(n))
một thuật toán mạnh trong nhóm các thuật toán truyền thống như sắp xếp nhanh hay hòa nhập
vi s phép so sánh trong trường hp xu nht lần lượt O(n2) và O(nlog(n)). Thuật toán sắp
xếp vun đống cho một danh sách các phần t thc hiện hai công việc. Trước hết thuật toán tạo
TNU Journal of Science and Technology
229(15): 29 - 34
http://jst.tnu.edu.vn 31 Email: jst@tnu.edu.vn
đống trên cùng danh ch các phn t ban đầu. Mi quan h giữa các phần t trong đống được
xác định qua ch s của nó. Trong một danh sách các phn t được đánh số t 0, phn t th i có
cha v trí [(i 1)/2], con trái v trí 2 × i + 1 con phi v trí 2 × i + 2 nếu có. Giá trị ca
phn t cha lớn hơn hoặc bằng giá trị ca phn t con. Phn t v trí đầu tiên của danh sách
không là con ca phn t nào và giá trị ln nht. Tiếp đó, thuật toán phân danh sách thành hai
phn, phn cuối danh sách gồm các phần t đã được sp xếp theo th t tăng dần phần đầu
danh sách gồm các phần t chưa được sp xếp, nhưng vẫn duy trì cấu trúc đống. Thuật toán lần
ợt đi ch phn t v trí đầu tiên cuối cùng ca phần đầu danh sách; sau đó phần t cui
cùng của phần đầu được kết np vào phần sau. Phần đầu khi đó thể không đảm bảo được trt
t đống do phn t trên đỉnh của đống ( v tđầu tiên của phần đầu) nh hơn c phần t con
của nó. Thuật toán sẽ đổi ch phn t đầu tiên với phn t con lớn hơn của cho đến khi đạt
được trt t của đống.
2.1.2. Áp dụng sp xếp X + Y
Bài báo áp dụng thuật toán sắp xếp vun đống để sp xếp X + Y như sau. Đầu tiên thuật toán
đưa tất c n2 b (x, y) vào một danh sách, trong đó x phần t thuộc X y là phần t thuc Y.
Sau đó thực hin thuật toán sắp xếp vun đống trên danh ch các bộ (x, y) theo tng của x y.
Thuật toán có số phép so sánh là O(n2log(n2)) = O(n2log(n)).
2.2. Thuật toán đề xut
Phần này trình bày thuật toán đề xuất và ví dụ minh họa cho các bước chy ca thuật toán.
2.2.1 Thuật toán
Thuật toán 1 thuật toán đề xut th hin bằng gi Python. Thuật toán đầu vào hai
tp X Y n phần tử, được lưu trong hai danh sách được đánh số t 0. Thuật toán cn to
ra tập X + Y được lưu trong danh sách XY có n × n phn t, mi phn t gm mt phn t thuc
X một phn t thuộc Y. Các phần t trong danh sách XY được sp xếp theo th t tổng tăng
dn ca hai phn t trong mi phn t. Thuật toán trước hết sp xếp riêng danh sách X Y sử
dng thuật toán sắp xếp vun đống. Thuật toán lưu trữ cập nht lại các cặp phn t phải xét đ
chn ra cặp tng nh nhất trong các cặp chưa được đưa vào XY trong danh sách XYS. Mỗi
phn t thuc XYS gm 3 thuộc tính: xID là chỉ s mt phn t thuộc X, yID là ch s mt phn
t thuộc Y và s tổng ca hai phn tử. Tuy nhiên, để đơn giản trong trình bày, thut ng cp ch
s ca hai phn t hoc cp phn t được dùng thay thế cho b 3 thành phần trong mt s ni
dung dưới đây, tổng ca hai phn t thuộc X Y thể tính được t cp ch số. Danh sách
XYS cấu trúc đống nh nhất theo giá trị tng s ca hai phn tử. Danh sách XYS ban đu ch
có một phn t (0, 0, X[0] + Y[0]) phn t tổng s nh nhất trong các phần t. Thuật toán
cũng lưu chỉ s ln nht ca phn t thuc X trong XYS trong biến lastXID, ban đầu 0. Tiếp
đó, thuật toán thc hiện vòng lặp for (dòng 7) với biến chạy step trong n × n lần. Mỗi bước lp
chn ra cặp có tổng nh nhất trong các cặp chưa được chọn để cho vào XY. Thuật toán đưa ra kỹ
thut hn chế s cp phn t phải xét trong mỗi ln chn. Mi phn t x thuc X ch được xét
ghép cặp với đúng một phn t thuộc Y, phần t nh nhất chưa được ghép cặp vi x. Mi ln
cp ch s xID, yID gc của đống XYS được chn: nếu yID < n - 1, thì cặp này được thay thế
bng cặp xID, yID + 1 được đưa xuống cho tới khi đạt được trt t đống (các cặp ghép xID
vi ch s phn t thuc Y nh hơn yID không được xét cp phn t tương ứng đã được đưa
vào XY, các cp vi ch s phn t thuc Y lớn hơn yID + 1 cũng không được xét tổng các
phn t tương ng lớn hơn hoặc bng X[xID] + Y[yID + 1]); nếu yID = n - 1 thì cặp (xID, yID)
b loi khỏi đống, xID s không còn xuất hin lại trong XYS vì yID = n - 1 đồng nghĩa với tt c
các cặp xID đã được chọn. Ngoài ra nếu xID là chỉ s ln nhất trong các chỉ s phn t thuc
X trong XYS (xID = lastXID) lastXID < n 1 ttăng lastXID lên một đơn vị bổ sung
thêm cặp ch s lastXID, 0 vào XYS. Danh sách các cặp phn t được xét XYS không có cặp nào
TNU Journal of Science and Technology
229(15): 29 - 34
http://jst.tnu.edu.vn 32 Email: jst@tnu.edu.vn
xID > lastXID do tổng các phần t tương ng ln hơn hoc bng X[lastXID] + Y[0], tức
XYS ch chứa các xID lastXID. Các k thuật này giúp hạn chế s phn t thuộc X được xét
trong mi ln chn.
Ngoài ra, cách lưu trữ các cặp phn t được xét trong cấu trúc đống giúp việc chn ra cp nh
nhất được thc hin trong thi gian O(1). Các thao tác thay thế cp phn t gốc, xóa cặp phn
t gốc thêm một cp phn tử, tương đương với thời gian đưa một cp phn t xuống phía
dưới hay lên phía trên của đống cho đến khi đạt được trt t của đống O(log(n)) [13]. Bng
nhng k thuật như vậy thuật toán đã giúp giảm s phép so sánh và thời gian tính toán để giải bài
toán sắp xếp X + Y.
Thuật toán 1. Thuật toán sắp xếp
Đầu vào: Hai danh sách đầu vào X và Y. Mỗi danh sách có n phần t vi ch s bắt đu t 0.
Đầu ra: Một danh sách đầu ra XY được sp xếp có n × n phn t. Mi phn t cha mt phn t
thuộc X và một phn t thuc Y.
1
Khi tạo danh sách XY rng
2
Sp xếp X bng thut toán sắp xếp vun đống
3
Sp xếp Y bng thut toán sắp xếp vun đống
4
Khi tạo đống XYS lưu các bộ (xID, yID, X[xID] + Y[yID]) được xét để chn ra cp phn t có tổng
nh nht
5
Thêm bộ (0, 0, X[0] + Y[0]) là b có tổng các phần t nh nhất vào XYS
6
Đặt lastXID = 0 # lastXID lưu chỉ s ln nht ca phn t thuc X trong XYS
7
for step in range(0, n*n)
8
Ly phn t XYS[0] gc ca đống XYS và đưa cặp phn t (x, y) tương ứng vi cp ch s
thuộc XYS[0] vào XY
9
Lưu XYS[0].xID và XYS[0].yID vào biến xID và yID
10
if (yID < n 1):
11
Thay thế phn t XYS[0] bng phn t (xID, yID + 1, X[xID] + Y[yID + 1])
12
Đưa (xID, yID + 1, X[xID] + Y[yID + 1]) xuống dưới cho đến khi đạt được trt t đống
nh nht
13
else: # trường hp yID == n - 1
14
Xóa XYS[0] gc khỏi đống XYS
15
if (xID == lastXID and lastXID < n - 1):
16
lastXID += 1
17
Thêm phần t (lastXID, 0, X[lastXID] + Y[0]) vào đng XYS
2.2.2. Ví dụ minh ha
Sau dòng lệnh 6, ta danh sách XY rỗng, danh sách X Y đã được sp xếp, đống XYS
mt phn t (0, 0, X[0] + Y[0]), chỉ s ln nht ca phn t thuc X trong XYS lưu trong biến
lastXID bng 0. Để minh họa cho các bước của vòng lặp for (dòng 7) với biến chy step ca thut
toán đề xuất, chúng tôi sử dụng đầu vào X = {0, 3, 4} Y = {1, 5, 8} đã đề cp trong phn gii
thiệu. Danh sách X và Y trong trường hợp này có kích thước n = 3 và đã được sp xếp.
Bng 1. Bng minh họa các bước chy thuật toán đề xut
step
lastXID
XYS
xID, yID, s
x, y, s
0
0
(0, 0, 1)
0, 0, 1
0, 1, 1
1
1
(1, 0, 4)(0, 1, 5)
1, 0, 4
3, 1, 4
2
2
(0, 1, 5)(1, 1, 8)(2, 0, 5)
0, 1, 5
0, 5, 5
3
2
(2, 0, 5)(1, 1, 8)(0, 2, 8)
2, 0, 5
4, 1, 5
4
2
(1, 1, 8)(2, 1, 9)(0, 2, 8)
1, 1, 8
3, 5, 8
5
2
(0, 2, 8)(2, 1, 9)(1, 2, 11)
0, 2, 8
0, 8, 8
6
2
(2, 1, 9)(1, 2, 11)
2, 1, 9
4, 5, 9
7
2
(1, 2, 11)(2, 2, 12)
1, 2, 11
3, 8, 11
8
2
(2, 2, 12)
2, 2, 12
4, 8, 12
TNU Journal of Science and Technology
229(15): 29 - 34
http://jst.tnu.edu.vn 33 Email: jst@tnu.edu.vn
Bng 1 th hiện giá trị của các biến đầu mỗi bước lp, trong đó: cột “step” là giá trị ca biến
step (chính là chỉ s bước lp), cột “lastXID” là ch s ln nht ca phn t X trong XYS, ct
“XYS” là đống lưu các b (xID, yID, X[xID] + Y[yID]) được xét để chn cặp tổng nh nht
trong các cặp chưa được chọn để đưa vào danh sách được sp xếp XY, cột “xID, yID, s” thể hin
b ch s hai phn t thuộc X Y được chọn để đưa vào XY tổng hai phn t, cột “x, y, s”
th hin b giá trị ca hai phn t thuộc X và Y được chọn để đưa vào XY và tổng hai phn t.
Vòng lặp for kết thúc sau 3 × 3 = 9 bước lp, ng với các giá trị step t 0 đến 8. Ta có các cặp
đã lần lượt được chọn để thêm vào XY là {0, 1}, {3, 1}, {0, 5}, {4, 1}, {3, 5}, {0, 8}, {4, 5}, {3,
8}, {4, 8}. Các cặp này đã được sp xếp theo th t tổng tăng dần.
Bng 2. So sánh thuật toán đề xuất và cách tiếp cn truyn thng
n
Đề xut
Truyn thng
Đề xut/ Truyn thng
#So sánh
Thi gian
#So sánh
Thi gian
#So sánh
Thi gian
100
94.778
31
235.047
69
40,32%
44,93%
200
449.945
126
1.099.708
304
40,91%
41,45%
300
1.106.137
294
2.687.296
887
41,16%
33,15%
400
2.095.983
562
5.039.003
1.664
41,60%
33,77%
500
3.419.819
961
8.187.691
2.868
41,77%
33,51%
600
5.095.811
1.500
12.185.630
4.371
41,82%
34,32%
700
7.145.070
1.996
17.001.861
6.398
42,03%
31,20%
800
9.567.964
2.659
22.714.673
8.649
42,12%
30,74%
900
12.362.638
3.489
29.310.098
11.173
42,18%
31,23%
1000
15.530.542
4.426
36.747.976
14.480
42,26%
30,57%
3. Thc nghiệm và đánh giá
Bài báo tiến hành thực nghim vi thuật toán “Đề xuất” cách tiếp cn dựa trên thuật toán
sp xếp vun đống “Truyền thống” đã tả Phn 2. Mi thuật toán được chy với các tập đầu
vào X Y các kích thước khác nhau n = 100, 200,..., 1000 s dụng máy tính xách tay bộ
x Intel(R) Core(TM) i3-1005G1 CPU @ 1.20GHz 1.19 GHz RAM 4 GB. Vi mỗi kích
thước n, mi thuật toán chạy 20 ln vi 20 b d liu ngẫu nhiên của các tập X Y. Giá trị ca
các phần t trong tập X Y nằm trong khong t 0 đến 50000. Vi mỗi kích thước n, s phép
so sánh trung bình thời gian chạy trung bình của 20 ln chạy được ghi nhn li cho thuật toán
“Đ xuất” và “Truyền thống”. Các phép so sánh ở đây bao gồm so sánh giữa các phần t thuc X
vi nhau, giữa các phần t thuc Y với nhau giữa tổng các cặp x + y vi nhau. Kết qu thc
nghim th hin trong Bảng 2, trong đó cột “#So sánh” “Thời gian” số phép so sánh trung
bình thời gian trung bình tính bằng ms (mili giây) của 20 ln chy, cột “Đề xut/Truyn
thống” t l phần trăm số phép so sánh trung bình thi gian chạy trung nh của thuật toán
đề xuất trên các giá trị s đó của cách tiếp cn da trên thuật toán sp xếp vun đống truyn thng.
Bng 2 cho thy s phép so sánh trung bình thời gian chạy trung bình của thuật toán đề
xuất ít hơn đáng kể so với các giá trị s đó của cách tiếp cn truyn thng, ch bằng chưa đến
43% chưa đến 45% các giá trị s đó của cách tiếp cn truyn thống. Tính trung bình thì số
phép so sánh trung bình và thời gian chạy trung bình của thuật toán đề xut ch bng khong 42%
34% các giá trị s đó của các tiếp cn truyn thng. Kết qu này được do thuật toán đề
xuất đã được thiết kế vi k thut hn chế các cặp được xét trong mỗi ln chn ra cp (x, y)
tổng nhất trong các cặp còn lại để đưa vào tập X + Y. Trong mi ln chn, k thuật khả
năng hạn chế s phn t thuộc X được xét chỉ xét duy nhất mt phn t thuộc Y để ghép cặp
vi mi phn t thuộc X. Bên cạnh đó, bằng cách lưu tr các cặp phn t được xét trong danh
sách tổ chức dưới dng cấu trúc đống nh nht theo tng ca cp phn t, vic chn cp phn t
có tng nh nht thc hin trong thời gian O(1) cặp này luôn nằm gc của đống, cũng chính
là ở đầu danh sách. Việc thay thế phn t và xóa phần t sau khi được chọn, và việc thêm phần t
được xét vào đống cũng thực hin vi thời gian O(log(n)). Như vậy mỗi bước lặp để chn ra mt