Сортирање поређењем

Сортирање поређењем је један од алгоритама сортирања који само чита листу елемената кроз једну апстрактну операцију поређења (често "мање или једнако" оператор или троструко поређење) који одређује који од два елемента треба први да се појави у крајњој сортираној листи. Једини захтев је то што оператор поштује две особине линеарног уређења:

ако a ≤ b и b ≤ c онда a ≤ c (транзитивност)
за свако a и b, или a ≤ b или b ≤ a (трихотомија).

Ако је могуће да a ≤ b и b ≤ a; у овом случају један или други могу доћи први у сортирану листу. У , у овом случају улазни редослед одређује сортирани редослед .

Метафора за размишљање о сортирању поређењем је да неко има скуп необележених тегова и вагу (инструмент). Циљ је да поређамо тегове по реду а без икакве информације, осим тога што постављамо два тега на вагу и гледамо шта је теже (или једнако).

Примери[уреди | уреди извор]

Неки од најпознатијих алгоритама поређења укључују:

Ограничења перформанси и предности различитих техника сортирања[уреди | уреди извор]

Постоје основна ограничења за перформансе сортирања поређењем. Сортирање поређењем мора да има просечну доњу границу Ω(n log n) операција поређења ,^[1] што је познато и као линеаритмичко време. Ово је последица ограничења информација доступних кроз сама поређења — или, да га стави другачије, у неодређене алгебарске структуре потпуно уређених скупова. У овом смислу, сортирање спајањем, хипсорт, и интросорт су асимптотички оптимални у смислу броја поређења које морају да одраде, иако ово метрички занемарује друге операције. Сортирања која немају поређења (као што су пример испод) могу да достигну O(n) перформансу коришћењем других операција, допуштајући им да заобиђу ову доњу границу (под претпоставком да су елементи константне величине).

Приметите да сортирање поређењем може бите брже на неким листама; много адаптивних сортирања као што је сортирање уметањем ради у O(n) времену на већ сортираној или полу-сортираној листи. Ω(n log n) доња граница прихвата само случајеве у којима улазна листа може бити у било ком могућем редоследу.

Такође примтите да у стварном животу брзина сортирања зависи и од могућност неких алгоритама да оптимално користе релативно брзу кеш меморију, или апликација може имати користи од метода за сортирање у којој сортиран подаци почињу да се појављују кориснику брже (и онда корисникова брзина читања ће бити ограничен фактор) за разлику од метода сортирања где није доступан излаз за приказивање све док цела листа не буде сортирана.

Упркос овим ограничењима, сортирање поређењем нуди приметну практичну предност која контролише функцију поређења дозвољавајући сортирање веома различитих типова података и добру контролу на сортираној листи. На пример, обртање резултата функције поређења дозвољава листи да буде обрнуто сортирана; и једном се може сортирати листа н-торки у лексикографском поретку тако што правимо функцију поређења која пореди сваки део у секвенци:

function NtorkaPoredjenje((leviA, leviB, leviC), (desniA, desniB, desniC))
    if leviA ≠ desniA
        return compare(leviA, desniA)
    else if leviB ≠ desniB
        return compare(leviB, desniB)
    else
        return compare(leviC, desniC)

Балансирана тернарна нотација омогућава да поређење буде у једном кораку, а резултати буду "мање", "веће" или "једнако".

Сортирање поређењем се генерално прилагођава много лакше комплексном поретку као што је поредак у бројевима са покретним зарезом. Такође, кад се фукција поређења једно напише, било које сортирање поређењем се може искористити без модификације; сортирања без поређења обично зајтевају посебне верзије за сваки тип података.

Ова флексибилност, заједно са ефикасношћу горенаведеног алгоритма сортирања поређењем на савременим рачунарима, довела је до великог коришћења овог алгоритма у разним областима.

Алтернативе[уреди | уреди извор]

Неки проблеми сортирања захтевају искључиво брже решење него $Ω(n log n)$ граница за Сортирање поређењем; пример је целобројно сортирање, где су сви кључеви цели бројеви. Када кључеви чине мали распон, Сортирање пребројавањем је пример алгоритма који ради у ленеарном времену. Остали целобројни алгоритми сортирања, као што је радикс сортирање, нису асимптотички бржи од сортирања поређењем, али у пракси могу бити бржи.

Проблем сортирања парова по њиховом збиру не подлеже $Ω(n ² log n)$ граници или (квадрату резултата упаривања); најбољи познати алгоритам и даље има $O(n ² log n)$ временску сложеност, али само $O(n ²)$ поређења.

Број проређења неопходних за сортирање листе[уреди | уреди извор]

n	$\lceil \log _{2}(n!)\rceil$	Minimum
1	0	0
2	1	1
3	3	3
4	5	5
5	7	7
6	10	10
7	13	13
8	16	16
9	19	19
10	22	22
11	26	26
12	29	30^[2]
13	33	34^[3]
14	37	38^[3]
15	41	42^[4]
16	45	45 or 46^[5]
19	57	58^[4]
22	70	71^[3]

n	$\lceil \log _{2}(n!)\rceil$	$n\log _{2}n-{\frac {n}{\ln 2}}$
10	22	19
100	525	521
1 000	8 530	8 524
10 000	118 459	118 451
100 000	1 516 705	1 516 695
1 000 000	18 488 885	18 488 874

Изнад: Поређење доње границе

\lceil \log _{2}(n!)\rceil

