Search

Sorting algorithms are the class of algorithms that result in the ordered arrangement of a list of given elements. The arrangement can be in ascending or descending order based on the requirement given. Time complexity, space complexity and optimality are used to assess the algorithms. In this paper, a new sorting algorithm called Matrix sort is introduced. This algorithm aims to sort the elements of a matrix without disturbing the matrix structure. It has a time complexity of O(n p nlog p n) and hence takes lesser time than existing O(n 2 ) algorithms. A pseudocode for the algorithm is provided and the best, average and worst case time complexities are derived.

Generally, there is no sorting algorithm much faster than O(nlogn). The quicksort has a best performance O(nlogn) in best and average-case, and in worst-case. This paper suggests virtual radix counting bucket sort such that counting the frequency of numbers in each radix digit, and moves the arbitrary number to proper virtual bucket in the array, and divides the array into radix digit numbers virtually. Also, this algorithm moves the data to proper location within an array for using the minimum auxiliary memory. This algorithm performs k-times such that the number of k digits in given data and the time complexity is O(n). Therefore, this algorithm has a O(kn) time complexity.

Among comparison sorts, no algorithm excels a current set lower bound of O(nlogn) in operation. Quicksort, the fastest of its kind, has a complexity of O(nlogn) at its best and on average and at worst. This paper thus presents two methods: first is an O(n+k) simple counting sort which operates much more speedily than an O(n+k), (k=maximum value) counting sort, and second is an O(ln) radix counting sort which counts the frequency of numbers in the digit l of a data and saves it in a corresponding virtual bucket in an array, only to virtually divide the array into radix digit numbers. For the 6 experimental data, the proposed algorithm makes O(nlogn) or of Quicksort simple into O(n+k) or O(ln). After all, the proposed sorting algorithm has proved to be much faster than the counting sort and Quicksort.

Data Structure is considered as one of the fundamental research area in computer science. Sorting is a foremost issue in data structure which arranges the data in ascending or descending order. Though several sorting algorithms are available, it is necessary to select the best sorting algorithm depends on the situation. These sorting technique are frequently used in a large variety of important applications. This paper presents a new sorting technique, "Mean Sort" which has exclusively been developed to sort the number of elements and also makes the data analysis and data processing very easy by taking the advantage of a computed mean. Like merge sort or quick sort, this algorithm works by single a divide-and-conquer strategy to divide a single unsorted array into two smaller sub-arrays. It uses mean to divide and sort them and time complexity is O(n∗logn). This algorithm is described using C++. The proposed algorithm is analyzed using asymptotic analysis and also using machine-running time and compared with their basic sorting algorithms.

