Сортирање поређењем — разлика између измена
Садржај обрисан Садржај додат
Ред 159:
|}
<div class="thumbcaption">
Изнад: Поређење доње границе <math>\lceil\log_2(n!)\rceil</math> са стварни минимумом броја поређења (од {{OEIS2C|id=A036604}}) који је неопходан за сортирање листе од ''n'' елемената. Испод: Помоћу Стирлингове апроксимације, ова доња граница је оптимизована са <math>n \log_2 n - \frac{n} {\ln 2}</math>.</div>
</div>
</div>
Број поређења који овај алгоритам захтева повећање у пропорцији са <math>n\log(n)</math>, где <math>n</math> је број елемената за сортирање. Ова граница је асимптотички мала.
Given a list of distinct numbers (we can assume this because this is a worst-case analysis), there are ''n'' [[factorial]] permutations exactly one of which is the list in sorted order. The sort algorithm must gain enough information from the comparisons to identify the correct permutation. If the algorithm always completes after at most ''f''(''n'') steps, it cannot distinguish more than 2<sup>''f''(''n'')</sup> cases because the keys are distinct and each comparison has only two possible outcomes. Therefore,
| |||