基于中项平衡划分的快速排序算法

阐述了Hoare的快速排序算法及其缺点,在此快速排序算法的基础上利用找中项的线性选择算法改进了快速排序算法,使得快速排序在最坏情况下的性能达到最优。     

任意类型的分类数据的快速排序

快速排序在数据部分相等或有序时,时间复杂度最坏为O（n2）。针对于任意类型的分类数据的排序,文章在快速排序的基础上,提出一种新的排序算法,具有快速排序算法的简洁性,但是不使用递归算法,时间复杂度为O（n）,空间复杂度为O（1）。通过理论分析和实验表明,该算法的性能明显优于其它排序算法,特别适合于数据量大的场合。     

一种三路划分快速排序的改进算法

快速排序是一种经典的排序算法,它的平均性能非常突出。针对快速排序在某些特殊情况下(如数据已有序或重复数据较多时)效率较低的问题进行了研究,对三路快速排序进行改进,使快速排序在特殊情况下也能保持较好的效率。通过大量的数据测试发现,该算法在最好情况下其性能在几个数量级上优于普通快速排序,在最坏情况下,其性能较普通快速排序无明显差距。改进后的三路快速排序是一种通用高效的排序算法,因此在某些情况下选用、该算法会获得更好的效率。     

基于流水光总线阵列上的快速可扩展并行排序算法

在Y．Pan提出的基于流水光总线阵列模型(LARPBS)上使用N个处理器对N个元素进行排序在最好情况下以O(logN)时间，最坏情况下以O(N)时间完成的并行排序算法的基础上，提出了一种LARPBS模型上的可扩展的快速并行排序算法，对N个元素进行排序，使用p(1≤P≤N)个处理器在最好情况下以O(NlogN／p)时间，最坏情况下以O(N^2／p)时间完成排序。另外还提出了一种LARPBS模型上改进的快速高效并行排序算法，该算法对N个元素进行排序使用N个处理器在最好情况下以O(log√N)时间、最坏情况下以O(√N)时间完成排序。     

位排序--一种快速排序法

众所周知,排序速度的快慢,取决于排序算法的时间复杂度和空间复杂度。因而,排序算法设计的主导思想,就是要千方百计降低算法的时间复杂度和空间复杂度。虽然计算机硬件的运算速度越来越快,但排序算法的研究仍是算法理论中的一个重要课题。已有的排序算法很多,在所有基于“记录关键字之间比较”的排序方法中,快速排序(quick sort)是平均时间性能最好的一种方法,平均时间为O（n*log n)。但是在最坏情况下,时间复杂度却很高,为O(n^2)。     

二次分级连接排序算法

近年来，人们提出了不少排序运算量为Ｏ（Ｎ）的新算法。但对这些算法分析研究的结果表明，普遍存在着以下两点不足：（１）附加空间开销大；（２）排序效率过分依赖于键值的均匀分布。对此，本文提出了一个排序算法－二次分级连接排序法。该方法保证排序时间在最坏下为Ｏ（Ｎ）的基础上，仅需附加空间开销Ｎ＋√△Ｍ＋２。这里，△Ｍ为键值的变化范围。     

快速排序性能分析

在决策树计算模型下,任何一个基于比较来确定元素相对位置的排序算法需要的计算时间是Ω(nlog2n).如果能设计一个需要O(nlog2n)时间的排序算法,在渐近的意义上,这个排序算法就是最优的.由C.A.R.Hoare发明的快速排序算法它在平均情况下需要O(nlog2n)时间.本文就该算法在最好情况下、最坏情况下、平均情况下的性能进行分析.     

分组排序算法

提出了分组排序算法,详细分析了算法的原理及其时间与空间复杂度,得出了在最坏情况下的时间复杂度是θ（mn）;最好情况和平均情况下的时间复杂度均是θ（nlog（n/m^k））;在最坏情况下的空间复杂度是O（mn-m²＋m）;最好情况和平均情况下的空间复杂度均是O（m^klog（n/m^k））;并用多组随机数据与效率较高的快速算法进行仿真对比实验,试验结果说明了文中结论的正确性。这一结果,将有助于进一步设计高效的海量数据分析方法。     

按字节桶分配链接排序法

本文准备提出一种谓之按字节桶分配链接的新序方法，给出排序算法，流科和用Ｃ语言编写程序进行实验的结果。算法分析和实验结果都表明，该排序方法的时间复杂性Ｏ且与数据的分布情况，附加存储开销为（Ｎ＋５１２）ε。该排序方法不仅速度上明显快于快速排序法，而且在非均匀分布数据的民政部下了明显快于桶排序法。     

