Википедија

Сортирање поређењем — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Ред 166:
Број поређења који овај алгоритам захтева повећање у пропорцији са <math>n\log(n)</math>, где <math>n</math> је број елемената за сортирање. Ова граница је асимптотички мала.
 
Дата је листа различитих бројеа (можемо претпоставити, пошто нас занима анализа најгорег могућег случаја), постоји ''n'' факторијел пермутација, и тачно једана од тих представља сортирану листу.
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,
Алгоритам за сортирање мора добити довољно информација из поређења да идентификује тачну пермутацију. Ако се алгоритам увек завршава после ''f''(''n'') корака, не може да разликује више од 2<sup>''f''(''n'')</sup> случајева зато што су кључеви различити и свако поређење има само два могућа случаја. Зато,
:<math>2^{f(n)}\geq n!</math>, or equivalently <math>f(n)\geq\log_2(n!).</math>
From [[Stirling's approximation]] we know that :<math>\log_22^{f(n)}\geq n!)</math>, isили еквивалентно <math>\Omegaf(n )\geq\log_2 (n!).</math>. This provides the lower-bound part of the claim.
Из Стирлингове апроксимације знамо да <math>\log_2(n!)</math> је <math>\Omega(n \log_2 n)</math>. Ово потврђује тврдњу за доњу границу.
 
Идентична горња граница следи из алгоритама који достиже ову границу у најгорем случају.
An identical upper bound follows from the existence of the algorithms that attain this bound in the worst case.
 
Наведени аргумент омогућује'' апсолутну'', а не само асимптотичку доњу границу броја поређења, тј. <math>\lceil\log_2(n!)\rceil</math> поређења. Ова доња граница је стварно добра (може се постићи са простим алгоритмом сортирања спајањем), али је познат да може бити нетачан. На пример, <math>\lceil\log_2(13!)\rceil=33</math>, али најмањи број поређења за 13 елемената је 34 (што је доказано).<ref name="Peczarski2004" /><ref>Marcin Peczarski: The Ford-Johnson algorithm is still unbeaten for less than 47 elements. Inf. Process. Lett. 101(3): 126-128 (2007) {{doi|10.1016/j.ipl.2006.09.001}}</ref>
The above argument provides an ''absolute'', rather than only asymptotic lower bound on the number of comparisons, namely <math>\lceil\log_2(n!)\rceil</math> comparisons. This lower bound is fairly good (it can be approached within a linear tolerance by a simple merge sort), but it is known to be inexact. For example, <math>\lceil\log_2(13!)\rceil=33</math>, but the minimal number of comparisons to sort 13 elements has been proved to be 34
.<ref name="Peczarski2004" /><ref>Marcin Peczarski: The Ford-Johnson algorithm is still unbeaten for less than 47 elements. Inf. Process. Lett. 101(3): 126-128 (2007) {{doi|10.1016/j.ipl.2006.09.001}}</ref>
 
Determining the ''exact'' number of comparisons needed to sort a given number of entries is a computationally hard problem even for small ''n'', and no simple formula for the solution is known. For some of the few concrete values that have been computed, see {{OEIS2C|id=A036604}}.
Преузето из „https://sr.wikipedia.org/wiki/Сортирање_поређењем”