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.

An algorithm is basically term vital part of Operations Research Methodology. There are many algorithms related to sorting, basically it is the operation of logically arrangement of records or elements and it can be used for the numerically data or alphabetically data. Sorting operation implemented in the Data Structure to make efficient searching of elements. The Sorting Algorithm, having the swap, comparison and assignment operations related to the direct complexity of an algorithm. In proposed sorting algorithms we used strategy of selection of the elements i.e. we have the functions called as MinOddFunction(collect the minimum odd value of list) and MinEvenFunction(collect the minimum even valued from list), these functions collect the values from list and compare with each other and freeze it and so on till array is empty. This algorithm has the time complexity in the worst case is O(n^2), where n is the size of data being sorted. In this proposed paper, we will conclude the time complexity on the basis of number of iterations, comparisons, memory time and other factors.

This article considers the methods of sorting, i.e. placing the array of numbers, which are used in computer techniques today, according to the rule. Sorting is one of the most common principles of programming systems, while their application for various applied problems requires choosing an optimal sorting algorithm from a set of existing ones. The objective of the article is to analyze temporal characteristics of the selection process aimed at choosing the algorithm, which is the most suitable for a certain goal realization. Existing methods of sorting can be grouped into: sorting by insertion, sorting by selection, sorting by exchange. Existing methods are analyzed in terms of quantity indexes of exchanges, integrations and comparisons that define each algorithm at most. As a result, the total operating speed of each method was estimated; the advantages and disadvantages of each method were singled out. The results of analysis of well known sorting methods allow choosing the best method for software and hardware implementation from this point of view. The principal possibility of new solutions in the field of hardware implementation was shown in order to increase the level of parallelism and accelerate the sorting process, whereby the sorting method by exchange should be prerogative. After checking the known sorting methods for operating speed with the use of the constant volume array, the operation time of sorting programs was defined on the basis of different sorting methods. Yet, the sorting method of Shell and quick sort method have shown best results.

Quicksort is one of the most popular sorting algorithms, it is based on a divide-and-conquer technique and has a wide acceptance as the fastest general-purpose sorting technique. Though it is successful in separating large partitions into small ones, quicksort runs slowly when it processes its small partitions, for which completing the sorting through using a different sorting algorithm is much plausible solution. This variant minimizes the overall execution time but it switches to a constant sorting algorithm at a constant cut-off point. To cope with this constancy problem, it has been suggested that a dynamic model which can choose the fastest sorting algorithm for the small partitions. The model includes continuation with quicksort so that the cut-off point is also more flexible. To implement this with an intelligent algorithm selection model, artificial neural networks are preferred due to their non-comparison, constant-time and low-cost architecture features. In spite of the fact that finding the best sorting algorithm by using a neural network causes some extra computational time, the gain in overall execution time is greater. As a result, a faster variant of quicksort has been implemented by using artificial neural network based algorithm selection approach. Experimental results of the proposed algorithm and the Several other fast sorting algorithms have been presented, compared and discussed. (C) 2012 Elsevier Inc. All rights reserved.

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.

This paper presents a new procedure for the nondominated sorting with constraint handling to be used in a multiobjective evolutionary algorithm. The strategy uses a sorting algorithm and binary search to classify the solutions in the correct level of the Pareto front. In a problem with objective functions, using solutions in the population, the original nondominated sorting algorithm, used by NSGA-II, has always a computational cost of in a naïve implementation. The complexity of the new algorithm can vary from in the best case and in the worst case. A experiment was executed in order to compare the new algorithm with the original and another improved version of the Deb’s algorithm. Results reveal that the new strategy is much better than other versions when there are many levels in Pareto front. It is also concluded that is interesting to alternate the new algorithm and the improved Deb’s version during the evolution of the evolutionary algorithm.