са стварни минимумом броја поређења (од

A036604) који је неопходан за сортирање листе од n елемената. Испод: Помоћу Стирлингове апроксимације, ова доња граница је оптимизована са

n\log _{2}n-{\frac {n}{\ln 2}}

.

Број поређења који овај алгоритам захтева повећање у пропорцији са $n\log(n)$ , где $n$ је број елемената за сортирање. Ова граница је асимптотички мала.

Дата је листа различитих бројеа (можемо претпоставити, пошто нас занима анализа најгорег могућег случаја), постоји n факторијел пермутација, и тачно једана од тих представља сортирану листу. Алгоритам за сортирање мора добити довољно информација из поређења да идентификује тачну пермутацију. Ако се алгоритам увек завршава после f(n) корака, не може да разликује више од 2^f(n) случајева зато што су кључеви различити и свако поређење има само два могућа случаја. Зато,

2^{f(n)}\geq n!

, или еквивалентно

f(n)\geq \log _{2}(n!).

Из Стирлингове апроксимације знамо да $\log _{2}(n!)$ је $\Omega (n\log _{2}n)$ . Ово потврђује тврдњу за доњу границу.

Идентична горња граница следи из алгоритама који достиже ову границу у најгорем случају.

Наведени аргумент омогућује апсолутну, а не само асимптотичку доњу границу броја поређења, тј. $\lceil \log _{2}(n!)\rceil$ поређења. Ова доња граница је стварно добра (може се постићи са простим алгоритмом сортирања спајањем), али је познат да може бити нетачан. На пример, $\lceil \log _{2}(13!)\rceil =33$ , али најмањи број поређења за 13 елемената је 34 (што је доказано).^[3]^[6]

Одређивање тачног броја поређења потребних за сортирање датог броја пријава, је рачунски тежак проблем чак и за мало н, и није позната једноставна формула за решење. За неке од неколико конкретних вредности које су израчунате, види A036604.

Доња граница за просечан број поређења[уреди | уреди извор]

Слична граница важи и за просечан броја поређења. Под претпоставком да

су сви кључеви различити, нпр. свако поређење ће дати или a>b или a<b, и
улаз је случајна пермутација, изабрана јединствено из скупа свих могућих пермутација n елемената,

не могуће је одредити у ком редоследу је улаз мањи од log₂(n!) просеком поређења.

Ово је најлакше приметити помоћу концепта теорије информације. Ентропија тако случајне пермутације је log₂(n!) битова. Пошто поређење може дати само два решења, највећа количина информације коју произведе је 1 бит. Зато, после k поређења преостала ентропија поређења, с обзиром на резултате поређења је бар log₂(n!) - k битова. Да бисмо сортирали, неопходна је комплетна информација, да би преостала ентропија била 0. Из тога следи да k мора бити најмање log₂(n!).

Приметите да се ово разликује од најгоре случаја који је дат горе изнад, смислу да не дозвољава заокруживање на најближи цео број. На пример, за n = 3, најгори случак горње границе је 3, просек за доњу границу је око 2.58, док је највећа доња граница за просечне случајеве око 2.67.

У оваквим случајевима више елемената може имати исти кључ, не постоји очигледна статистичка интерпретација за "просечан случај", тако да аргумент попут овог изнад не може бити примењен без прављења одређених претпоставки о расподели кључева.

Референце[уреди | уреди извор]

^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd изд.). MIT Press and McGraw-Hill. стр. 191—193. ISBN 0-262-03384-4.
^ M. Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971.
^ ^а ^б ^в ^г Marcin Peczarski, New Results in Minimum-Comparison Sorting. Algorithmica 40(2):133-145, 2004.
^ ^а ^б Cheng Weiyi, Liu Xiaoguang, Wang Gang et al. The results of S(15) and S(19) to minimum-comparison sorting problem. Journal of Frontiers of Computer Science and Technology, 2007, 1(3): 305-313.
^ Peczarski, Marcin (3. 8. 2011). „Towards Optimal Sorting of 16 Elements”. arXiv:1108.0866 .
^ Peczarski, Marcin (2007). „The Ford–Johnson algorithm still unbeaten for less than 47 elements”. Information Processing Letters. 101 (3): 126—128. doi:10.1016/j.ipl.2006.09.001.

Литература[уреди | уреди извор]

Knuth, Donald (1997). „Minimum-Comparison Sorting”. The Art of Computer Programming. Volume 3: Addison-Wesley. стр. 180–197. ISBN 978-0-201-89685-5.

[1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd изд.). MIT Press and McGraw-Hill. стр. 191—193. ISBN 0-262-03384-4.

[2] M. Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971.

[Peczarski2004-3] а ^б ^в ^г Marcin Peczarski, New Results in Minimum-Comparison Sorting. Algorithmica 40(2):133-145, 2004.

[ChengLiuWang2007-4] а ^б Cheng Weiyi, Liu Xiaoguang, Wang Gang et al. The results of S(15) and S(19) to minimum-comparison sorting problem. Journal of Frontiers of Computer Science and Technology, 2007, 1(3): 305-313.

[5] Peczarski, Marcin (3. 8. 2011). „Towards Optimal Sorting of 16 Elements”. arXiv:1108.0866 .

[6] Peczarski, Marcin (2007). „The Ford–Johnson algorithm still unbeaten for less than 47 elements”. Information Processing Letters. 101 (3): 126—128. doi:10.1016/j.ipl.2006.09.001.

[1]

[2]

[3]

[4]

[5]

[6]