MỘT THUẬT TOÁN GIÚP GIẢM THIỂU SỐ PHÉP SO SÁNH CHO BÀI TOÁN SẮP XẾP X + Y=AN ALGORITHM HELPS REDUCE THE NUMBER OF COMPARISONS FOR SORTING X + Y

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Văn Việt Phạm

Ngôn ngữ: vie

Ký hiệu phân loại:

Thông tin xuất bản: Tạp chí Khoa học và Công nghệ - Đại học Thái Nguyên, 2024

Mô tả vật lý: tr.29 -34

Bộ sưu tập: Báo, Tạp chí

ID: 485151

Thêm vào giỏ

Bài báo này đề xuất một thuật toán hiệu quả để giảm thiểu số lượng phép so sánh cho bài toán sắp xếp X + Y. Thuật toán đề xuất trước hết sắp xếp riêng các tập X và Y, sau đó tiến hành chọn từng cặp phần tử từ tập X và tập Y và thêm vào tập X + Y theo thứ tự tổng tăng dần của các cặp. Thuật toán được thiết kế với kỹ thuật có khả năng hạn chế số cặp phải xét trong mỗi lần chọn. Kỹ thuật có khả năng hạn chế số phần tử thuộc X được xét và chỉ xét duy nhất một phần tử thuộc Y để ghép cặp với mỗi phần tử thuộc X để chọn ra cặp có tổng nhỏ nhất trong các cặp chưa được chọn. Cấu trúc đống được sử dụng để lưu trữ và cập nhật lại các cặp được xét giúp các thao tác trong lựa chọn một cặp phần tử chỉ cần chạy trong thời gian O(log(n)) và tổng thời gian chạy của thuật toán là O(n2log(n)). Kết quả thực nghiệm cho thấy số lượng phép so sánh và thời gian chạy của thuật toán đề xuất nhỏ hơn đáng kể so với các giá trị số này của cách tiếp cận dựa trên thuật toán sắp xếp vun đống truyền thống.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.

1. Đọc trực tuyến

1. Đọc trực tuyến

Tạo bộ sưu tập với mã QR