A cut-and-paste operation can be a reversal, a transposition, or a transreversal on circular or linear permutations. There are several approximation algorithms for sorting signed permutations by combinations of these operations. For sorting unsigned permutations, we only know an algorithm with performance ratio 3 and its improved version with performance ratio [email protected] allowing reversals and transpositions. In this paper, we present a 2.25-approximation algorithm for sorting unsigned circular permutations by cut-and-paste operations. A structure called tie is proposed to represent the alternating path of length 5. We can classify the ties into 6 types and find ways to remove the breakpoints for each type of ties, so that every cut-and-paste operation can reduce at least 43 breakpoints averagely. Our algorithm can be used to sort unsigned linear permutations and achieve the performance ratio 2.25 if another operation named revrev is allowed.

Problem statement: Researchers focused their attention on optimally ad aptive sorting algorithm and illustrated a need to develop tools f or constructing adaptive algorithms for large class es of measures. In adaptive sorting algorithm the run time for n input data smoothly varies from O(n) to O(nlogn), with respect to several measures of disor der. Questions were raised whether any approach or technique would reduce the run time of adaptive sor ting algorithm and provide an easier way of implementation for practical applications. Approach: The objective of this study is to present a new method on natural sorting algorithm with a run time for n input data O(n) to O(nlogm), where m defines a positive value and surrounded by 50% of n . In our method, a single pass over the inputted data creates some blocks of data or buffers accordi ng to their natural sequential order and the order can be in ascending or descending. Afterward, a bottom up approach is applied to merge the naturally sorted subsequences or buffers. Additionally, a par allel merging technique is successfully aggregated in our proposed algorithm. Results: Experiments are provided to establish the best, wo rst and average case runtime behavior of the proposed method. The simulation statistics provide same harmony with the theoretical calculation and proof the method ef ficiency. Conclusion: The results indicated that our method uses less time as well as acceptable memory to sort a data sequence considering the natural order behavior and applicable to the realistic rese arches. The parallel implementation can make the algorithm for efficient in time domain and will be the future research issue.

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.

The generalized sorting problem is to find the first k largest elements among n input elements and to report them in a sorted order. In this paper, we propose a fast generalized sorting algorithm under the single hop wireless networks model with collision detection (WNCD). The algorithm is based on the maximum finding algorithm and the sorting algorithm. The key point of our algorithm is to use successful broadcasts to build broadcasting layers logically and then to distribute the data elements into those logic layers properly. Thus, the number of broadcast conflicts is reduced. We prove that the average time complexity required for our generalized sorting algorithm is Θ(k + log(n - k)). When k = 1, our generalized sorting algorithm does the work of finding maximum, and when k = n, it does the work of sorting. Thus, the analysis of our algorithm builds a connection between the two extremely special cases which are maximum finding and sorting.

A product network defines a class of topologies that are very often used such as meshes, tori, and hypercubes, etc. This paper proposes a generalized algorithm for fault-tolerant parallel sorting in product networks. To tolerate r - 1 faulty nodes, an r-dimensional product network containing faulty nodes is partitioned into a number of subgraphs such that each subgraph contains at most one fault. Our generalized sorting algorithm is divided into two steps. First, a single-fault sorting operation is presented to correctly performed on each faulty subgraph containing one fault. Second, each subgraph is considered a supernode, and a fault-tolerant multiway merging operation is presented to recursively merge two sorted subsequences into one sorted sequence. Our generalized sorting algorithm can be applied to any product network only if the factor graph of the product graph can be embedding in a ring. Further, we also show the time complexity of our sorting operations on a grid, hypercube, and Petersen cube. Performance analysis illustrates that our generalized sorting scheme is a truly efficient fault-tolerant algorithm.

