Арапайым таңдаумен сорттау анализі.

Кілттерді салыстыру саны С кілттердің бастапқ ы ретіне тә уелді емес. Бұ л ретте қ арапайым таң даумен сорттау қ арапайым енгізулермен сорттауғ а қ арағ анда орынды екенін айтуғ а болады. Біз мынаны аламыз:

Жө нелтудің бастапқ ы реттелген кілттер жағ дайында минималды саны

M _min = і (n -1)

жә не ең ү лкен мә нді қ абылдайды:

,

егер бастапқ ыда кілттер кері тә ртіппен орналасқ ан болса. Алгоритмнің қ арапайымдылығ ына қ арамастан орташаны М_орт. анық тау қ иын. Ол неше рет анық талуына тә уелді, k₁,..., k_n тізбегін қ арастырғ анда k_i келесі k₁,..., k_{iө 1} шамалардан кіші болады. Саны n -ғ а тең n кілттердің барлық орын ауыстырулары ү шін алынғ ан орташа шама, бұ л

H_n -1,

мұ ндағ ы H_n - n-дік гармониялық сан

(Д.Кнут. Т.1 қ араң ыз).

H_n санын былайша бейнелеуге болады:

мұ ндағ ы y=0.577216... - эйлеров тұ рақ тысы. Жеткілікті ү лкен n ү шін біз бө лшек қ осылғ ыштарды қ алдырып кетіп, осылайша i-інші ө туде игерулердің орташа санын келесі тү рде аппроксимирлей аламыз:

.

Онда М орт. жө нелтулердің орташа саны таң даумен іріктеу кезінде F_i қ осындысы бар, бұ нда i 1-ден n-ге дейінгі мә ндерді қ абылдайды:

Интегралдың кө мегімен ары қ арай жекелеген қ осылғ ыштардың қ осындысын аппроксимирлей отырып

Осы жуық мә нді аламыз

Біз қ арапайым таң даумен іріктеу ә детте қ арапайым енгізулермен іріктеуге қ арағ анда тә уірлеу, бірақ кілттер ертерек іріктелген немесе іріктелген дерлік жағ дайларында қ арапайым енгізулермен іріктеу анағ ұ рлым тезірек жұ мыс істейді.