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.

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.

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.

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.

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.

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

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.

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.

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

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.

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.

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.

In this paper we give a bijection between the class of permutations that can be drawn on an X-shape and a certain set of permutations that appears in [Knuth] in connection to sorting algorithms. A natural generalization of this set leads us to the definition of almost-increasing permutations, which is a one-parameter family of permutations that can be characterized in terms of forbidden patterns. We find generating functions for almost-increasing permutations by using their cycle structure to map them to colored Motzkin paths. We also give refined enumerations with respect to the number of cycles, fixed points, excedances, and inversions., 17 pages, 9 figures

International audience; This paper proposes new algorithms for computing pairwise rearrangement scenarios that conserve the combinatorial structure of genomes. More precisely, we investigate the problem of sorting signed permutations by reversals without breaking common intervals. We describe a combinatorial framework for this problem that allows to characterize classes of signed permutations for which one can compute in polynomial time a shortest reversal scenario that conserves all common intervals. In particular we define a class of permutations for which this computation can be done in linear time with a very simple algorithm that does not rely on the classical Hannenhalli-Pevzner theory for sorting by reversals. We apply these methods to the computation of rearrangement scenarios between permutations obtained from 16 synteny blocks of the X chromosomes of the human, mouse and rat.

The growing complexity of modern processors has made the development of highly efficient code increasingly difficult. A promising automatic code generation strategy is implemented by library generators. This approach has mainly been applied to scientific codes which can be optimized by identifying code characteristics that depend only on the target machine. In this paper, we study the generation of sorting routines whose performance also depends on the characteristics of the input data. We present two approaches to generate efficient sorting routines. First, we consider the problem of selecting the best "pure" sorting algorithm as a function of the characteristics of the input data. We used machine learning algorithms to compute a function for each target machine that, at runtime, is used to select the best algorithm. Our second approach generalizes the first approach and can build new sorting algorithms from a few primitive operations. We use genetic algorithms and a classifier system to build hierarchically-organized hybrid sorting algorithms. Our results show that the algorithms generated using this second approach are quite effective and perform significantly better than the many conventional sorting implementations we tested. In particular, the routines generated using the second approach performs better than the most popular libraries available today: IBM ESSL, INTEL MKL and the C+ + STL.

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.

Unsigned circular permutations are used to represent tours in the traveling salesman problem as well as the arrangement of gene loci in circular chromosomes. The minimum number of segment reversals required to transform one circular permutation into another gives some measure of distance between them which is useful when studying the 2-opt local search landscape for the traveling salesman problem, and, when determining the phylogeny of a group of related organisms. Computing this distance is equivalent to sorting by (a minimum number of) reversals. In this paper we show that sorting circular permutations by reversals can be reduced to the same problem for linear reversals, and that it is NP-hard. These results suggest that for most practical purposes any computational tools available for reversal sort of linear permutations will be sufficiently accurate. These results entail the development of the algebraic machinery for dealing rigorously with circular permutations. © Springer-Verlag Berlin Heidelberg 2003.

We study several tested cases of the error-correcting graph isomorphism problem. The set Sn of n! permutations on n items is the search space for this optimization problem. We apply MA-sorting. This is a memetic algorithm with domain-independent mutation operators based on classical sorting. Each sorting algorithm works on results to a comparison predicate and defines a path in SI.,. In MA-sorting the mutation operator is a local-search that evaluates permutations suggested by the sorting algorithm. When such evaluation results in an improvement, the mutation is accepted and the comparison operator of the sorting algorithm evaluates to true. In contrast with previous proposals, our MA-sorting instantiated with selection sort finds optimal solutions for this case study.

A novel class of Very Fast Sorting Networks based on the theoretical properties of sorting is presented. The sorting algorithm makes exclusive use of the n-input maximum and minimum. It is shown that it is possible to design a Sorting Network of any size if some suitable rules are adopted. The most important characteristic of this technique is that the total delay, which is lower than that of other solutions, is almost independent of the number of Sorting Network inputs. The Sorting Networks presented are easy to implement as VLSI circuits.

In many situations, a statistical method must be applied repeatedly, e.g., during a series of iterations. Procedures based on ranks and order statistics are often attractive but, if used in a repetitive context, may require sorting each of a sequence of data sets. In many cases, the sort performed on a given member of such sequences can be used to induce partial sorting in the next member. This can in turn lead to sharply lower computing costs: While sorting random input requires O(n log n) time, some types of nonrandom input can be sorted in just O(n) time. Two sorting algorithms designed for partly sorted input are presented, and their performance compared with that of some widely used sorting methods. The advantages of capitalizing on partly sorted input are demonstrated in a simulation study of an iterative algorithm for computing Jaeckel's robust estimator in simple regression.

