Partial sorting of a set of numbers consists in construction of a nonincreasing list containing a subset of a given set. Two types of sets are considered: A) a set of 2ⁿ sums over all subsets of a set {c₁,…,c_n} and B) a set of sums a₁b_σ1+…+a_nb_σn for all n! permutations σ =(σ₁,…, σ_n), where {a₁,…,a_n} and {b₁,…,b_n} are given sets. It is shown that a sorted list of M maximal elements of the set of sums may be constructed with the complexity O(nM) operations for the case A) and with the complexity O(nM²) operations for the case B).

sorting algorithms, set of sums, list of maximal elements

Mathematical problems and theory of numerical methods