Search

It is well-known that signed permutations can be sorted in polynomial time, while sorting unsigned ones is an NP -hard problem. Although sorting signed permutations by reversals is an “easy” computational problem, the study of the average reversal distance is justified because it gives rise to interesting combinatorial questions and also because in applications related with genome similarity analysis, exact solutions for this problem have been used to design approximate algorithms for its unsigned NP -hard version. Thus, the average number of reversals needed to sort signed permutations represents a good control mechanism for the quality of approximate solutions for the unsigned case. This paper analyzes the average number of reversals needed to sort signed permutations by exploring combinatorial properties of structures related with signed permutations, such as breakpoint graphs, and provides a recurrence formula for this average number. The recurrence formula is built based on the analysis of the probability that two nodes of the breakpoint graph belong to the same alternating cycle among all the breakpoint graphs related with permutations of length n . Through this analysis it is possible to compute the average reversal distance for signed variations of the identity permutation. Also, lower and upper bounds of the average reversal distance for signed permutations are provided. Additionally, based on computational data, it is shown how these bounds can be used in order to propose concrete upper and lower bounds.

In this paper, we show how the theory of sorting networks can be applied to synthesize optimized general-purpose sorting libraries. Standard sorting libraries are often based on combinations of the classic Quicksort algorithm, with insertion sort applied as base case for small, fixed, numbers of inputs. Unrolling the code for the base case by ignoring loop conditions eliminates branching, resulting in code equivalent to a sorting network. By replacing it with faster sorting networks, we can improve the performance of these algorithms. We show that by considering the number of comparisons and swaps alone we are not able to predict any real advantage of this approach. However, significant speed-ups are obtained when taking advantage of instruction level parallelism and non-branching conditional assignment instructions, both of which are common in modern CPU architectures. Furthermore, a close control of how often registers have to be spilled to memory gives us a complete explanation of the performance of different sorting networks, allowing us to choose an optimal one for each particular architecture. Our experimental results show that using code synthesized from these efficient sorting networks as the base case for Quicksort libraries results in significant real-world speed-ups.

We present a new sorting network on 24 channels, which uses only 12 layers, improving the previously best known bound by one layer. By monotonicity, this also implies improved sorting networks for 23 channels. This result was obtained by combining techniques for generating prefixes of sorting networks with propositional encodings.

The combination of non-determinism and sorting is mostly associated with permutation sort, a sorting algorithm that is not very useful for sorting and has an awful running time. In this paper we look at the combination of non-determinism and sorting in a different light: given a sorting function, we apply it to a non-deterministic predicate to gain a function that enumerates permutations of the input list. We get to the bottom of necessary properties of the sorting algorithms and predicates in play as well as discuss variations of the modelled non-determinism. On top of that, we formulate and prove a theorem stating that no matter which sorting function we use, the corresponding permutation function enumerates all permutations of the input list. We use free theorems, which are derived from the type of a function alone, to prove the statement.

Sorting data is one of the main problems in computer science which studied vastly and used in several places. In several geometric problems, like problems on point sets or lines in the plane or Euclidean space with higher dimensions, the problem of sorting pairs of points based on the distance (between them is used. Using general sorting algorithms, sorting n 2) distances between n points can be done in O(n2 log n) time. Ofcourse, sorting (n2) independent numbers does not have a faster solution, but since we have dependency between numbers in this case, finding a faster algorithm or showing that the problem in this case has O(n2 log n) time complexity is interesting. In this paper, we try to answer this question.

We introduce a sorting scheme which is capable of efficiently sorting encrypted data without the secret key. The technique is obtained by focusing on the multiplicative depth of the sorting circuit alongside the more traditional metrics such as number of comparisons and number of iterations. The reduced depth allows much reduced noise growth and thereby makes it possible to select smaller parameter sizes in somewhat homomorphic encryption instantiations resulting in greater efficiency savings. We first consider a number of well known comparison based sorting algorithms as well as some sorting networks, and analyze their circuit implementations with respect to multiplicative depth. In what follows, we introduce a new ranking based sorting scheme and rigorously analyze the multiplicative depth complexity as $$\mathcal {O}\log N+\log \ell $$OlogN+logl, where N is the size of the array to be sorted and $$\ell $$l is the bit size of the array elements. Finally, we simulate our sorting scheme using a leveled/batched instantiation of a SWHE library. Our sorting scheme performs favorably over the analyzed classical sorting algorithms.

Sorting is a huge demand research area in computer science. One of the fundamental issues in computer science is how to order the data in lexicographic order. In practical application computing requires things to be in order. The performance of any computation depends on the sorting algorithms. A lot of sorting algorithm has been developed by many authors to enhance the performance in terms of complexity analysis, and most of author analysis the time complexity and auxiliary space complexity of the sorting algorithms but the total space complexity taken by the algorithms not evaluated yet. The total space complexity contains the primary and secondary memory required to store input and output data, memory required to hold the code and working space. The goal of this paper is to test the various existing sorting algorithms and to evaluate the total space complexity of various sorting algorithms on a standard dataset. Sorting algorithms are evaluated on four cases of standard dataset. The four cases of the dataset are random with repeated data, reverse sorted with repeated data, sorted with repeated data, and nearly sorted with repeated data, and we measure the performance of each sorting algorithm in each case.

