Sharof rashidov nomidagi samarqand davlat universiteti amaliy matematika yo

1.1 Taqqoslanmaydigan turlar

Ba'zi algoritmlar yuqorida muhokama qilinganlarga nisbatan sust, masalan bogosort cheklanmagan ish vaqti va stoge sort qaysi bor O(n^2.7) ishlash vaqti. Ushbu turlar odatda algoritmlarning ishlash vaqtini qanday baholashini ko'rsatish uchun ta'lim maqsadida tavsiflanadi. An'anaviy dasturiy ta'minot kontekstida real hayotda foydalanish uchun foydasiz bo'lgan ba'zi bir saralash algoritmlari quyidagi jadvalda juda yomon ishlashi yoki ixtisoslashtirilgan apparat talablari tufayli tasvirlangan.

Nazariy kompyuter olimlari, bundan yaxshiroqini ta'minlaydigan boshqa saralash algoritmlarini batafsil bayon qildilar O(n jurnal n) qo'shimcha cheklovlarni o'z ichiga olgan vaqtning murakkabligi, shu jumladan:
Mashhur saralash algoritmlari
Saralash algoritmlari juda ko'p bo'lsa-da, amaliy dasturlarda bir nechta algoritmlar ustunlik qiladi. Kiritish saralashi kichik ma'lumotlar to'plamlari uchun keng qo'llaniladi, katta ma'lumotlar to'plamlari uchun asimptotik jihatdan samarali saralash, birinchi navbatda, yig'indilarni saralash, birlashtirish tartiblari yoki tezkorlar. Samarali dasturlar odatda a dan foydalanadi gibrid algoritm, umumiy saralash uchun asimptotik jihatdan samarali algoritmni rekursiyaning pastki qismidagi kichik ro'yxatlar uchun qo'shish bilan birlashtirish. Yuqori darajada sozlangan dasturlar kabi murakkab variantlardan foydalaniladi, masalan Timsort (birlashtirish saralash, qo'shish tartibini va qo'shimcha mantiq), Android, Java va Python-da ishlatiladigan va introsort (quicksort va heap sort), ba'zilarida ishlatilgan (variant shaklida) C ++ saralash dasturlari va .NET-da.
Belgilangan oraliqdagi raqamlar kabi cheklangan ma'lumotlar uchun, tarqatish turlari sanash sort yoki radix sort kabi keng qo'llaniladi. Bubble sort va variantlari amalda kamdan kam qo'llaniladi, lekin odatda o'quv va nazariy munozaralarda uchraydi.
Ob'ektlarni jismoniy tartiblashda (masalan, qog'ozlar, testlar yoki kitoblar) alfavit qilishda odamlar intuitiv ravishda odatda kichik to'plamlar uchun qo'shilish turlaridan foydalanadilar. Kattaroq to'plamlar uchun odamlar ko'pincha birinchi chelakni, masalan, boshlang'ich harflar bilan, va bir nechta chelaklar juda katta to'plamlarni amaliy saralashga imkon beradi. Ko'pincha bo'shliq nisbatan arzon, masalan, erga yoki katta maydonga narsalarni yoyish, ammo operatsiyalar qimmatga tushadi, ayniqsa ob'ektni uzoq masofaga ko'chirish - mos yozuvlar joylashuvi muhim ahamiyatga ega. Birlashtirish turlari jismoniy ob'ektlar uchun ham amaliydir, chunki ikkita qo'l ishlatilishi mumkin, har bir ro'yxat birlashtirilishi mumkin, boshqa algoritmlar, masalan, yig'ish tartibida yoki tezkor tartiblash, odam uchun juda mos emas. Kabi boshqa algoritmlar kutubxona, bo'sh joy qoldiradigan qo'shilish tartibining bir varianti ham jismoniy foydalanish uchun amaliydir.
Oddiy navlar
Eng oddiy ikkita turdan biri - qo'shimchalarni saralash va tanlash saralashi, ikkalasi ham kichik ma'lumotlarda samarali bo'ladi, chunki qo'shimcha xarajatlar past, ammo katta ma'lumotlarda samarali emas. Kiritish saralashi amalda tanlov saralashiga qaraganda tezroq bo'ladi, chunki taqqoslashlar kamligi va deyarli saralangan ma'lumotlarda yaxshi ishlashi va shuning uchun amalda afzal ko'rilgan, ammo tanlov saralash kamroq yozishlardan foydalanadi va shu bilan yozish ishlashi cheklovchi omil bo'lganda ishlatiladi.
Kiritish tartibi
Asosiy maqola:
Kiritish tartibi kichik saralashlar va asosan saralangan ro'yxatlar uchun nisbatan samarali bo'lgan va ko'pincha murakkab algoritmlarning bir qismi sifatida ishlatiladigan oddiy saralash algoritmidir. Bu ro'yxatdagi elementlarni birma-bir olish va ularni o'zlarining to'g'ri holatiga hamyonimizga qanday pul qo'yishimizga o'xshash yangi tartiblangan ro'yxatga kiritish orqali ishlaydi.^[22] Massivda yangi ro'yxat va qolgan elementlar massivning bo'sh joyini bo'lishishi mumkin, ammo kiritish juda qimmat, shuning uchun quyidagi barcha elementlarni birma-bir almashtirish kerak. Shellsort (quyida ko'rib chiqing) - bu katta ro'yxatlar uchun samaraliroq bo'lgan qo'shilish tartibining bir variantidir.
Tanlov tartibida
Asosiy maqola:
Tanlov tartibida bu joyida taqqoslash. Unda bor O (n²) murakkabligi, uni katta ro'yxatlarda samarasiz qiladi va umuman o'xshashidan yomonroq ishlaydi qo'shish tartibi. Tanlovni saralash soddaligi bilan ajralib turadi, shuningdek, muayyan vaziyatlarda murakkab algoritmlarga nisbatan ishlashning afzalliklariga ega.
Algoritm minimal qiymatni topadi, uni birinchi holatdagi qiymat bilan almashtiradi va ro'yxatning qolgan qismida ushbu amallarni takrorlaydi.^[23] Bu ko'proq emas n almashtirish, shuning uchun almashtirish juda qimmat bo'lgan joyda foydalidir.
Samarali navlar
Amaliy umumiy saralash algoritmlari deyarli har doim o'rtacha vaqt murakkabligi (va umuman olganda eng yomon holatdagi murakkablik) algoritmiga asoslanadi.n jurnal n), ulardan eng keng tarqalgani - yig'ma saralash, birlashma va tezkor tortish. Ularning har birining afzalliklari va kamchiliklari bor, eng muhimi, birlashma tartibini oddiy amalga oshirish O (n) qo'shimcha maydon va tezkor kortni oddiy bajarish O (n²) eng yomon murakkablik. Ushbu muammolarni yanada murakkab algoritm evaziga hal qilish yoki yaxshilash mumkin.
Ushbu algoritmlar tasodifiy ma'lumotlarda asimptotik jihatdan samarali bo'lsa, real ma'lumotlar uchun amaliy samaradorlik uchun turli xil modifikatsiyalar qo'llaniladi. Birinchidan, ushbu algoritmlarning qo'shimcha xarajatlari kichikroq ma'lumotlarda muhim ahamiyat kasb etadi, shuning uchun ko'pincha gibrid algoritm ishlatiladi, odatda ma'lumotlar etarlicha kichik bo'lgandan so'ng qo'shish tartibiga o'tadi. Ikkinchidan, algoritmlar allaqachon saralangan ma'lumotlar yoki deyarli saralangan ma'lumotlarda yomon ishlaydi - bular real dunyo ma'lumotlarida keng tarqalgan va ularni O (n) tegishli algoritmlar bo'yicha vaqt. Nihoyat, ular ham bo'lishi mumkin beqaror va barqarorlik ko'pincha biron bir tarzda kerakli xususiyatdir. Shunday qilib, ko'pincha murakkab algoritmlardan foydalaniladi, masalan Timsort (birlashma tartibiga asoslangan) yoki introsort (tez yig'ilishga asoslangan holda, yana uyumga tushish).
Saralashni birlashtirish
Asosiy maqola:
Saralashni birlashtirish allaqachon saralangan ro'yxatlarni yangi tartiblangan ro'yxatga birlashtirish qulayligidan foydalanadi. Har ikkala elementni taqqoslash bilan boshlanadi (ya'ni, 1 bilan 2, keyin 3 bilan 4 ...) va agar birinchisi ikkinchisidan keyin kelishi kerak bo'lsa, ularni almashtirish. Keyinchalik, natijada olingan ikkita ro'yxatning har birini to'rtta ro'yxatga birlashtiradi, so'ngra to'rtta ro'yxatni birlashtiradi va hokazo; oxirgi ikki ro'yxat yakuniy saralangan ro'yxatga birlashtirilguncha.^[24] Bu erda tavsiflangan algoritmlardan biri bu juda katta ro'yxatlarning o'lchovidir, chunki uning eng yomon ish vaqti O (n jurnal n). Bundan tashqari, u nafaqat massivlarga, balki ro'yxatlarga ham osonlikcha qo'llaniladi, chunki u tasodifiy kirishni emas, balki ketma-ket kirishni talab qiladi. Biroq, u qo'shimcha O (n) kosmik murakkablik va oddiy dasturlarda juda ko'p nusxalarni o'z ichiga oladi.
Birlashtirish navi murakkab algoritmda ishlatilganligi sababli amaliy qo'llanmalar uchun nisbatan yaqinda ommalashgan Timsort, bu dasturlash tillarida standart tartib uchun ishlatiladi Python^[25] va Java (sifatida JDK7^[26]). Birlashtirish tartibining o'zi odatdagi tartibdir Perl,^[27] boshqalar qatorida va kamida 2000 yildan beri Java-da ishlatilgan JDK1.3.^[28]
Heapsort
Asosiy maqola:
Heapsort ning ancha samarali versiyasidir tanlov saralash. Shuningdek, u ro'yxatning eng katta (yoki eng kichik) elementini aniqlab, ro'yxatning oxiriga (yoki boshiga) qo'yib, so'ngra ro'yxatning qolgan qismida davom etish orqali ishlaydi, ammo bu vazifani a deb nomlangan ma'lumotlar tuzilishi yordamida samarali bajaradi. uyum, maxsus turi ikkilik daraxt.^[29] Ma'lumotlar ro'yxati uyumga aylantirilgandan so'ng, ildiz tuguni eng katta (yoki eng kichik) element bo'lishiga kafolat beradi. U olib tashlanib, ro'yxatning oxiriga qo'yilganda, uyum qayta tartibga solinadi, shunda qolgan eng katta element ildizga o'tadi. To'pni ishlatib, keyingi eng katta elementni topish O (log) ni oladi n) O, o'rniga vaqt (n) oddiy tanlov tartibidagi kabi chiziqli skanerlash uchun. Bu Heapsort-ga O (n jurnal n) vaqt, va bu ham eng yomon murakkablik.
Asosiy maqola: Quicksort
Quicksort a algoritmni ajratish va yutish a ga asoslangan bo'lim operatsiya: massivni ajratish, element deb nomlangan burilish tanlangan.^[30][31] Burilishdan kichik bo'lgan barcha elementlar undan oldin va barcha katta elementlar undan keyin harakatlanadi. Buni chiziqli vaqt ichida samarali bajarish mumkin va joyida. Keyinchalik kichik va katta sublistlar rekursiv tartibda saralanadi. Bu o'rtacha vaqt murakkabligini O (n jurnal n), kam xarajatli va shuning uchun bu mashhur algoritm. Quicksort-ning samarali qo'llanilishi (joyida bo'linish bilan) odatda beqaror va biroz murakkab, ammo amalda eng tez tartiblash algoritmlari qatoriga kiradi. Uning oddiy O (log) bilan birga n) bo'sh joydan foydalanish, tezkor saralash eng mashhur saralash algoritmlaridan biri bo'lib, ko'plab standart dasturlash kutubxonalarida mavjud.
Quicksort haqida muhim ogohlantirish shundaki, uning eng yomon ko'rsatkichi O (n²); Bu kamdan-kam hollarda, sodda dasturlarda (birinchi yoki oxirgi elementni pivot sifatida tanlash) bu tartiblangan ma'lumotlar uchun sodir bo'ladi, bu odatiy hol. Quicksortdagi eng murakkab masala - bu yaxshi burilish elementini tanlashdir, chunki burilishlarning doimiy ravishda yomon tanlovi O ning pasayishiga olib kelishi mumkin (n²) ishlash, lekin pivotlarni yaxshi tanlash O (n jurnal n) asimptotik jihatdan maqbul bo'lgan ishlash. Masalan, agar har bir qadamda o'rtacha burilish sifatida tanlanadi, keyin algoritm O (n jurnaln). Kabi mediani topish medianlar medianasi tanlash algoritmi ammo O (n) tartiblanmagan ro'yxatlarda ishlash va shuning uchun saralash bilan katta xarajatlarni amalga oshiradi. Amalda tasodifiy burilishni tanlash deyarli aniq O (n jurnaln) ishlash.