In this paper, we propose a taxonomy of parallel sorting that includes a broad range of array and file sorting algorithms. We analyze the evolution of research on parallel sorting, from the earliest sorting networks to the shared memory algorithms and the VLSI sorters. In the context of sorting networks, we describe two fundamental parallel merging schemes the odd-even and the bitonic merge. Sorting algorithms have been derived from these merging algorithms for parallel computers where processors communicate through interconnection networks such as the perfect shuffle, the mesh and a number of other sparse networks. After describing the network sorting algorithms, we show that, with a shared memory model of parallel computation, faster algorithms have been derived from parallel enumeration sorting schemes, where keys are first ranked and then rearranged according to their rank. Parallel sorting algorithms are evaluated according to a number of criteria, related not only to their time complexity, but also to their feasibility from a computer architecture point of view. We show that in addition to their attractive communication schemes, network sorting algorithms have non-adaptive schedules that make them suitable for implementation. In particular, they are easily generalized to block-sorting algorithms, that utilize limited parallelism to solve large sorting problems. We also address the problem of sorting large mass-storage files in parallel, using modified disk devices or intelligent bubble memories. Finally, the newer area of VLSI sorting is mentioned as an active and promising direction of research on parallel sorting.

We provide tight upper and lower bounds, up to a constant factor, for the number of inputs and outputs (I/OS) between internal memory and secondary storage required for five sorting-related problems: sorting, the fast Fourier transform (FFT), permutation networks, permuting, and matrix transposition. The bounds hold both in the worst case and in the average case, and in several situations the constant factors match. Secondary storage is modeled as a magnetic disk capable of transferring P blocks each containing B records in a single time unit; the records in each block must be input from or output to B contiguous locations on the disk. We give two optimal algorithms for the problems, which are variants of merge sorting and distribution sorting. In particular we show for P = 1 that the standard merge sorting algorithm is an optimal external sorting method, up to a constant factor in the number of I/Os. Our sorting algorithms use the same number of I/Os as does the permutation phase of key sorting, except when the internal memory size is extremely small, thus affirming the popular adage that key sorting is not faster. We also give a simpler and more direct derivation of Hong and Kung's lower bound for the FFT for the special case B = P = O(1).

The paper asserts that the hidden-surface problem is mainly one of sorting. The various surfaces of an object to be shown in hidden-surface or hidden-line form must be sorted to find out which ones are visible at various places on the screen. Surfaces may be sorted by lateral position in the picture (XY), by depth (Z), or by other criteria. The paper shows that the order of sorting and the types of sorting used form differences among the existing hidden-surface algorithms. (Modified author abstract)

The information-gathering aspect of sorting is considered from a theoretical viewpoint. A large class, R, of sorting algorithms is defined, based on the idea of information use. Properties of this algorithm class are developed, and it is noted that several well-known sorting algorithms are closely related to algorithms in R . The Binary Tree Sort is shown to be in R and to have unique properties in this class. A vector is defined which characterizes the information-gathering efficiency of the algorithms of R . Finally, a more general class of algorithms is defined, and some of the definitions extended to this class. Two intriguing conjectures are given which appear to require graph theory or combinatorial topology for their solution.

An ordering operator that leads to the development of an algorithm for internal sorting is described. An analysis of the algorithm is presented, together with a discussion of the number of comparisons necessary for sorting. It is shown that the number of comparisons is close to the theoretically obtainable number. The sorting algorithm is a variant of the two-way merge.

In this paper a new general approach for the so-called “zero-one principle” for sorting algorithms is described. A theorem from propositional logic that states the connection between two-valued logic and many-valued logic is used to prove this zero-one principle. As a consequence a zero-one principle for a more general class of sorting algorithms is derived.

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.