Constraint based sorting is considered to be one of the fundamental topics of discussion in computer science. Even though a large number of sorting algorithms have already been proposed and verified, but still new algorithms are being developed with respect to emerging problem statements. As sorting is the common operation of many algorithms, so efficient sorting makes easy searching, arranging and locating the information. This paper introduces a novel in-place sorting algorithm which works under the restriction of the number of movements. The restriction of movement is element wise i.e. there is a constraint on the number of movements for a particular element. The proposed algorithm is useful when cost of moving each element is not same and we have to sort the list keeping in mind that elements with higher movement cost should be swapped lesser number of times. In this paper, the algorithm has been presented with time complexity, space complexity analysis and experimental results.

We consider the combinatorial problem of sorting a permutation using a minimum number of rearrangement events, which finds application in the estimation of evolutionary distance between species. Many variants of this problem, which we generically refer to as the rearrangement sorting problem, have been tackled in the literature, and for most of them, the best known algorithms are approximations or heuristics. In this article, we present a tool, called GRAAu , to aid in the evaluation of the results produced by these algorithms. To illustrate its application, we use GRAAu to evaluate the results of four approximation algorithms regarding two variants of the rearrangement sorting problem: the problem of sorting by prefix reversals and the problem of sorting by prefix transpositions. As a result, we show that the approximation ratios of three algorithms are tight and conjecture that the approximation ratio of the remaining one is also tight.

The complexity of multi-objective evolutionary algorithms based on the non-dominated principles mainly depends on finding non-dominated fronts. In order to reduce complexity and improve construction efficiency, this paper introduces a non-dominated set construction algorithm based on Two Dimensional Sequence (TSNS). When the non-dominated set closes to the Pareto optimal front, it always maintains one dimension by ascending order while the other dimension by descending order. In order to verify the effectiveness of the proposed algorithm, we integrate the algorithm into GA, DE, PSO, then we tested and compared it with classical benchmark functions. The experimental results indicate that the proposed algorithm performs better than NSGA-II in terms of the quality of solutions and the speed of convergence.

Nowadays the tasks of computations speed-up and/or their optimization are actual. Among the approaches on how to solve these tasks, a method applying approaches of parallelization and asynchronization to a sorting algorithm is considered in the paper. The sorting methods are ones of elementary methods and they are used in a huge amount of different applications. In the paper, we offer a method of an array sorting that based on a division into a set of independent adjacent pairs of numbers and their parallel and asynchronous comparison. And this one distinguishes the offered method from the traditional sorting algorithms (like quick sorting, merge sorting, insertion sorting and others). The algorithm is implemented with the use of Petri nets, like the most suitable tool for an asynchronous systems description.

Currently the tasks of computations speed-up and/or their optimization are actual ones. Among the ways to solve these tasks is a method of parallelization and asynchroniza-tion of a sorting algorithm, which is considered in the article. We offer a sorting method that is based on the principle of dividing an array into a set of independent pairs of numbers and their parallel and asynchronous comparison, which distinguishes the offered method from the traditional sorting algorithms (like quick sorting, merge sorting, insertion sorting and others). The algorithm is realized with the use of Petri nets as the most suitable tool for describing asynchronous systems. Examples of its work are given. The performance of the algorithm is evaluated for the best and the worst cases. In the best case the algorithm is executed for 2 or 3 conditional tacks depending on an array partition into the pairs of adjacent elements. In the worst case –for n or 3n/2, where n is the number of elements. Parallelization and asynchronization principles, used during the algorithm construction, can also be used for different algorithms.

In this paper the different sorting algorithms execution time has been examined with different number of elements. Through this experimental result concluded that the algorithm which is working best way. The analysis and execution time has been analyzed and tabulated with the help of Microsoft Excel. The sorting problem has attracted a great deal of research, perhaps due to the complexity of solving it efficiently despite its simple, familiar statement. Sorting algorithms are prevalent in introductory computer science classes, where the abundance of algorithms for the problem provides a gentle introduction to a variety of core algorithm concepts. The main objective of this paper is finding the best sorting algorithm based upon the time complexity.

Data sorting is an important procedure with many applications in computer science. Thus, various methods that improve the performance of sorting algorithms have been published. Most existing algorithms mainly aim to achieve a faster processing time for sorting and require memory space to load all data in the set. Such designs can be a burden for small devices that have relatively insufficient resources. This paper proposes a new sorting method for mobile devices that finds the minimum and maximum values by reading only a portion of the data into memory, unlike existing methods that read all data into memory. This phase is repeated as often as necessary in accordance with the size of the data set. The min/max values that are determined are written at the start and end point of the data set in storage. As the process is repeated, sorting can take place even if a small amount of memory is available, such as when using a mobile device. In order to evaluate the proposed method, we implemented a prototype for a music recommendation system, and we conducted comparative experiments with representative sorting methods. The results indicate that the proposed method consumed significantly less memory, and we confirmed the effectiveness and potentiality of the proposed method.