Hide
Раскрыть

ISSN 2587-814X (print),
ISSN 2587-8158 (online)

Russian version: ISSN 1998-0663 (print),
ISSN 2587-8166 (online)

Sergey Avdoshin1, M. Shatilov
  • 1 National Research University Higher School of Economics, 20 Myasnitskaya Str., Moscow, 101000, Russian Federation

Minimization of Number of Comparisons of Worst-Case Linear Selection Algorithm

2010. No. 1. P. 3–9 [issue contents]

In this paper, a problem statement of parametric optimization of Blum, Floyd, Pratt, Rivest, and Tarjan’s worst-case linear selection algorithm is considered. We define the parameter value that guarantees minimal theoretical upper bound of worst-case number of comparisons. We research dependence between number of comparisons and various values of parameter which is based on computational experiment.

Citation: Avdoshin S. M., Shatilov M. P. (2010) Minimizatsiya chisla sravneniy v khudshem sluchae v algoritme poiska poryadkovykh statistik [Minimization of Number of Comparisons of Worst-Case Linear Selection Algorithm] Biznes-informatika, 1, pp. 3-9 (in Russian)
Keywords: binary comparisons; algorithms optimization; linear selection algorithm; recursions theory; swap generation algorithm
 Full text
BiBTeX
RIS
 
 
Rambler's Top100 rss