检索结果-内蒙古大学图书馆

algorithms AND AVERAGE TIME-BOUNDS OF sorting ON A MESH-CONNECTED COMPUTER

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1994年第3期5卷 308-315页

作者： GU, QP GU, J UNIV CALGARY DEPT ELECT & COMP ENGN CALGARY T2N 1N4 ALBERTA CANADA

In this paper, we give three new parallel sorting algorithms on a mesh-connected computer with wraparound connections (i.e., a torus). These three algorithms, with the minimum queue size of 1, sort n 2 random input data items into a blocked snakelike row major order, a row major order, and a snakelike row major order, in 1.5n + o(n), 2n + o(n), and 2n + o(n) average steps, respectively. These results improve the previous results of 2n + o(n), 2.5n + o(n), and 2.5n + o(n), respectively. In addition, we prove in this paper that the distance bound n on a torus is an average-time lower bound independent of indexing schemes of sorting random input data items on it.

关键词： AVERAGE TIME COMPLEXITY MESH-CONNECTED COMPUTER PARALLEL algorithms sorting algorithms TORUS

来源：评论

学校读者我要写书评

暂无评论

Visualizing algorithms: A Comprehensive Exploration of sorting and Computational Problem-Solving

Visualizing Algorithms: A Comprehensive Exploration of Sorti...

引用

2023 International Conference on Integrated Intelligence and Communication Systems, ICIICS 2023

作者： Dubey, Subham Gupta, Shivansh Kumar, Aditya Kaur, Gurmeet Chandigarh University Department of Computer Science Punjab Mohali India

ISBN: (纸本)9798350315455

Effective visuals are essential for solving computational issues and comprehending complicated algorithms. Through the use of a web-based sorting Algorithm Visualizer and associated components, this study presents a fresh approach to algorithm visualization. We look at different approaches to sorting, approaches to solving problems, and computing difficulties. With the help of a visual depiction, users may better understand the inner workings of sorting algorithms like bubble sort, selection sort, insertion sort, merge sort, fast sort, etc. by using the sorting Algorithm Visualizer. Positive user feedback exhibiting better algorithmic comprehension is shown in the research, which highlights the sorting Algorithm Visualizer's efficacy in offering an interactive and complete platform for viewing and learning sorting algorithms. The project's accomplishments and room for expansion demonstrate how crucial visualization is to understanding algorithms and addressing computational problems. © 2023 IEEE.

关键词： Algorithm Visualization Computational Problem-Solving Educational Tools Interactive Learning sorting algorithms Visualization Techniques

来源：评论

学校读者我要写书评

暂无评论

A comparison-free sorting algorithm on CPUs and GPUs

引用

JOURNAL OF SUPERCOMPUTING 2018年第11期74卷 6369-6400页

作者： Abdel-hafeez, Saleh Gordon-Ross, Ann Abubaker, Samer Jordan Univ Sci & Technol Irbid 22110 Jordan Univ Florida Dept Elect & Comp Engn Gainesville FL 32611 USA Univ Florida NSF Ctr High Performance Reconfigurable Comp CHRE Gainesville FL USA

This paper presents a new sorting algorithm that sorts input data elements without any comparison operations between the datacomparison-free sorting. Our algorithm's time complexity is on the order of O(N) for both single- and multi-threaded CPU and many-core GPU implementations. Our results show speedups on average of 4.6x, 4x, and 3.5xfor single-threaded CPU, 8-threaded CPU, and many-threaded GPU implementations, respectively, for input sizes ranging from 2(7) to 2(30) elements as compared to common sorting algorithms for a wide variation of element distributions, ranging from all unique elements to a single repeated element. In addition, our proposed algorithm more efficiently utilizes the GPU architecture as compared to a multi-core CPU architecture, showing a speedup of approximately 4x for input sizes ranging from 2(7) to 2(30) elements.

关键词： Comparison-free sort Parallel CUDA code Multi-core CPUs Many-threaded GPUs Big data Parallel computing SIMD sorting algorithms

来源：评论

学校读者我要写书评

暂无评论

Noisy sorting Capacity

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第9期70卷 6121-6138页

作者： Wang, Ziao Ghaddar, Nadim Zhu, Banghua Wang, Lele Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada Univ Toronto Dept Elect & Comp Engn Toronto ON M5S 3G8 Canada Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA

