Open AccessNew selection algorithm based on generating sequences
Author(s) -
Y. N. Artamonov,
Y. V. Alyaeva
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1847/1/012026
Subject(s) - sequence (biology) , selection (genetic algorithm) , algorithm , statistic , range (aeronautics) , natural number , value (mathematics) , computer science , mathematics , combinatorics , artificial intelligence , statistics , genetics , materials science , composite material , biology
The paper proposes a new deterministic selection algorithm with computational complexity O(n) , called cs-select, which is a modification of the quickselect algorithm. The changes concern the selection of reference elements. Instead of selecting some elements of the sequence itself as References, the cs-select algorithm proposes to use finite segments of complete sequences, that allow to represent any natural number in a given range as the sum of elements from a selected finite segment of the complete sequence. It is theoretically justified that in the cs-select algorithm, the number of comparisons when searching for the k-th statistic in a sequence of length n can converge to the value 2n with unlimited growth of n for some complete sequences. It was also shown that different variations of the complete sequences make it possible to reduce the latent constant in O(n) less than 2.