We consider the problem of sorting a permutation using a network of data structures as introduced by Knuth and Tarjan. In general the model as considered previously was restricted to networks that are directed acyclic graphs (DAGs) of stacks and/or queues. In this paper we study the question of which are the smallest general graphs that can sort an arbitrary permutation and what is their efficiency. We show that certain two-node graphs can sort in time @Q(n^2) and no simpler graph can sort all permutations. We then show that certain three-node graphs sort in time @W(n^3^/^2), and that there exist graphs of k nodes which can sort in time @Q(nlog"kn), which is optimal.

Quick sort is a sorting algorithm whose worst case running time is θ(n2 ) on an input array of n numbers. It is the best practical for sorting because it has the advantage of sorting in place. Problem statement: Behavior of quick sort is complex, we proposed in-place 2m threads parallel heap sort algorithm which had advantage in sorting in place and had better performance than classical sequential quick sort in running time. Approach: The algorithm consisted of several stages, in first stage; it splits input data into two partitions, next stages it did the same partitioning for prior stage which had been spitted until 2 m partitions was reached equal to the number of available processors, finally it used heap sort to sort respectively ordered of non internally sorted partitions in parallel. Results: Results showed the speed of algorithm about double speed of classical Quick sort for a large input size. The number of comparisons needed was reduced significantly. Conclusion: In this study we had been proposed a sorting algorithm that uses less number of comparisons with respect to original quick sort that in turn requires less running time to sort the same input data.

Rainbow Sort is an unconventional method for sorting, which is based on the physical concepts of refraction and dispersion. It is inspired by the observation that light that traverses a prism is sorted by wavelength. At first sight this "rainbow effect" that appears in nature has nothing to do with a computation in the classical sense, still it can be used to design a sorting method that has the potential of running in ? (n) with a space complexity of ? (n), where n denotes the number of elements that are sorted. In Section 1, some upper and lower bounds for sorting are presented in order to provide a basis for comparisons. In Section 2, the physical background is outlined, the setup and the algorithm are presented and a lower bound for Rainbow Sort of ? (n) is derived. In Section 3, we describe essential difficulties that arise when Rainbow Sort is implemented. Particularly, restrictions that apply due to the Heisenberg uncertainty principle have to be considered. Furthermore, we sketch a possible implementation that leads to a running time of O(n+m), where m is the maximum key value, i.e., we assume that there are integer keys between 0 and m. Section 4 concludes with a summary of the complexity and some remarks on open questions, particularly on the treatment of duplicates and the preservation of references from the keys to records that contain the actual data. In Appendix A, a simulator is introduced that can be used to visualise Rainbow Sort.

We analyze the Shell Sort algorithm under the usual random permutation model. Using empirical distribution functions, we recover Louchard's result that the running time of the 1-stage of.2; 1/-Shell Sort has a limiting distribution given by the area under the absolute Brownian bridge. The analysis extends to .h; 1/- Shell Sort where we find a limiting distribution given by the sum of areas under correlated absolute Brownian bridges. A variation of.h; 1/-Shell Sort which is slightly more efficient is presented and its asymptotic behavior analyzed. 1. Introduction. Shell Sort is an algorithm that generalizes the method of sorting by insertion. It is essentially several stages of insertion sort. The algorithm was proposed in Shell (1959). The method received considerable attention over the past quarter of a century after Knuth's 1973 book popularized it (Knuth, 1973). From a practical point of view, the interest in Shell Sort stems from the fact that it is a rather practicable method of in situ sorting with little overhead and can be implemented with ease. From a theoretical standpoint, the interest is that insertion sort has an average of 2.n 2 / running time to sort n random keys, whereas the appropriate choice of the parameters of the stages of Shell Sort can bring down the order of magnitude. For instance, by a certain choice of the structure of the stages, a 2-stage Shell Sort can sort in O.n 5=3 / average running time. Ultimately, an optimized choice of the parameter can come close to the information-theoretic lower bound of O.n ln n/ average case. The analysis of Shell Sort has stood as a formidable challenge. Most research on Shell Sort has gone in the direction of making good choices for the parameters of the stages to obtain good worst-case behavior (see, for example, the review paper of Sedgewick (1996)). We propose here to take the research along a different axis and to analyze the stochastic structure of the algorithm. We rederive the limit result of Louchard (1986) for .2; 1/-Shell Sort, which he proved by essentially combinatoric arguments, and we generalize the approach to the analysis of .h; 1/-Shell Sort. The integrated alsolute value of the Brownian bridge appears in the limiting distributions; the moments of the distribution of this random variable were found by Shepp (1982), and Johnson and Killeen (1983) gave an explicit characterization of the distribution function.

String sorting or variable-length key sorting has lagged in performance on the GPU even as the fixed-length key sorting has improved dramatically. Radix sorting is the fastest on the GPUs. In this paper, we present a fast and efficient string sort on the GPU that is built on the available radix sort. Our method sorts strings from left to right in steps, moving only indexes and small prefixes for efficiency. We reduce the number of sort steps by adaptively consuming maximum string bytes based on the number of segments in each step. Performance is improved by using Thrust primitives for most steps and by removing singleton segments from consideration. Over 70% of the string sort time is spent on Thrust primitives. This provides high performance along with high adaptability to future GPUs. We achieve speed of up to 10 over current GPU methods, especially on large datasets. We also scale to much larger input sizes. We present results on easy and difficult strings defined using their after-sort tie lengths.

Various methods, such as address-calculation sorts, distribution counting sorts, radix sorts, and bucket sorts, use the values of the numbers being sorted to increase efficiency but do so at the expense of requiring additional storage space. In this paper, a specific implementation of bucket sort is presented whose primary advantanges are that (i) linear average-time performance is achieved with an additional amount of storage equal to any fraction of the number of elements being sorted and (ii) no linked-list data structures are used (all sorting is done with arrays). Analytical and empirical results show the trade-off between the additional storage space used and the improved computational efficiency obtained. Computer simulations show that for lists containing 1,000 to 30,000 uniformly distributed positive integers, the sort developed here is faster than both Quicksort and a standard implementation of bucket sort. Furthermore, the running time increases with size at a slower rate.

This paper presents a new sort algorithm, self-indexed sort (SIS) , on an approach of non compare-based sorting. Results on time complexity O ( n ) and space complexity O(n+m) are achieved, where n is the size of data being sorted and m is the size of the sorting space.Two versions of SIS sort algorithm are implemented with one for the sort of structured records and the other for pure data file. The performance of SIS sort is tested and analysed under various conditions.

In this paper, we propose a constant time sorting algorithm on an array composed of comparators and single-pole-double-throw switches, which is far more feasible than other constant time sorting algorithms [21]-[23]. Our results shown that the algorithm uses time T = Θ(1) and area A = O ( N 3 ). This nearly matches the AT 2 = Ω( N 2 log 2 N ) lower bound for sorting in the VLSI model.

Sorting is technique by which elements are arranged in a particular order following some characteristic or law [1]. In this paper we presented an algorithm called as Relative Concatenate Sort, which is based on the idea of Selection Sort, but it divides the list into two. After dividing the list it takes the average of both halves of the list. Comparing this average with elements it sorts both arrays and then put these arrays together to get the final sorted list.

We design a high-performance parallel merge sort for highly parallel systems. Our merge sort is designed to use more register communication (not shared memory), and does not suffer from over-segmentation as opposed to previous comparison based sorts. Using these techniques we are able to achieve a sorting rate of 250 MKeys/sec, which is about 2.5 times faster than Thrust merge sort performance, and 70% faster than non-stable state-of-the-art GPU merge sorts. Building on this sorting algorithm, we develop a scheme for sorting variable-length key/value pairs, with a special emphasis on string keys. Sorting non-uniform, unaligned data such as strings is a fundamental step in a variety of algorithms, yet it has received comparatively little attention. To our knowledge, our system is the first published description of an efficient string sort for GPUs. We are able to sort strings at a rate of 70 MStrings/s on an NVidia GTX 580 on one dataset, and up to 1.25 GB/s on another dataset.

We introduce an algorithm to determine when a sorting operation, such as stack-sort or bubble-sort, outputs a given pattern. The algorithm provides a new proof of the description of West-2-stack-sortable permutations, that is permutations that are completely sorted when passed twice through a stack, in terms of patterns. We also solve the long-standing problem of describing West-3-stack-sortable permutations. This requires a new type of generalized permutation pattern we call a decorated pattern., On introduit un algorithme qui détermine quand un opérateur de tri (tels que le tri par une pile, ou le tri-bulle) produit un motif donnè en sortie. Cet algorithme fournit une nouvelle preuve de la caractérisation des permutations 2-triables au sens de West (c'est-à-dire des permutations qui sont triées complètement par deux passages dans une pile) par des motifs interdits. On résout aussi le problème longtemps ouvert de la caractérisation des permutations 3-triables au sens de West. Ceci demande de définir un nouveau type de motifs généralisés, appelè motif décoré.

In this paper we present a sorting algorithm for natural numbers, which uses the methodology of indexing of the array and insert that number into proper index of the array without performing any element comparisons and swapping. This algorithm efficiently to give a much better performance than the existing sorting algorithms of the O(n2) class, for large array size with same length of digits of input data.

The challenge of direct parameterized suffix sorting (p-suffix sorting) for a parameterized string (p-string) is the dynamic nature of parameterized suffixes (p-suffixes). In this work, we propose transformative approaches to direct p-suffix sorting by generating and sorting lexicographically numeric fingerprints and arithmetic codes that correspond to individual p-suffixes. Our algorithm to p-suffix sort via fingerprints is the first theoretical linear time algorithm for p-suffix sorting for non-binary parameter alphabets, which assumes that each code is represented by a practical integer. We eliminate the key problems of fingerprints by introducing an algorithm that exploits the ordering of arithmetic codes to sort p-suffixes in linear time on average.

You're teaching elementary sorting techniques, and you would like your students to do a programming assignment that tests their understanding of the ideas. But all of the code for elementary sorting techniques are in the textbook, easily found on the Web, etc. We suggest the use of two "Double Sorting" techniques whose solution is not standardly available, are fairly straight-forward to code, and offer speed improvements over the "straight" sorts. Double Sorting, the idea of processing two chosen elements simultaneously, applies to both Insertion Sort and Selection Sort, with speedups of 33% and 25%, hence are good enough to justify coding, but not good enough to be in Web collections. Code for this can be written in as little as a dozen lines of C++/Java code, and is easily within the reach of introductory students who understand the basic algorithms. In addition, the ideas used for double sorting are natural first steps in understanding how the N2 sorts can be improved towards the N log N sorts that they will study later. For more advanced students, these double sorts also generate good exercises in the analysis of algorithms.

In a bucket sorting algorithm, the key to increase bucket sorting efficiency is how to uniformly distribute records into each "bucket". The data collected from empirical studies usually follow a certain probability distribution in a certain interval. To sort this kind of data, this paper proposed an innovative method through constructing a hash function based on its probability density function. Then n records can be allocated into n buckets uniformly according to the value of their key, which enables the sorting time of the proposed bucket sorting algorithm to reach O(n) under any circumstance.

A parallel sorting algorithm using cooperating heaps in a linear array of processors is presented. It can sort a sequence whose length is much larger than the number of processors. Because the output begins one step after all the items have been input, sorting n items requires 2n + 1 steps. Two independent modifications of the algorithm are possible; one tries to reduce the number of processors used, and the other can sort more items on the same array.

This chapter covers how to search for specific values within Interactive Data Language (IDL) arrays and sort the values of IDL arrays into increasing or decreasing order. The following IDL procedures are discussed: (1) WHERE function: COUNT, COMPLEMENT, and NCOMPLEMENT keywords, (2) SORT function, and (3) VALUE_LOCATE function. A common programming task is to find the elements of an array that satisfy a particular condition. The WHERE function is an essential tool for doing fast conditional array operations in IDL. Most operations that could be done in a Fortran-like style using FOR loops and IF statements can be done faster and more elegantly in IDL using WHERE. WHERE applies the logical test to every element of the array. The built-in IDL function to sort the elements of an array is SORT. In a manner similar to WHERE, SORT returns a list of the indices of the array sorted in the proper order, not the elements themselves.

Sorting is one of the most common and important computing operations. In analyzing and comparing sorting algorithms, we consider their execution times, as indicated by the number of operations they execute as they sort n elements. The simplest algorithms have times that grow approximately as n 2 , while more complex algorithms offer times that grow approximately as n log n . This paper pursues a contrary goal: a sorting algorithm whose time grows more quickly than that of the well-known algorithms. The paper exhibits and analyzes such an algorithm.

Two ways to sort externally are Multi-Line Merging Sort and Bucket Sort, both with two passes. The Bucket Sort burdens the CPU less and is more efficient, while its usage is restricted heavily by the High-Bit scheme that distributes records into subfiles: the keys have to be integers; the sizes of subfiles may vary too much; the number of subfiles cannot be chosen freely. Based on statistical theory, this paper presents a sample-seperators scheme to broaden the ussage of bucket sort algorithm. A brief discussion on the convergance of sample-seperator estimation is given and the probability to avoid memory overflow is calculated. This scheme enables the bucket sort algorithm to be applied in the SheenkSort system to win the 2003 PennySort (the Indy category) competition.

A top-down approach is presented for the derivation of, and corresponding exposition of sorting algorithms. Work done in automatic program synthesis has produced interesting results about sorting algorithms which suggest this approach. In particular insertion sort and selection sort are seen to be instances of merge sort and Quick sort, and sinking sort and bubble sort are presented as in-place versions of insertion sort and selection sort. This top-down approach is offered as an alternative way of deriving and ultimately teaching about sorting algorithms.

This paper presents two sorting algorithms on the uniform ladder (a new storage device based on charged coupled devices, or magnetic bubbles implementation, proposed by Chen et al.). It is assumed that control and comparison timings are negligible when compared to the relatively slow bubble movements. The first algorithm (Algorithm 1) enables the sorting process on a single ladder to be completely embedded in the input/output time (whereas Chen's algorithm (SLISO) has a 20 percent unoverlapped sorting time in the load-sort-unload process). When one ladder cannot accommodate all the input records and two or more ladders are needed, Algorithm 2 attains a negligible unoverlapped sorting time (which can be removed with a minor modification in the system hardware and hence in Algorithm 2). In comparison, Algorithm 2 obviates the need for explicit merging of the ladders, which is required in Chen's algorithm (MLISO). This implies that unlike the MLISO scheme, ladders are not tied up for merging, and can be recycled once their contents are outputted. Therefore, in a real processing environment, the number of ladders required by Algorithm 2 may even be less than the theoretical minimum which can be attained by the MLISO scheme.

We develop models of secondary storage to evaluate external sorting and use them to analyze the average I/O access time of mergesort and tag sort on files with uniform key distribution. The k-way mergesort takes [log k R] merge passes to sort a file with R initial sorted runs. Choosing k as large as possible reduces the number of merge passes, but we show that under the assumptions of our models, the I/O access time of the merge phase in mergesort increases as a function of k. For large files with short keys, tag sort provides a promising alternative to mergesort. We analyze the I/O access time of tag sort with a ``sequential scan'' distribution method. We show that for large files tag sort takes asymptotically less I/O time than mergesort.

This paper reports the development of a sorting algorithm, called a ‘pocket sort.’ It is primarily directed to sorting of character data. The algorithm is strictly of order O(n); sorting time is directly proportional to the number of data elements to be sorted. Further, through the use of pointer - linked list data structures, no internal movement of the records containing the sort field is required. The algorithm has been implemented in Turbo Pascal. Data are presented comparing this pocket sort to other sorting techniques.

By using anN-loop shift-register structure called a uniform ladder,N records can be sorted by a simplified adaptation of the odd-even transposition-sort algorithm to finish in (N + 1)/2 loop times (periods) using (N − 1) comparators. The sorting can be overlapped with input/output; the percentage of unoverlapped sorting times is less than 20% of the total time with a single ladder, less than 6% using two ladders, and is zero with a sufficient number of ladders.

The block sorting problem is the problem of minimizing the number of steps to sort a list of distinct items, where a sublist of items which are already in sorted order, called a block, can be moved in one step. We give an approximation algorithm for the block sorting problem with an approximation ratio of 2 and run time O(n2). The approximation algorithm is based on the related concept of block deletion. We show that finding an optimum block deletion sequence can be done in O(n2) time, even though block sorting is known to be NP-hard. Block sorting has importance in connection with optical character recognition (OCR) and is related to transposition sorting in computational biology.

One of the major fundamental issues of Computer Science is arrangement of elements in the database. The efficiency of the sorting algorithms is to optimize the importance of other sorting algorithms11. The optimality of these sorting algorithms is judged while calculating their time and space complexities12. The idea behind this paper is to modify the conventional Merge Sort Algorithm and to present a new method with reduced execution time. The newly proposed algorithm is faster than the conventional Merge Sort algorithm having a time complexity of O(n log2 n). The proposed algorithm has been tested, implemented, compared and the experimental results are promising.

This chapter presents an algorithm for sorting. A frequently occurring problem in combinatorial work is the sorting of an array. There are various criteria by which a person may evaluate the effectiveness of a sorting method, such as the average amount of labor (pairwise comparisons or displacements of position) required to sort an array of length n , the maximum amount of labor required by some sequence of length n , the amount of array storage required, the amount by which the method takes advantage of whatever order is already present in the input list, and elegance, compactness, universality, etc. No single sorting method optimizes all departments at once. The algorithm presented in the chapter is a good choice if just one general-purpose sort is to be available for combinatorial applications. It requires an average of cn log n operations, a maximum of cn log n operations, no array storage other than the input array, and it is extremely elegant, compact, and universal. The chapter discusses the Heapsort algorithm, which is divided into two phases: (1) the input array is transformed into a heap and (2) the heap is sorted into nondecreasing order.

When performing an external sort, an extra integer field added to the sort key can be used to count subsequences, and make the counts available at the beginning of each subsequence.