sorting is the task of ordering n elements using pairwise comparisons. It is well known that m = Theta(nlogn) comparisons are both necessary and sufficient when the outcomes of the comparisons are observed with no noise. In this paper, we study the sorting problem when each comparison is incorrect with some fixed yet unknown probability p. Unlike the common approach in the literature which aims to minimize the number of pairwise comparisons m to achieve a given desired error probability, we consider randomized algorithms with expected number of queries E[M] and aim at characterizing the maximal sorting rate nlogn/E[M] such that the ordering of the elements can be estimated with a vanishing error probability asymptotically. The maximal rate is referred to as the noisy sorting capacity. In this work, we derive upper and lower bounds on the noisy sorting capacity. The two lower bounds - one for fixed-length algorithms and one for variable-length algorithms - are established by combining the insertion sort algorithm with the well-known Burnashev-Zigangirov algorithm for channel coding with feedback. Compared with existing methods, the proposed algorithms are universal in the sense that they do not require the knowledge of p, while maintaining a strictly positive sorting rate. Moreover, we derive a general upper bound on the noisy sorting capacity, along with an upper bound on the maximal rate that can be achieved by sorting algorithms that are based on insertion sort.

关键词： sorting Noise measurement Noise Upper bound Codes Error probability Task analysis sorting algorithms coding for channels with feedback posterior matching

来源：评论

学校读者我要写书评

暂无评论

Adaptive Shivers Sort: An Alternative sorting Algorithm

引用

ACM TRANSACTIONS ON algorithms 2024年第4期20卷 1-55页

作者： Juge, Vincent Univ Gustave Eiffel LIGM UMR 8049 CNRS Marne la Vallee France

We present a new sorting algorithm, called adaptive ShiversSort, that exploits the existence of monotonic runs for sorting efficiently partially sorted data. This algorithm is a variant of the well-known algorithm TimSort, which is the sorting algorithm used in standard libraries of programming languages, such as Python or Java (for non-primitive types). More precisely, adaptive ShiversSort is a so-called k-aware merge-sort algorithm, a class that captures 'TimSort-like' algorithms and that was introduced by Buss and Knop. In this article, we prove that, although adaptive ShiversSort is simple to implement and differs only slightly from TimSort, its computational cost, in number of comparisons performed, is optimal within the class of natural merge-sort algorithms, up to a small additive linear term. This makes adaptive ShiversSort the first k-aware algorithm to benefit from this property, which is also a 33% improvement over TimSort's worst-case. This suggests that adaptive ShiversSort could be a strong contender for being used instead of TimSort. Then, we investigate the optimality of k-aware algorithms. We give lower and upper bounds on the best approximation factors of such algorithms, compared to optimal stable natural merge-sort algorithms. In particular, we design generalisations of adaptive ShiversSort whose computational costs are optimal up to arbitrarily small multiplicative factors. CCS Concepts: center dot Theory of computation -> sorting and searching

关键词： sorting algorithms merge sorts entropy worst-case complexity approx- imability

来源：评论

学校读者我要写书评

暂无评论

Parallel Multidimensional Lookahead sorting Algorithm

引用

IEEE ACCESS 2019年 7卷 75446-75463页

作者： Gebali, Fayez Taher, Mohamed Zaki, Ahmed M. El-Kharashi, M. Watheq Tawfik, Ayman Univ Victoria Dept Elect & Comp Engn Victoria BC V8W 3P6 Canada Ain Shams Univ Fac Engn Comp & Syst Engn Dept Cairo 11517 Egypt Ajman Univ Elect Engn Dept Ajman U Arab Emirates

This paper presents a new parallel structured lookahead multidimensional sorting algorithm. Our algorithm can be based on any sequential sorting algorithm. The amount of parallelism can be controlled using several parameters such as the number of threads, word size, memory/processor communication overhead, and the dimension of the algorithm. The proposed technique is ideally suited for general purpose graphic processing units and shared-memory massively parallel processor systems. It ensures that data being processed exhibits temporal and spatial locality to maximize the utilization of processor cache. The algorithm achieves a speedup even when a single processor is used. A lookahead algorithm is also proposed to achieve even higher speedup. The performance of the proposed algorithm is verified numerically and experimentally.

关键词： Lookahead multicore execution parallel algorithms sorting algorithms

来源：评论

学校读者我要写书评

暂无评论

sorting a sequence of strong kings in a tournament

引用

INFORMATION PROCESSING LETTERS 2003年第6期87卷 317-320页

作者： Ho, TY Chang, JM Natl Taipei Coll Business Dept Informat Management New York NY 10021 USA Natl Taipei Coll Business Dept Publ Finance & Tax Adm New York NY 10021 USA

