V algoritmah sortuvannya porivnyannyami dlya otrimannya informaciyi pro roztashuvannya elementiv vhidnoyi poslidovnosti a 1 a 2 a n displaystyle langle a 1 a 2 dots a n rangle vikoristovuyutsya tilki poparni porivnyannya elementiv Inshimi slovami dlya viznachennya vzayemnogo poryadku dvoh elementiv a i displaystyle a i ta a j displaystyle a j vikonuyetsya odna z perevirok a i lt a j a i a j a i a j a i a j displaystyle a i lt a j a i leq a j a i a j a i geq a j abo a i gt a j displaystyle a i gt a j Mi ne mozhemo vikoristovuvati znachennya samih elementiv abo otrimuvati informaciyu pro nih inshim sposobom Sortuvannya nepoznachenih gir za vagoyu vikoristovuyuchi lishe terezi vimagaye algoritmu sortuvannya porivnyannyami Zmist 1 Prikladi 2 Model dereva prijnyattya rishen 3 Nizhnya mezha dlya najgirshoyi shvidkodiyi 4 DzherelaPrikladi red Sortuvannya bulbashkoyu Piramidalne sortuvannya Sortuvannya zlittyam Sortuvannya vklyuchennyam Sortuvannya viborom Shvidke sortuvannya Sortuvannya zmishuvannyamModel dereva prijnyattya rishen red nbsp Derevo prijnyattya rishen dlya sortuvannya vklyuchennyam na troh elementah Vnutrishnij vuzol zapisanij yak i j displaystyle i j nbsp poznachaye porivnyannya mizh a i displaystyle a i nbsp i a j displaystyle a j nbsp List anotovanij perestanovkoyu p 1 p 2 p n displaystyle langle pi 1 pi 2 dots pi n rangle nbsp poznachaye vporyadkuvannya a p 1 a p 2 a p n displaystyle a pi 1 leq a pi 2 leq dots leq a pi n nbsp Vidilenim poznacheni rishennya dlya poslidovnosti a 1 5 a 2 3 a 3 4 displaystyle langle a 1 5 a 2 3 a 3 4 rangle nbsp Perestanovka 3 1 2 displaystyle langle 3 1 2 rangle nbsp oznachaye sho vidsortovanim vporyadkuvannyam ye a 2 3 a 3 4 a 1 5 displaystyle a 2 3 leq a 3 4 leq a 1 5 nbsp Vsogo isnuye 3 6 displaystyle 3 6 nbsp mozhlivih perestanovok vhidnih elementiv i otzhe derevo prijnyattya rishen povinno mati ne menshe 6 displaystyle 6 nbsp listiv Mi mozhemo rozglyadati sortuvannya porivnyannyami abstraktno u terminah dereva prijnyattya rishen Derevo prijnyattya rishen povne dvijkove derevo yake predstavlyaye porivnyannya mizh elementami yaki vikonav pevnij algoritm sortuvannya porivnyannyami na nadanih vhidnih danih Nizhnya mezha dlya najgirshoyi shvidkodiyi red Dovzhina najdovshogo prostogo shlyahu vid korenya do lista predstavlyaye kilkist porivnyan yaki neobhidno vikonati v najgirshomu vipadku Z cogo viplivaye sho kilkist porivnyan v najgirshomu vipadku dlya pevnogo algoritmu sortuvannya porivnyannyami dorivnyuye visoti dereva prijnyattya rishen Nizhnya mezha dlya vsih derev prijnyattya rishen v yakih kozhna perestanovka ye dosyazhnim listom i ye nizhnoyu mezheyu shvidkodiyi dlya bud yakogo algoritmu sortuvannya porivnyannyami Teorema Bud yakij algoritm sortuvannya porivnyannyami v najgirshomu vipadku vimagaye W n lg n displaystyle Omega n lg n nbsp porivnyan Dovedennya Zi skazanogo vishe dostatno viznachiti visotu dereva prijnyattya rishen v yakomu kozhna perestanovka z yavlyayetsya yak dosyazhnij list Rozglyanemo derevo visoti h displaystyle h nbsp z l displaystyle l nbsp dosyazhnimi listami sho vidpovidaye sortuvannyu porivnyannyami dlya n displaystyle n nbsp elementiv Cherez te sho kozhna n displaystyle n nbsp perestanovok vhidnih danih z yavlyayetsya v yakomus listi mi mayemo n l displaystyle n leq l nbsp oskilki povne dvijkove derevo visoti h displaystyle h nbsp maye ne bilshe nizh 2 h displaystyle 2 h nbsp listiv mayemo n l 2 h displaystyle n leq l leq 2 h nbsp sho yaksho prologarifmuvati daye h lg n W n lg n displaystyle h geq lg n Omega n lg n nbsp dlya dovedennya ostannogo rivnyannya zruchno vikoristati formulu Stirlinga v logarifmichnij formi Dzherela red Sortuvannya za linijnij chas Otrimano z https uk wikipedia org w index php title Sortuvannya porivnyannyami amp oldid 35016677