We present a VLSI implementation of a hardware sorting algorithm for continuous data sorting. The device is able to continuously process an input data stream while producing a sorted output data stream. At each clock cycle, the device reads and processes a 48-bit word, 24 bits for the datum and 24 bits for the associated tag. The data stream is sorted according to the tags preserving the order of words with identical tags. Sequences up to 256 words are completely sorted and longer sequences are partially sorted. The maximum operation frequency is 50 Mwords/s. The architecture is based on a chain of identical elementary sorting units. A full custom design exploits the highly regular architecture to achieve high area and time performance. We describe the algorithm and give architectural details.

Block sorting is used in connection with Optical Character Recognition (OCR). Recent work has focused on finding good strategies which work in practice. In this paper, we show that optimizing block sorting is [Formula: see text]-hard. Along with this result, we give new non-trivial lower bounds. These bound can be computed efficiently. We define the concept of "Local Property Algorithms" and show that several previously published block sorting algorithms fall into this class.

To perform searching operation we have different kinds of searching techniques. These all searching algorithms works on data, which are previously sorted. An efficient algorithm is required to make searching fast and efficient. This paper presents a new sorting algorithm named as “Find and Place Sorting Technique for Unique Numbers (FPSTUN)”. This FPSTUN is designed to perform sorting quickly and easily and also efficient as existing algorithms in sorting.

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.

In this paper, we study a genome rearrangement primitive called block moves. This primitive as a special case of another well studied primitive transposition. We revisit the problem of BLOCK SORTING, which is a sorting problem under the primitive block moves in this work. BLOCK SORTING has been shown to be NP-Complete, and a couple of results have designed factor 2 approximation algorithms for the problem - the best known till date. However whether the problem is APX-Hard, or an improvement over the factor 2 approximation algorithms have been interesting open problems. We design a new factor 2 approximation algorithm for BLOCK SORTING. Our algorithm is equal to the best known in terms of approximation ratio, however, our approach is much simpler and is linear time (O (n)) as compared to the cubic (O (n3)) and quadratic (O (n2)) run-times of the existing algorithms for the problem.

This paper describes a computer-assisted non-existence proof of nine-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, we obtain that the 29-comparator network found by Waksman in 1969 is optimal when sorting ten inputs. This closes the two smallest open instances of the optimal size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to eight inputs. The proof involves a combination of two methodologies: one based on exploiting the abundance of symmetries in sorting networks, and the other, based on an encoding of the problem to that of satisfiability of propositional logic. We illustrate that, while each of these can single handed solve smaller instances of the problem, it is their combination which leads to an efficient solution for nine inputs., 18 pages

Sorting permutations by operations such as reversals and block-moves has received much interest because of its applications in computational biology, particularly in the study of genome rearrangements. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. This paper investigates the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation. A 4/3-approximation algorithm for this problem is presented. Exact polynomial-time algorithms are presented for woven bitonic permutations and woven double-strip permutations. A linear-time maximum matching algorithm for a special class of grid graphs is also discovered that improves the time complexity of one of these exact algorithms.

We present a hardware-algorithm for sorting N elements using either a p-sorter or a sorting network of fixed I/O size p while strictly enforcing conflict-free memory accesses. To the best of our knowledge, this is the first realistic design that achieves optimal time performance, running in /spl Theta/(NlogN/plogp) time for all ranges of N. Our result completely resolves the problem of designing an implementable, time-optimal algorithm for sorting N elements using a p-sorter. More importantly, however, our result shows that, in order to achieve optimal time performance, all that is needed is a sorting network of depth O(log/sup 2/p) such as, for example, Batcher's classic bitonic sorting network.

We present a simple and general parallel sorting scheme, ZZ-sort, which can be used to derive a class of efficient in-place sorting algorithms on realistic parallel machine models. We prove a tight bound for the worst case performance of ZZ-sort. We also demonstrate the average performance of ZZ-sort by experimental results obtained on a MasPar parallel computer. Our experiments indicate that ZZ-sort can be incorporated into a distributed memory parallel computer system as a standard routine, and this routine is useful for space critical situations. Finally, we show that ZZ-sort can be used to convert a non-adaptive parallel sorting algorithm into an in-place and adaptive one by considering the problem of sorting an arbitrarily large input on fixed-size reconfigurable meshes.