Most queries that applied on database management systems (DBMS) depend heavily on the performance of the used sorting algorithm. In addition to have an efficient sorting algorithm, as a primary feature, stability of such algorithms is a major feature that is needed in performing DBMS queries. In this paper, we study a new Sorting Algorithm for Join Queries (SAJQ) that has both advantages of being efficient and stable. The proposed algorithm takes the advantage of using the m -way-merge algorithm in enhancing its time complexity. SAJQ performs the sorting operation in a time complexity of O ( n log m ), where n is the length of the input array and m is number of sub-arrays used in sorting. An unsorted input array of length n is arranged into m sorted sub-arrays. The m -way-merge algorithm merges the sorted m sub-arrays into the final output sorted array. The proposed algorithm keeps the stability of the keys intact. An analytical proof has been conducted to prove that, in the worst case, the proposed algorithm has a complexity of O ( n log m ). Also, a set of experiments has been performed to investigate the performance of the proposed algorithm. The experimental results have shown that the proposed algorithm outperforms other Stable–Sorting algorithms that are designed for join-based queries.

A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.

Sorting permutations by reversals is one of the most challenging problems related with the analysis of the evolutionary distance between organisms. Genome rearrangement can be done through several operations with biological significance, such as block interchange, transposition and reversal, among others; but sorting by reversals, that consists in finding the shortest sequence of reversals to transform one genome into another, came arise as one of the most challenging problems from the combinatorial and algebraic points of view. In fact, sorting by reversal unsigned permutations is an NP-hard problem, for which the question of NP-completeness remains open for more than two decades and for which several interesting combinatorial questions, such as the average number of reversals needed to sort permutations of the same size, remain without solution. In contrast to the unsigned case, sorting by reversals signed permutations belongs to P. In this paper, a standard genetic algorithm for solving the problem of sorting by reversals unsigned permutations is proposed. This approach is based on Auyeung and [email protected]?s method which uses exact solutions for the signed case in order to build approximate solutions for the unsorted one. Additionally, an improved genetic algorithm is proposed, that in the initial generations applies reversals that simultaneously eliminate two breakpoints, a heuristic mechanism used by several approximation algorithms. As control mechanism for estimating the precision of the results, a correct implementation of an 1.5-approximation algorithm was developed. Also, the results were compared with permutations for which exact solutions are known, such as [email protected]?s permutations and their inverses. Several experiments with randomly generated permutations were performed and the results showed that in average the precision of the outputs provided by both the standard and improved genetic algorithms overcome the results given by the 1.5-approximation algorithm as well as those results provided by previous known genetic approaches.

What is a sorting function—not a sorting function for a given ordering relation, but a sorting function with nothing given?Formulating four basic properties of sorting algorithms as defining requirements, we arrive at intrinsic notions of sorting and stable sorting: A function is a sorting function if and only it is an intrinsically parametric permutation function. It is a stable sorting function if and only if it is an intrinsically stable permutation function.We show that ordering relations can be represented isomorphically as inequality tests, comparators and stable sorting functions, each with their own intrinsic characterizations, which in turn provide a basis for run-time monitoring of their expected I/O behaviors. The isomorphisms are parametrically polymorphically definable, which shows that it is sufficient to provide any one of the representations since the others are derivable without compromising data abstraction.Finally we point out that stable sorting functions as default representations of ordering relations have the advantage of permitting linear-time sorting algorithms; inequality tests forfeit this possibility.

An important problem in genome rearrangements is sorting permutations by transpositions. The complexity of the problem is still open, and two rather complicated 1.5-approximation algorithms for sorting linear permutations are known (Bafna and Pevzner, 98 and Christie, 99). The fastest known algorithm is the quadratic algorithm of Bafna and Pevzner. In this paper, we observe that the problem of sorting circular permutations by transpositions is equivalent to the problem of sorting linear permutations by transpositions. Hence, all algorithms for sorting linear permutations by transpositions can be used to sort circular permutations. Our main result is a new O(n3/2logn) 1.5-approximation algorithm, which is considerably simpler than the previous ones, and whose analysis is significantly less involved.

A technique for proving min-max norms of sorting algorithms is given. One new algorithm for finding the minimum and maximum elements of a set with fewest comparisons is proved optimal with this technique.

Integer sorting is a subclass of the sorting problem where the elements have integer values and the largest element is polynomially bounded in the number of elements to be sorted. It is useful for applications in which the size of the maximum value of element to be sorted is bounded. In this paper, we present a new distributed radix-sort algorithm for integer sorting. The structure of our algorithm is similar to radix sort except that it typically requires less number of communication phases. We present experimental results for our algorithm on two distributed memory multiprocessors, the Intel Paragon and the Thinking machine CM-5. These results are compared with two other well known practical parallel sorting algorithms based on radix sort and sample sort. The experimental results show that the distributed radix-sort is competitive with the other two algorithms.