A variant of the Ford-Johnson algorithm that is more space efficient

A variant of the Ford-Johnson or merge insertion sorting algorithm that we called four Ford-Johnson (₄FJ, for short) is presented and proved to execute exactly the same number of comparisons than the Ford-Johnson algorithm. The main advantage of our algorithm is that, instead of recursively working over lists of size the half of the input, as the Ford-Johnson algorithm does, ₄FJ recursively works over lists of size the quarter of the input. This allows for implementations of data structures for coordinating the recursive calls of size only 33% of the ones needed for the Ford-Johnson algorithm.     

An efficient external sorting with minimal space requirement

An efficient external sorting algorithm with minimal space requirement is presented in this article. The average number of passes over the data is approximately 1 +Ln(N + 1)/4B, whereN is the number of records in the file to be sorted, andB is the buffer size. The external storage requirement is only the file itself, no additional disk space is required. The internal storage requirement is four buffers: two for input, and two for output. The buffer size can be adjusted to the available memory space. A stack of size log₂ N is also required.This work was partially supported by a fellowship and grant from Western Michigan University.     

An analysis and implementation of an efficient in-place bucket sort

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

An efficient algorithm for Horn description

We give a new algorithm for computing a prepositional Horn CNF formula given the set of its models. Its running time is O(|R|n(|R|+n)), where |R| is the number of models and n that of variables, and the computed CNF contains at most |R|n clauses. This algorithm also uses the well-known closure property of Horn relations in a new manner.     

Implementation of bubble sort and the odd-even transposition sort on a rack of transputers

In this short note we discuss implementation of bubble sort and its variant the odd-even transposition sort in a parallel environment consisting of a network of transputers, with the accompanying OCCAM language.     

An efficient parallel algorithm for building the separating tree

We present an efficient parallel algorithm for building the separating tree for a separable permutation. Our algorithm runs in O(log²n)$O\left({log}^{2}n\right)$ time using O(nlog^1.5n)$O\left(n{log}^{1.5}n\right)$ operations on the CREW PRAM and O(log²n)$O\left({log}^{2}n\right)$ time using O(nlognloglogn)$O(nlognloglogn)$ operations on the COMMON CRCW PRAM.     

An efficient implementation algorithm for generating de Bruijn sequences

A nonsingular feedback shift register will generate pairwise disconnecting cycles. To get a de Bruijn cycle, we put a different mark on the states that are on the different cycle. This could help us find adjacent cycles easily and join them together. We modify the marks of the states that on the joined cycles to the same mark. At the same time, the feedback function is modified accordingly. Then a full cycle is obtained when the marks of all the states on different cycles are modified to the same mark. At the same time, the feedback function that could generate the de Bruijn sequences is also obtained.     

A new external sorting algorithm with no additional disk space

This paper is concerned with an external sorting algorithm with no additional disk space. The proposed algorithm is a hybrid one that uses Quicksort and special merging process in two distinct phases. The algorithm excels in sorting a huge file, which is many times larger than the available memory of the computer. This algorithm creates no extra backup file for manipulating huge records. For this, the algorithm saves huge disk space, which is needed to hold the large file. Also our algorithm switches to special merging process after the first phase that uses Quicksort. This reduces the time complexity and makes the algorithm faster.     

Simple and efficient floor-planning

We show a new algorithm for computing in O(n) time a floor-plan of a given plane near-triangulation. We use modules which are the union of two rectangles and are T-, L- or I-shaped. Our algorithm has the following advantages: the number of T-shaped modules is at most , all T-shaped modules are uniformly directed, the size of the picture is at most n×n−1. A very important asset of our algorithm is its extraordinary simplicity.     

An efficient algorithm for estimating rotation distance between two binary trees

There are a number of ways of measuring the difference in shape between two rooted binary trees with the same number of leaves. Pallo (Computer Journal, 9, 171–175, 1986) introduced a left weight sequence, which is a sequence of positive integers, to characterize the structure of a binary tree. By applying the AVL tree transformation on binary trees, we develop an algorithm for the efficient transformation of the left weight sequences between two binary trees.     

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

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

Simplified odd-even sort using multiple shift-register loops

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

Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort

In this paper, we proposed a new efficient sorting algorithm based on insertion sort concept. The proposed algorithm is called Bidirectional Conditional Insertion Sort (BCIS). It is in-place sorting algorithm and it has remarkably efficient average case time complexity when compared with classical insertion sort (IS). By comparing our new proposed algorithm with the Quicksort algorithm, BCIS indicated faster average case time for relatively small size arrays up to 1500 elements. Furthermore, BCIS was observed to be faster than Quicksort within high rate of duplicated elements even for large size array.     

An efficient approach to cyclic reference counting based on a coarse-grained search

Reference counting is known to have problems working with cyclic structures. In this paper, we present an efficient approach to cyclic reference counting, consisting of two key components. The first is a coarse-grained cycle collection algorithm that essentially performs a coarser (lightweight) analysis of the computation graph and thus greatly reduces the tracing cost (in comparison with the algorithms based on trial deletion to detect cycles). Our new cycle collector relies on this algorithm to obtain efficiency. Second, a predefined backup algorithm is incorporated to eliminate a theoretical problem that appears in the coarse-grained algorithm, thereby making the collector more practical. In this regard, we develop a heuristic based on the runtime behavior of the cycle collection to help the collector determine when to trigger the backup one. We have implemented and evaluated the proposed cycle collector on the Jikes RVM, where the SPECjvm98 benchmarks were applied. The results demonstrate that the novel approach is efficient and practical, compared to a modern cycle collector based on trial deletion.