Reversals are operations of great biological significance for the analysis of the evolutionary distance between organisms. Genome rearrangement through reversals, consists in finding the shortest sequence of reversals to transform one genome represented as a signed or unsigned permutation into another. When genes are non oriented and correspondingly permutations are unsigned, sorting by reversals came arise as a challenging problem in combinatorics of permutations. In fact, this problem is known to be NP-hard, but the question whether it is NP-complete remains open for more than twenty years. When permutations are signed and correspondingly genes are oriented, the problem is known to be in P. A parallelization of a standard GA (Genetic Algorithm) is proposed for the problem of sorting unsigned permutations. This GA was previously reported in the literature as the most competitive regarding precision for which as control mechanism an 1.5-approximation algorithm was used. For the parallelization, the MPI Library of the C language was used and experiments were performed for calculating the execution time and precision. By increasing the number of individuals, experiment showed improvement in relation to previous approaches. Additionally, a virtualization of the GA using a MicroBlaze processor from Xilinx was performed on OVP for which the average number of executed instructions was of approximately 1.40 Giga instruction per second.

Sorting algorithms find their application in many fields. One of their main uses is to organize databases. Classical applications of sorting algorithms often can not cope satisfactorily with large data sets or with unfavorable poses of sorted strings. Typically, in such situations, we try to use other methods or apply sorting process to reshuffled input data. Unfortunately, this approach complicates sorting process and often results in significant prolongation of the time. In this paper, the authors examined an algorithm dedicated to the problem of sorting large scale data sets. In the literature, there are no studies of such examples. These studies will allow to describe the properties of sorting methods for large scale data sets. Performed tests have shown superior performance of the examined algorithm, especially for large scale data sets. Changes sped up sorting of data with any arrangement of the input elements.

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.

With the popularity of parallel database machines based on the shared-nothing architecture, it has become important to find external sorting algorithms which lead to a load-balanced computation, i.e., balanced execution, communication and output. If during the course of the sorting algorithm each processor is equally loaded, parallelism is fully exploited. Similarly, balanced communication will not congest the network traffic. Since sorting can be used to support a number of other relational operations (joins, duplicate elimination, building indexes etc.) data skew produced by sorting can further lead to execution skew at later stages of these operations. In this paper we present a load-balanced parallel sorting algorithm for shared-nothing architectures. It is a multiple-input multiple-output algorithm with four stages, based on a generalization of Batcher's odd-even merge. At each stage then keys are evenly distributed among thep processors (i.e., there is no final sequential merge phase) and the distribution of keys between stages ensures against network congestion. There is no assumption made on the key distribution and the algorithm performs equally well in the presence of duplicate keys. Hence our approach always guarantees its performance, as long asn is greater thanp 3, which is the case of interest for sorting large relations. In addition, processors can be added incrementally.

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.

A sorting network is a mathematical model which can be used as a multiple-input, multiple-output switching network [1]. Sorting network has been one of the most critical applications on parallel computing machines. Many classic textbooks on algorithms like Thomas H. Cormen, therefore considered this problem in great detail and listed many sorting network for this purpose [2]. Sorting networks CLR90, Sav98 turned out to be convenient mean to describe certain parallel sorting algorithms [2]. In this paper we have introduced a new sorting network having time complexity (log 2 N)2 of theoretically and practically, where N is the number of elements. This network has a special feature it will always give the data in the required sequence (ascending or descending order) and feed the input from any direction (moving from left to right or from right to left).

