KIAM Main page Web Library  •  Publication Searh  Русский 

Article collection "Mathematical Problems of Cybernetics" №17, Moscow, 2008
Authors: Zubkov A.M., Sokolov D.V.
Partial sorting algorithms for sets of sums
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 2n sums over all subsets of a set {c1,…,cn} and B) a set of sums a1bσ1+…+anbσn for all n! permutations σ =(σ1,…, σn), where {a1,…,an} and {b1,…,bn} 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(nM2) operations for the case B).
sorting algorithms, set of sums, list of maximal elements
Publication language: russian,  pages: 10 (p. 225-234)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Zubkov A.M.,  ,  Математический институт им.В.А.Стеклова РАН
  • Sokolov D.V.,  Математический институт им.В.А.Стеклова РАН