Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Ред 27:
==Ограничења перформанси и предности различитих техника сортирања==
 
Постоје основна ограничења за перформансе сортирања поређењем. Сортирање поређењем мора да има просечну доњу границу [[big-O notation|Ω]](''n'' log ''n'') операција поређења ,<ref>{{Introduction to Algorithms|3|pages=191–193}}</ref> што је познато и као линеаритмичко време. Ово је последица ограничења информација доступних кроз сама поређења — или, да га стави другачије, у неодређене алгебарске структуре потпуно уређених скупова. У овом смислу, сортирање спајањем, хипсорт, и интросорт су асимптотички оптимални у смислу броја поређења које морају да одраде, иако ово метрички занемарује друге операције. Сортирања која немају поређења (као што су пример испод) могу да достигну [[big-O notation|O]](''n'') перформансу коришћењем других операција, допуштајући им да заобиђу ову доњу границу (под претпоставком да су елементи константне величине).
There are fundamental limits on the performance of comparison sorts. A comparison sort must have an average-case lower bound of [[big-O notation|Ω]](''n'' log ''n'') comparison operations,<ref>{{Introduction to Algorithms|3|pages=191–193}}</ref> which is known as [[linearithmic]] time. This is a consequence of the limited information available through comparisons alone — or, to put it differently, of the vague algebraic structure of totally ordered sets. In this sense, mergesort, heapsort, and introsort are [[asymptotically optimal]] in terms of the number of comparisons they must perform, although this metric neglects other operations. Non-comparison sorts (such as the examples discussed below) can achieve [[big-O notation|O]](''n'') performance by using operations other than comparisons, allowing them to sidestep this lower bound (assuming elements are constant-sized).
 
Note that comparison sorts may run faster on some lists; many [[adaptive sort]]s such as [[insertion sort]] run in O(''n'') time on an already-sorted or nearly-sorted list. The [[big-O notation|Ω]](''n'' log ''n'') lower bound applies only to the case in which the input list can be in any possible order.
Преузето из „https://sr.wikipedia.org/wiki/Сортирање_поређењем”