Sorting unsigned permutations by reversals is an important and difficult problem in combinatorial processing of permutations with important applications in bio-informatics for the interpretation of the evolutionary relationship between organisms. Since it was shown that the problem is NP-hard many approximation and a few evolutionary algorithms were proposed. In this paper we propose a new genetic algorithm approach that uses modified crossover and mutation operators adapted to the problem. Instead previous genetic algorithmic approaches, the proposed algorithm uses a very simple fitness function that can be linearly computed in the size of the permutation and updated in constant time, for each individual in each generation. In order to compare the accuracy of the computed solutions, an 1.5 approximation ratio algorithm was developed by fixing Christie's approximation method. The results showed that on average the proposed genetic approach produces competitive results in relation with the ones given by the 1.5-approximation algorithm. Additionally, it has been observed that for permutations of all sizes, that were randomly generated, it was alway possible to compute better solutions with the genetic than with the approximate approach and that the difference obtained for these cases is greater than the ones obtained in the cases in which the genetic approach has a worse behavior than the approximate one.

A sorting network is a mathematical model of an oblivious sorting algorithm - that is, a sorting algorithm in which all comparisons take place in a fixed order at predetermined positions in the list.The search for sorting networks of optimal size is an old problem. Asymptotically optimal networks of size O(n log n) are known, where n is the number of inputs, but the hidden constants are enormous. Genetic algorithms have been used to tackle this problem in a number of studies since the early 1990s, often focusing on the historically interesting case of 16 inputs. In this special case, the best known bound of 60 comparisons has been attained, but often through the use of a particular, highly structured, initial sequence of comparisons that narrows the search space by filtering out all but a small core of input sequences.We make explicit the concept of a filter - a fixed sequence of comparisons to be extended to a sorting network through a stochastic process - and present a new construction for any perfect square number of inputs. In the case of 9 inputs, we extend the filter to a sorting network of size 25, attaining the best known bound. For 16 and 25 inputs, we present a simple GA variant that extends the filter to produce small sorting networks with highly regular structure.

An algorithm is any well-defined procedure or set of instructions, that takes some input in the form of some values, processes them and gives some values as output. Sorting involves rearranging information into either ascending or descending order. Sorting is considered as a fundamental operation in computer science as it is used as an intermediate step in many operations. A new sorting algorithm namely ‘An Endto-End Bi-directional Sorting (EEBS) Algorithm’ is proposed to address the shortcomings of the current popular sorting algorithms. The goal of this research is to perform an extensive empirical analysis of the newly developed algorithm and present its functionality. The results of the analysis proved that EEBS is much more efficient than the other algorithms having O(n2 ) complexity, like bubble, selection and insertion sort..

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é.

We present a parallel sorting algorithm and its proof which sorts a sequence of n elements in time O(log2n) with n/2 processors on an EREW-PRAM computational model. A sorting network directly implements the algorithm using O(n·log n)PEs. The algorithm is based on the elementary Compare-Exchange operation and has the advantage that it does not require a powerful computational model, uses the least amount of space for the sorting problem, has small constants and can be implemented directly on a sorting network. Furthermore, the architecture of the network is simple and makes no unrealistic technological assumptions.

The tree representation of the MIMO detection problem is illuminating for the development, interpretation, and classification of various detection methods. One method, based on the Dijkstra's search algorithm, pursues tree exploration according to a bounded, sorted list of tree nodes. Since sorting directly affects tree exploration and truncation in this tree-search method, it is critical to the performance. Motivated by the observation that sorting according to nodes' path metric, as in the conventional algorithm, does not adequately represent the "goodness" of nodes, a new probabilistic sorting rule is developed by innovatively exploiting the statistical properties of the path metric to yield more effective sorting. The relationship between the probabilistic sorting and the conventional one is established, and new features of the probabilistic sorting are presented. The effectiveness of the proposed method is demonstrated by computer simulation, where the new method outperforms the previous tree-search method in achieving near-ML detection performance, and meanwhile offers significant complexity reduction compared to the previous tree-search method.

