On extremal sort sequences

A sort sequence S_n is a sequence of all unordered pairs of indices inI _n = {1, 2, ..., n}. With a sort sequenceS_n = (s₁ ,s₂ ,...,s_{( 2ⁿ )} )S_n = (s_1 ,s_2 ,...,s_{\left( {_2^n } \right)} ), one can associate a predictive sorting algorithm A(S_n). An execution of the algorithm performs pairwise comparisons of elements in the input setX in the order defined by the sort sequence S_n except that the comparisons whose outcomes can be inferred from the results of the preceding comparisons are not performed. A sort sequence is said to be extremal if it maximizes a given objective function. First we consider the extremal sort sequences with respect to the objective function ω(S_n) — the expected number of active predictions inS _n. We study ω-extremal sort sequences in terms of their prediction vectors. Then we consider the objective function Ω(S_n) — the minimum number of active predictions in S_n over all input orderings.     

Weak-heap sort

A data structure called aweak-heap is defined by relaxing the requirements for a heap. The structure can be implemented on a 1-dimensional array with one extra bit per data item and can be initialized withn items using exactlyn–1 data element compares. Theoretical analysis and empirical results indicate that it is a competitive structure for sorting. The worst case number of data element comparisons is strictly less than (n–1) logn+0.086013n and the expected number is conjectured to be approximately (n–0.5)logn–0.413n.     

一类分布族

针对索赔分布在风险理论中的研究需要,利用其失效函数,探讨了一类介于重尾与轻尾分布间的分布,并给出该族分布的基本性质及其几种重要的判断方法.     

Matrix characterization of oscillation for double sequences

The notion of oscillation for ordinary sequences was presented by Hurwitz in 1930. Using this notion Agnew and Hurwitz presented regular matrix characterization of the resulting sequence space. The primary goal of this article is to extend this definition to double sequences, which grants us the following definition: the double oscillation of a double sequence of real or complex number is given P-lim sup_{(m,n)→∞;(α,β)→∞}|S _m,n -S _α,β |. Using this concept a matrix characterization of double oscillation sequence space is presented. Other implication and variation shall also be presented.      

Regularity characterization of asymptotically probability equivalent sequences

The notion of asymptotically equivalent sequences was presented by Pobyvanets in 1980. Using this definition, he presented Silverman–Toeplitz-type matrix conditions that ensure that a summability matrix preserves asymptotic equivalency. This work begins with an extension of Pobyvanets’ definition of convergence in probability. This definition is also used to present Silverman–Toeplitz-type conditions for ensuring that a summability matrix preserves asymptotic probability equivalence. In addition, we shall also present a Marouf-type characterization of such a sequence space.     

Matrix characterization of A-statistical convergence of double sequences

We characterize the multiplier space of summability fields of four dimensional RH-regular matrices and show that the space of multipliers of a nonnegative RH-regular matrix over an algebra \(\mathcal{U} \) is the space of A-statistically convergent double sequences. For this purpose we prove a variant of the Brudno–Mazur–Orlicz bounded consistency theorem for a class of four dimensional matrices. Finally we give a matrix characterization of A-statistical convergence over the space of the Pringsheim A-uniformly integrable double sequences.     

The characterization of compact operators on spaces of strongly summable and bounded sequences

We use the characterizations of the classes of all infinite matrices that map the spaces of sequences which are strongly summable or bounded by the Cesàro method of order 1 into the spaces of null or convergent sequences given by Ba?ar, Malkowsky and Altay [Matrix transformations on the matrix domains of triangles in the spaces of strongly C₁-summable and bounded sequences, Publ. Math. Debrecen 73 (1-2) (2008), 193-213] and the Hausdorff measure of noncompactness to characterize the classes of all compact operators between those spaces.     

Conditional connectivity of bubble sort graphs