分“档”快速排序算法研究

文章在文献［１］的基础上,提出了一种由分“档”、整体置换和局部快速排序所组成的新排序算法——分“档”快速排序法。算法分析和实验结果都表明：在待排序数据均匀分布或正态分布的情况下,分“档”快速排序算法的时间复杂度可以达到Ｏ（ｎ）,而附加存储空间开销却仅仅为［（ｎ＋１）／２］,同时排序速度明显优于Ｑｕｉｃｋ Ｓｏｒｔ［２］、快速分组排序［５］、分“档”统计插入排序［１］和 Ｐｒｏｐｏｒｔｉｏｎ 　Ｓｐｌｉｔ Ｓｏｒｔ［４］等算法。     

CUDA‐quicksort: an improved GPU‐based implementation of quicksort

Sorting is a very important task in computer science and becomes a critical operation for programs making heavy use of sorting algorithms. General‐purpose computing has been successfully used on Graphics Processing Units (GPUs) to parallelize some sorting algorithms. Two GPU‐based implementations of the quicksort were presented in literature: the GPU‐quicksort, a compute‐unified device architecture (CUDA) iterative implementation, and the CUDA dynamic parallel (CDP) quicksort, a recursive implementation provided by NVIDIA Corporation. We propose CUDA‐quicksort an iterative GPU‐based implementation of the sorting algorithm. CUDA‐quicksort has been designed starting from GPU‐quicksort. Unlike GPU‐quicksort, it uses atomic primitives to perform inter‐block communications while ensuring an optimized access to the GPU memory. Experiments performed on six sorting benchmark distributions show that CUDA‐quicksort is up to four times faster than GPU‐quicksort and up to three times faster than CDP‐quicksort. An in‐depth analysis of the performance between CUDA‐quicksort and GPU‐quicksort shows that the main improvement is related to the optimized GPU memory access rather than to the use of atomic primitives. Moreover, in order to assess the advantages of using the CUDA dynamic parallelism, we implemented a recursive version of the CUDA‐quicksort. Experimental results show that CUDA‐quicksort is faster than the CDP‐quicksort provided by NVIDIA, with better performance achieved using the iterative implementation. Copyright © 2015 John Wiley & Sons, Ltd.     

External quicksort

An external sorting algorithm based on quicksort is presented. The file to be sorted is kept on a disk and only those blocks are fetched into the main memory which are currently needed. At each time, a block is kept in the main memory, if the expected space-time cost of holding it until its next use is smaller than the expected space-time cost of removing it and fetching it again. The efficiency of the algorithm is tested through simulation experiments and the results are compared to those achieved with mergesort in a corresponding environment. The total execution time and the main memory space-time integral are used for measuring the performance.

When equal block sizes are used, external quicksort results in a much smaller average space requirement than mergesort. On the other hand, mergesort is somewhat faster than external quicksort. The main memory space-time integral of quicksort is always considerably smaller than that of mergesort. External quicksort is less sensitive to the block size and to the file size. With faster disks, the performance of external quicksort improves faster than that of mergesort. The relative difference of the algorithms is independent of the file size.

The external quicksort is also analytically compared to some previous external versions of quicksort. It is shown to be satisfied with less space and fewer block fetches than the others.     

Parallel sorting algorithms for tightly coupled multiprocessors

We present three parallel sorting algorithms suitable for implementation on tightly coupled multiprocessors and compare their performance on the Denelcor HEP. Two of the algorithms implemented—parallel Shellsort and quickmerge—are new. Shellsort is amenable to parallelization; however, since Shellsort has higher complexity than quicksort, parallel Shellsort is inferior to parallel quicksort. A second new parallel algorithm, called quickmerge, is based upon both quicksort and mergesort. Our implementation of quickmerge achieves significantly higher speedup than occur implementation of parallel quicksort.     

Comparison of external sorting and internal sorting in virtual memory

To compare the performance of external sorting and internal sorting in virtual memory, (external) mergesort and (internal) quicksort are performed in corresponding environments. Quicksort is run using a virtual memory with fetch on demand and working set replacement policy. Mergesort uses sublists presorted by replacement selection, double buffering for input and output, and two disks. The performance is measured by main memory space allocation, execution time, and main memory space-time integral.To perform well, quicksort is satisfied with a smaller space allocation than mergesort, and it behaves more consistently with respect to space allocation. Mergesort needs far less execution time than quicksort, mainly because of its efficient overlapping of file handling and processor time. With respect to the space-time integral, quicksort outperforms mergesort only when small files (less than 1000 records) are sorted. With large files, mergesort is better, and the relative difference increases with increasing file size. The optimal page size and window size for quicksort are smaller than those typical to existing virtual memory systems, and they tend to decrease with increasing file size.     