Sorting is a well-known problem frequently used in many aspects in the world of computational applications. Sorting means arranging a set of records (or a list of keys) in some (increasing or decreasing) order. In this solution report, a complete graph structure based comparison sorting algorithm, CompleteGraphSort has been proposed that takes time Θ(n2) in the worst-case, where n is the number of records in the given list to be sorted.

Sorting by reversals is a simplified version of the genome rearrangement problem that seeks to discover the evolutionary relationship between different genomes, and is one of the many challenging problems in Bioinformatics. Solving the problem optimally has been proved to be NP-Hard and so a selection of approximation algorithms have been developed. In this paper a new mapping order is introduced to solve the problem of sorting unsigned permutations using a specialized multi-objective genetic algorithm. Our modified genetic algorithm uses a population with variable length individuals to maintain a worst time running time complexity of O(n4 log2 n), where n is the problem size. The results show that this approach is more effective than the 3/2 heuristic method and previous genetic algorithm approaches.

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 generation algorithm of permutation based on sorting makes the Series of permutations have some special features. The features guide the next generation under the current permutation, so the algorithm can effectively control the process of generating permutation. And the extended permutation generation algorithm based on sorting can meet some special requirements of clustering.

The design and analysis of adaptive sorting algorithms has made important contributions to both theory and practice. The main contributions from the theoretical point of view are: the description of the complexity of a sorting algorithm not only in terms of the size of a problem instance but also in terms of the disorder of the given problem instance; the establishment of new relationships among measures of disorder; the introduction of new sorting algorithms that take advantage of the existing order in the input sequence; and, the proofs that several of the new sorting algorithms achieve maximal (optimal) adaptivity with respect to several measures of disorder. The main contributions from the practical point of view are: the demonstration that several algorithms currently in use are adaptive; and, the development of new algorithms, similar to currently used algorithms that perform competitively on random sequences and are significantly faster on nearly sorted sequences. In this survey, we present the basic notions and concepts of adaptive sorting and the state of the art of adaptive sorting algorithms.

A new parallel sorting algorithm suitable for MIMD multiprocessor is presented. The algorithm reduces memory and bus contention, which many parallel sorting algorithms suffer from, by using a regular sampling of the data to ensure good pivot selection. For n data elements to be sorted and p processors, when n ≥ p 3 the algorithm is shown to be asymptotically optimal. In theory, the algorithm is within a factor of 2 of achieving ideal load balancing. In practice, there is almost a perfect partitioning of work. On a variety of shared and distributed memory machines, the algorithm achieves better than half-linear speedups.

Sorting is a very well known problem in computer science. It means arranging the data in either increasing or decreasing order. Here we present a new comparison based sorting algorithm whose complexity is theoretically shown to be O(n2).However graphs of total time taken by different sorting algorithms confirms the superiority of our algorithm over other existing similar algorithms. We have also proved the correctness of the proposed algorithm. The logic of this algorithm can be used for searching efficiently in a two dimensional array.

Sorting algorithms and the sorting itself is an important concept in computational field. In this research study, we are proposing a unique sorting algorithm, based on assuming the first value as smallest and comparing it with the rest of the list and assuming the last value as biggest and comparing it with the rest of the list. Running cost analysis and its results obtained after implementation are provided in graphical form with an objective to compare the efficiency of the proposed technique with some existing well known techniques of sorting.

In this paper we present a sorting algorithm, which uses the methodology of insertion sort efficiently to give a much better performance than the existing sorting algorithms of the O(n² ) class. We prove the correctness of the algorithm and give a detailed time complexity analysis of the algorithm. We also describe various applications of the algorithms.

In this paper, we study the problem of sorting a large collection of strings in external memory. Based on adaptive construction of a summary data structure, called adaptive synopsis trie , we present a practical string sorting algorithm DistStrSort , which is suitable for sorting string collections of large size in external memory, and also suitable for more complex string processing problems in text and semi-structured databases such as counting, aggregation, and statistics. Case analyses of the algorithm and experiments on real datasets show the efficiency of our algorithm in realistic setting.