A king in a tournament is a player who beats any other player directly or indirectly. According to the existence of a king in every tournament, Wu and Sheng [Inform. Process. Lett. 79 (2001) 297-299] recently presented an algorithm for finding a sorted sequence of kings in a tournament of size n, i.e., a sequence of players u(1), u(2),..., u(n) such that u(i) --> u(i)+(1) (u(i) beats u(i+1)) and ui is a king in the sub-tournament induced by {u(i), u(i)+(1),..., u(n)} for each i = 1, 2,..., n - 1. With each pair u, v of players in a tournament, let b(u, v) denote the number of third players used for u to beat v indirectly. Then, a king u is called a strong king if the following condition is fulfilled: if v --> u then b(u, v) > b(v, u). In the sequel, we will show that the algorithm proposed by Wu and Sheng indeed generates a sorted sequence of strong kings, which is more restricted than the previous one. (C) 2003 Elsevier B.V. All rights reserved.

关键词： tournament king strong king sorting algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

An Efficient O(N) Comparison-Free sorting Algorithm

引用

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS 2017年第6期25卷 1930-1942页

作者： Abdel-Hafeez, Saleh Gordon-Ross, Ann Jordan Univ Sci & Technol Coll Comp & Informat Technol Irbid 22110 Jordan Univ Florida Dept Elect & Comp Engn Gainesville FL 32611 USA Univ Florida Natl Sci Fdn Ctr High Performance Reconfigurable Comp Gainesville FL 32611 USA

In this paper, we propose a novel sorting algorithm that sorts input data integer elements on-the-fly without any comparison operations between the data-comparison-free sorting. We present a complete hardware structure, associated timing diagrams, and a formal mathematical proof, which show an overall sorting time, in terms of clock cycles, that is linearly proportional to the number of inputs, giving a speed complexity on the order of O(N). Our hardware-based sorting algorithm precludes the need for SRAM-based memory or complex circuitry, such as pipelining structures, but rather uses simple registers to hold the binary elements and the elements' associated number of occurrences in the input set, and uses matrix-mapping operations to perform the sorting process. Thus, the total transistor count complexity is on the order of O(N). We evaluate an application-specified integrated circuit design of our sorting algorithm for a sample sorting of N = 1024 elements of size K = 10-bit using 90-nm Taiwan Semiconductor Manufacturing Company (TSMC) technology with a 1 V power supply. Results verify that our sorting requires approximately 4-6 mu s to sort the 1024 elements with a clock cycle time of 0.5 GHz, consumes 1.6 mW of power, and has a total transistor count of less than 750 000.

关键词： 90-nm TSMC comparison free Gigahertz clock cycle one-hot weight representation sorting algorithms SRAM speed complexity O(N)

来源：评论

学校读者我要写书评

暂无评论

sorting an array using the topological sort of a corresponding comparison graph

引用

THEORETICAL COMPUTER SCIENCE 2020年 845卷 76-97页

作者： Behera, Balaram D. Univ Calif Santa Cruz Comp Sci & Engn Dept Santa Cruz CA 95064 USA

The quest for efficient sorting is ongoing, and we will explore a graph-based stable sorting strategy, in particular employing comparison graphs. We use the topological sort to map the comparison graph to a linear domain, and we can manipulate our graph such that the resulting topological sort is the sorted array. By taking advantage of the many relations between Hamiltonian paths and topological sorts in comparison graphs, we design a Divide-and-Conquer algorithm that runs in the optimal O(n logn) time. In the process, we construct a new merge process for graphs with relevant invariant properties for our use. Furthermore, this method is more space-efficient than the famous MERGESORT since we modify our fixed graph only. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Topological sort sorting algorithms Comparison graphs

来源：评论

学校读者我要写书评

暂无评论

A novel sorting algorithm and its application to a gamma-ray telescope asynchronous data acquisition system

引用

NUCLEAR INSTRUMENTS & METHODS IN PHYSICS RESEARCH SECTION A-ACCELERATORS SPECTROMETERS DETECTORS AND ASSOCIATED EQUIPMENT 1997年第3期394卷 374-380页

作者： Colavita, A Mumolo, E Capello, G UNIV TRIESTE DEEII-34127 TRIESTEITALY IST NAZL FIS NUCL ICTPMICROPROC LABI-34100 TRIESTEITALY

In this paper we present a novel parallel sorting algorithm, which works through a cascade of elementary sorting units and leads to a scalable architecture. The algorithm's complexity is analyzed and compared with a classical parallel algorithm. It comes out that, although it may be less efficient than classical approaches, the proposed algorithm is highly suited for VLSI implementation for its simplicity and scalability. The paper describes the applications of such device to the asynchronous data acquisition for a gamma-ray telescope.

关键词： gamma-ray telescope sorting algorithms asynchronous data acquisition VLSI algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：