分割方式的多线程快速排序算法

基于Java平台先对经典快速排序的改进方法作了介绍,通过测试得出了一个合适的经验阈值,改善了快速排序在小数据量情况下的低效问题。然后对快速排序作了多线程优化,并进行了单、多线程的对比测试,结果显示在多核主机上能有几倍的速度提升。最后对多线程快速排序算法进行了理论分析,得出了该算法速度的理论上限。     

Transitional behaviors of the average cost of quicksort with median-of-(2t + 1)

A fine analysis is given of the transitional behavior of the average cost of quicksort with median-of-three. Asymptotic formulae are derived for the stepwise improvement of the average cost of quicksort when iterating median-of-threek rounds for all possible values ofk. The methods used are general enough to apply to quicksort with median-of-(2t + 1) and to explain in a precise manner the transitional behaviors of the average cost from insertion sort to quicksort proper. Our results also imply nontrivial bounds on the expected height, “saturation level,” and width in a random locally balanced binary search tree. This work was done while the first author was at the Institute of Mathematics, Academia Sinica, Taipei, Taiwan. Online publication September 22, 2000.     

Acceleration of sweep-line technique by employing smart quicksort

Quicksort is usually the best practical choice for sorting because it is, on average, remarkably efficient. Unfortunately, this popular algorithm has a significant drawback: the slowest performance is obtained in the simplest cases when input data are already initially sorted or only a slight perturbation occurs. In this paper, we propose a combination of quicksort and a new algorithm, which shows excellent time performance in sorting such crucial data arrays, and which is not much slower than quicksort in random cases. Our work was inspired by problems met when sorting polygon vertices in the sweep-line algorithms of computational geometry and, therefore, we have named the new algorithm ‘vertex sort’. It splits the input array into three sub-arrays. Two of them are already sorted, and the third one is handled iteratively. A simple test decides whether to continue recursively with vertex sort or to employ quicksort in the second iteration. In this way, we achieve a situation where the worst case time complexity does not exceed the running times of quicksort, but the simplest cases are handled much faster (in linear time) than random cases. We have named the combined algorithm ‘smart quicksort’ because of this desired property. In the last part of the paper, we prove its efficiency by employing it in a well-known sweep-line-based polygon triangulation algorithm.     

Sorting with near linear speed-up on tightly coupled multiprocessors

A new parallel sorting algorithm, called parsort, suitable for implementation on tightly coupled multiprocessors is presented. The algorithm is based upon quicksort and two-way merging. An asynchronous parallel partitioning algorithm is used to distribute work evenly during merging to ensure a good load balance amongst processors, which is crucial if we are to achieve high efficiency. The implementation of this parallel sorting algorithm exhibits theoretical and measured near linear speed-up when compared to sequential quicksort. This is illustrated by the results of experiments carried out on the Sequent Balance 8000 multiprocessor.     

Connecting Design with Code

Jon Bentley wrote his thesis on divide-and-conquer algorithms and came to greatly admire C.A.R. Hoare's original quicksort algorithm. Yet for years, Bentley "tiptoed around its innermost loop" because he didn't understand it (Beautiful Code, O'Reilly, 2007). It was only after he implemented his own quicksort based on an elegant partitioning scheme for programming Pearls (Addison-Wesley, 1999) that he truly understood the reason for that inner loop. He also trimmed the original bulkier algorithm to a mere dozen tight lines of code. Code clutter and unnecessary complexity can obscure a design. However, connecting design decisions to code won't happen unless developers embrace the practice of writing code as if expressing design intent matters.     

On program synthesis knowledge

This paper presents a body of program synthesis knowledge dealing with array operations, space reutilization, the divide-and-conquer paradigm, conversion from recursive paradigms to iterative paradigms, and ordered set enumerations. Such knowledge can be used for the synthesis of efficient and in-place sorts including quicksort, mergesort, sinking sort, and bubble sort, as well as other ordered set operations such as set union, element removal, and element addition. The knowledge is explicated to a level of detail such that it is possible to codify this knowledge as a set of program synthesis rules for use by a computer-based synthesis system. The use and content of this set of programming rules is illustrated by the methodical synthesis of bubble sort, sinking sort, quicksort, and mergesort.