A subset F ? V (G) is called an R ^k -vertex-cut of a graph G if G ? F is disconnected and each vertex of G ? F has at least k neighbors in G ? F. The R ^k -vertex-connectivity of G, denoted by κ ^k (G), is the cardinality of a minimum R ^k -vertex-cut of G. Let B _n be the bubble sort graph of dimension n. It is known that κ _k (B _n ) = 2 ^k (n ? k ? 1) for n ≥ 2k and k = 1, 2. In this paper, we prove it for k = 3 and conjecture that it is true for all k ∈ N. We also prove that the connectivity cannot be more than conjectured.     

Recursive merge sort with erroneous comparisons

In this paper, we analyze the recursive merge sort algorithm and quantify the deviation of the output from the correct sorted order if the outcomes of one or more comparisons are in error. The disorder in the output sequence is quantified by four measures: the number of runs, the smallest number of integers that need to be removed to leave the sequence sorted, the number of inversions, and the smallest number of successive exchanges needed to sort the sequence. For input sequences whose length is large compared to the number of errors, a comparison is made between the robustness to errors of bubble sort, straight insertion sort, and recursive merge sort.     

Speeding sort algorithms by special instructions

This paper investigates some possibilities to speed up inner loops of certain sort algorithms by means of special instructions derived separately for each algorithm. Execution times were evaluated by a simple timing model in which the times taken by data references were strongly stressed. The results obtained by simulation experiments show that it is difficult to challenge the leading position of quicksort, although the relative time reductions in some less efficient algorithms are larger. We also discuss the question of the limits of any improvements by examining the microprogramming of the whole algorithms.     

The prediction of sequences

The problem of predicting the short-term future behavior of a sequence, after observing it as long as we please, so as to achieve a specified reliability against all possible sequences is considered. For a particular problem, namely, predicting when in a sequence of 0's and 1's the pair (1, 0) in that order is not coming next, a reliability of 3/4 can be approximated as closely as we please, but not achieved. This article appeared as a Research Memorandum of the Rand Corporation, RM-1570, 12 October 1955.     

The analysis of linear probing sort by the use of a new mathematical transform

A variant of the distribution sort approach which makes use of extra storage to sort a list of n elements in an average of about probes into a table is presented. An accurate analysis of this technique is made by introducing a transform from a Poisson approximation to the exact (finite) distribution. This analysis also leads to the solution of an interesting parking problem.     

Design of the federal express large package sort facility

In this paper, two mixed integer programming models, the Aggregate Bin Assignment Model (ABAM) and Aggregate Rack Assignment Model (ARAM), are developed for the analysis of possible large package sort facility designs for Federal Express Corporation. Applying the ABAM and RAM algorithm on the current topological design of the sort facility reduces the number of forklifts and total forklift travel time for accomplishing the sort by about 20%. Tests on 16 other configurations proposed by Federal Express indicated that savings of 33% with respect to the number of forklifts required and over 50% in the total forklift travel time when compared to the existing operations can be achieved.     

基于同异反态势排序的学生成绩分析

同异反态势排序是根据同异反联系数 a+bi+cj中 a、b、c大小关系而进行的一种排序。当把学生成绩用同异反联系数表示之后 ,可对照同异反态势排序表来研究其中的某些规律     

Implementation of samplesort: A minimal storage tree sort

An implementation of samplesort, a generalization of minimal-storage tree-sorting, is presented as an algorithm which is relatively insensitive to possible non-random permutations of the elements to be sorted. A brief analytical discussion and the results of extensive empirical tests are included. It is claimed that with the particular choice of samplesize, samplesort is probably one of the most efficient, if not the most efficient sorting algorithm known.     

A characterization of the kneading sequences associated to Lorenz maps of the interval

In this paper we characterize the kneading sequences associated to Lorenz maps of the interval.     

A Morita type theorem for a sort of quotient categories

We consider the quotient categories of two categories of modules relative to the Serre classes of modules which are bounded as abelian groups and we prove a Morita type theorem for some equivalences between these quotient categories.