202-“kidt” guruhi talabasi Iskandarov Otaxonning algoritmlar va berilganlar strukturasi fanidan tayyorlagan mustaqil ishi mavzu: Saralash algoritmlari. Saralash algoritmlarini murakkablikini baholash. Kvadratik

Urganch Davlat Universiteti
202-“KIDT” guruhi talabasi Iskandarov Otaxonning algoritmlar va berilganlar strukturasi fanidan tayyorlagan


MUSTAQIL ISHI


Mavzu: Saralash algoritmlari. Saralash algoritmlarini murakkablikini baholash. Kvadratik, logarifmik va chiziqli qiyinlikdagi saralash algoritmlari.
2022y
Informatikada saralash algoritmi ro‘yxat elementlarini tartib bilan joylashtiradigan algoritmdir. Eng ko'p ishlatiladigan tartiblar son tartibi va leksikografik tartib va ​​o'sish yoki kamayishdir. Samarali saralash kirish ma'lumotlarining saralangan ro'yxatlarda bo'lishini talab qiladigan boshqa algoritmlarning (masalan, qidirish va birlashtirish algoritmlari) samaradorligini optimallashtirish uchun muhimdir. Saralash ko'pincha ma'lumotlarni kanoniklashtirish va odam o'qiy oladigan natijalarni ishlab chiqarish uchun foydalidir.

Rasmiy ravishda, har qanday tartiblash algoritmining chiqishi ikkita shartni qondirishi kerak:

Chiqarish monotonik tartibda (har bir element oldingi elementdan kichikroq/katta emas, kerakli tartibda).
Chiqish - bu kirishning almashtirish (qayta tartiblash, lekin barcha asl elementlarni saqlab qolish).
Optimal samaradorlik uchun kiritilgan ma'lumotlar faqat ketma-ket kirishga ruxsat beruvchi emas, balki tasodifiy kirish imkonini beruvchi ma'lumotlar tuzilmasida saqlanishi kerak.
Saralash algoritmlarini quyidagicha tasniflash mumkin:

Hisoblashning murakkabligi

Ro'yxat hajmi bo'yicha eng yaxshi, eng yomon va o'rtacha ish harakati. Oddiy ketma-ket tartiblash algoritmlari uchun yaxshi xatti-harakatlar O(n log n), parallel tartiblash O(log2 n) da, yomon xulq esa O(n2). Ketma-ket tartiblash uchun ideal harakat O(n), lekin o'rtacha holatda bu mumkin emas. Optimal parallel tartiblash O(log n) dir.
"O'z joyida" algoritmlarga almashtiriladi.
Xotiradan foydalanish (va boshqa kompyuter resurslaridan foydalanish). Xususan, ba'zi tartiblash algoritmlari "o'z joyida". To'g'rirog'i, o'z o'rnida tartiblash uchun saralanadigan elementlardan tashqari faqat O(1) xotira kerak; ba'zan O(log n) qo'shimcha xotira "o'z joyida" deb hisoblanadi.
Rekursiya: Ba'zi algoritmlar rekursiv yoki rekursiv bo'lmagan, boshqalari esa ikkalasi ham bo'lishi mumkin (masalan, birlashtirish tartibi).
Barqarorlik: barqaror tartiblash algoritmlari teng kalitlar (ya'ni, qiymatlar) bilan yozuvlarning nisbiy tartibini saqlaydi.
Ular taqqoslash turimi yoki yo'qmi. Taqqoslash tartiblash ma'lumotlarni faqat ikkita elementni taqqoslash operatori bilan solishtirish orqali tekshiradi.
Umumiy usul: kiritish, almashish, tanlash, birlashtirish va h.k. Almashtirish turlariga pufakchali tartiblash va tezkor saralash kiradi. Tanlov turlariga sikllarni saralash va yig'ish saralash kiradi.
Algoritm ketma-ket yoki parallel bo'ladimi. Ushbu munozaraning qolgan qismi deyarli faqat ketma-ket algoritmlarga qaratiladi va ketma-ket ishlashni o'z ichiga oladi.
Moslashuvchanlik: kirishning oldindan saralanganligi ish vaqtiga ta'sir qiladimi yoki yo'qmi. Buni inobatga olgan algoritmlar adaptiv ekanligi ma'lum.
Onlayn: Onlayn bo'lgan Insertion Sort kabi algoritm doimiy kirish oqimini saralashi mumkin.
Ommabop tartiblash algoritmlari
Saralash algoritmlari juda ko'p bo'lsa-da, amaliy dasturlarda bir nechta algoritmlar ustunlik qiladi. Kichkina ma'lumotlar to'plamlari uchun qo'shish tartibi keng qo'llaniladi, katta ma'lumotlar to'plamlari uchun esa asimptotik jihatdan samarali saralash, birinchi navbatda, yig'ish, birlashtirish yoki tezkor saralash qo'llaniladi. Samarali ilovalar odatda gibrid algoritmdan foydalanadi, bu umumiy tartib uchun asimptotik jihatdan samarali algoritm bilan rekursiyaning pastki qismidagi kichik ro'yxatlar uchun qo'shish tartiblarini birlashtiradi. Yuqori darajada sozlangan ilovalar Android, Java va Python-da qoʻllaniladigan Timsort (birlashtirish, qoʻshish tartibi va qoʻshimcha mantiq) va baʼzi C++ sortlarida qoʻllaniladigan introsort (tezkor va yigʻma saralash) kabi murakkabroq variantlardan foydalanadi. ilovalar va .NET da.

Ruxsat etilgan oraliqdagi raqamlar kabi cheklangan ma'lumotlar uchun hisoblash tartiblash yoki radix tartiblash kabi tarqatish turlari keng qo'llaniladi. Bubble sort va variantlar amalda kamdan-kam qo'llaniladi, lekin odatda o'qitish va nazariy munozaralarda topiladi.

Ob'ektlarni jismonan saralashda (masalan, qog'ozlar, testlar yoki kitoblar alifbo tartibida) odamlar intuitiv ravishda kichik to'plamlar uchun kiritish tartiblaridan foydalanadilar. Kattaroq to'plamlar uchun odamlar odatda birinchi chelak, masalan, bosh harf bilan, va bir nechta chelaklar juda katta to'plamlarni amaliy saralash imkonini beradi. Ko'pincha bo'sh joy nisbatan arzon, masalan, ob'ektlarni polga yoki katta maydonga yoyish, lekin operatsiyalar qimmatga tushadi, ayniqsa ob'ektni katta masofaga ko'chirish - mos yozuvlar joyi muhim ahamiyatga ega. Birlashtirish turlari jismoniy ob'ektlar uchun ham amaliydir, ayniqsa ikkita qo'ldan foydalanish mumkin, har bir ro'yxatni birlashtirish uchun bittadan, boshqa algoritmlar, masalan, yig'ish yoki tezkor saralash odamlar uchun juda mos emas. Boshqa algoritmlar, masalan, kutubxona tartiblash, bo'sh joy qoldiradigan qo'shish turining varianti ham jismoniy foydalanish uchun amaliydir.
Oddiy turlar
Eng oddiy turlardan ikkitasi qoʻshish saralash va tanlash saralash boʻlib, ularning har ikkalasi ham kichik maʼlumotlarda samarali boʻladi, chunki kam yuk tufayli, lekin katta maʼlumotlarda samarali emas. Taqqoslashning kamroqligi va deyarli saralangan ma'lumotlarda yaxshi ishlashi tufayli qo'shish saralash amalda odatda tanlagan saralashdan tezroq bo'ladi va shuning uchun amalda afzal ko'riladi, lekin tanlash saralash kamroq yozishni ishlatadi va shuning uchun yozish samaradorligi cheklovchi omil bo'lsa ishlatiladi.

Kiritish tartibi

Asosiy maqola: Kiritish tartibi
Qo'shish tartibi - kichik ro'yxatlar va asosan tartiblangan ro'yxatlar uchun nisbatan samarali bo'lgan oddiy tartiblash algoritmi va ko'pincha murakkabroq algoritmlarning bir qismi sifatida ishlatiladi. U roʻyxatdagi elementlarni birma-bir olib, ularni toʻgʻri oʻrnida yangi tartiblangan roʻyxatga kiritish orqali ishlaydi, xuddi biz hamyonimizga pul qoʻyishimiz kabi.[19] Massivlarda yangi roʻyxat va qolgan elementlar massivning boʻsh joyini boʻlishishi mumkin, lekin qoʻshish qimmat boʻlib, keyingi barcha elementlarni bittaga siljitishni talab qiladi. Shellsort - bu kattaroq ro'yxatlar uchun samaraliroq bo'lgan qo'shish tartibining variantidir.

Tanlash tartibi

Asosiy maqola: Tanlash tartibi
Tanlangan saralash joyida taqqoslash turidir. U O(n2) murakkabligiga ega boʻlib, uni katta roʻyxatlarda samarasiz qiladi va odatda oʻxshash qoʻshish turiga qaraganda yomonroq ishlaydi. Tanlash tartibi soddaligi bilan ajralib turadi, shuningdek, muayyan vaziyatlarda murakkabroq algoritmlarga nisbatan ishlash afzalliklariga ega.

Algoritm minimal qiymatni topadi, uni birinchi o'rindagi qiymat bilan almashtiradi va ro'yxatning qolgan qismi uchun bu amallarni takrorlaydi.[20] U n dan ortiq almashtirishni amalga oshirmaydi va shuning uchun almashtirish juda qimmat bo'lgan joyda foydalidir.

Samarali turlar
Amaliy umumiy saralash algoritmlari deyarli har doim oʻrtacha vaqt murakkabligi (va umuman, eng yomon holat murakkabligi) O(n log n) boʻlgan algoritmga asoslanadi, ulardan eng keng tarqalganlari yigʻma saralash, birlashtirish va tezkor saralashdir. Ularning har birining afzalliklari va kamchiliklari bor, eng muhimi, birlashtirish tartibini oddiy amalga oshirish O(n) qo‘shimcha joyni ishlatadi va tezkor saralashning oddiy amalga oshirilishi O(n2) eng yomon murakkablikka ega. Ushbu muammolarni yanada murakkab algoritm yordamida hal qilish yoki yaxshilash mumkin.

Ushbu algoritmlar tasodifiy ma'lumotlarda asimptotik jihatdan samarali bo'lsa-da, real dunyo ma'lumotlarida amaliy samaradorlik uchun turli xil modifikatsiyalar qo'llaniladi. Birinchidan, bu algoritmlarning qo'shimcha xarajatlari kichikroq ma'lumotlar uchun ahamiyatli bo'ladi, shuning uchun ko'pincha gibrid algoritm qo'llaniladi, odatda ma'lumotlar etarlicha kichik bo'lsa, kiritish tartibiga o'tadi. Ikkinchidan, algoritmlar ko'pincha tartiblangan ma'lumotlar yoki deyarli saralangan ma'lumotlar bo'yicha yomon ishlaydi - bular real dunyo ma'lumotlarida keng tarqalgan va tegishli algoritmlar bilan O(n) vaqtida saralanishi mumkin. Va nihoyat, ular ham beqaror bo'lishi mumkin va barqarorlik ko'pincha istalgan xususiyatdir. Shunday qilib, ko'pincha Timsort (birlashma saralash asosida) yoki introsort (tezkor saralash asosida, yig'indisiga qaytish) kabi yanada murakkab algoritmlar qo'llaniladi.

Birlashtirish tartibi
Asosiy maqola: Birlashtirish tartibi
Birlashtirish tartibi allaqachon tartiblangan roʻyxatlarni yangi tartiblangan roʻyxatga birlashtirish qulayligidan foydalanadi. Bu har ikki elementni solishtirishdan boshlanadi (ya'ni, 1 bilan 2, keyin 3 bilan 4 ...) va agar birinchisi ikkinchidan keyin kelishi kerak bo'lsa, ularni almashtirish. Keyin u ikkitadan iborat ro'yxatlarning har birini to'rtta ro'yxatlarga birlashtiradi, so'ngra to'rtta ro'yxatni birlashtiradi va hokazo; oxirgi ikki roʻyxat yakuniy tartiblangan roʻyxatga birlashtirilguncha.[21] Bu erda tasvirlangan algoritmlardan birinchisi, bu juda katta ro'yxatlar uchun yaxshi o'lchovdir, chunki uning eng yomon ish vaqti O (n log n) dir. U nafaqat massivlarga, balki ro'yxatlarga ham oson qo'llaniladi, chunki u tasodifiy kirishni emas, balki faqat ketma-ket kirishni talab qiladi. Biroq, u qo'shimcha O(n) fazoviy murakkablikka ega va oddiy ilovalarda ko'p sonli nusxalarni o'z ichiga oladi.

Python[22] va Java dasturlash tillarida (JDK7[23] holatiga ko'ra) standart tartiblash uchun qo'llaniladigan murakkab Timsort algoritmida qo'llanilganligi sababli, birlashtirish sorti amaliy qo'llash uchun nisbatan yaqinda ommalashdi. . Birlashtirish tartibining o'zi boshqalar qatori Perlda[24] standart tartibdir va Java-da kamida 2000-yildan beri JDK1.3 da qo'llaniladi.[25]

Yigʻma tartib
Asosiy maqola: Heapsort
Heapsort - bu tanlashning ancha samarali versiyasi. Shuningdek, u roʻyxatning eng katta (yoki eng kichik) elementini aniqlash, uni roʻyxatning oxiriga (yoki boshiga) qoʻyish, soʻngra qolgan qismi bilan davom etish orqali ishlaydi, lekin bu vazifani a maʼlumotlar strukturasi yordamida samarali bajaradi. toʻp, ikkilik daraxtning maxsus turi.[26] Maʼlumotlar roʻyxati yigʻma holga keltirilgach, ildiz tugunining eng katta (yoki eng kichik) element boʻlishi kafolatlanadi. U olib tashlangan va ro'yxatning oxiriga qo'yilsa, yig'ma qolgan eng katta element ildizga o'tishi uchun qayta tartibga solinadi. Uyumdan foydalanib, keyingi eng katta elementni topish oddiy tanlashda bo'lgani kabi chiziqli skanerlash uchun O(n) o'rniga O(log n) vaqtni oladi. Bu Heapsort-ga O(n log n) vaqtida ishlashiga imkon beradi va bu ham eng yomon holat murakkabligi.

Tez tartiblash

Asosiy maqola: Quicksort
Quicksort — boʻlish va boʻysundirish algoritmi boʻlib, u boʻlish operatsiyasiga tayanadi: massivni boʻlish uchun pivot deb nomlangan element tanlanadi.[27][28] Pivotdan kichikroq barcha elementlar undan oldin, kattaroq elementlar esa undan keyin ko'chiriladi. Buni chiziqli vaqtda va joyida samarali bajarish mumkin. Keyinchalik kichik va katta pastki ro'yxatlar rekursiv saralanadi. Bu O(n log n) ning oʻrtacha vaqt murakkabligini, kam qoʻshimcha xarajatlarni beradi va shuning uchun bu mashhur algoritmdir. Tez saralashning samarali tatbiq etilishi (joyida bo'linish bilan) odatda beqaror va biroz murakkab, lekin amalda eng tez saralash algoritmlari qatoriga kiradi. O'zining oddiy O(log n) bo'sh joydan foydalanishi bilan bir qatorda, Quicksort eng mashhur tartiblash algoritmlaridan biri bo'lib, ko'plab standart dasturlash kutubxonalarida mavjud.

Tezkor saralash haqida muhim ogohlantirish shundaki, uning eng yomon ishlashi O(n2); Bu kamdan-kam bo'lsa-da, sodda ilovalarda (birinchi yoki oxirgi elementni pivot sifatida tanlash) bu tartiblangan ma'lumotlar uchun sodir bo'ladi, bu odatiy holdir. Tezkor saralashdagi eng murakkab masala bu yaxshi aylanma elementni tanlashdir, chunki pivotlarning doimiy ravishda yomon tanlanishi O(n2) unumdorligini keskin pasaytirishi mumkin, biroq pivotlarning yaxshi tanlanishi O(n log n) unumdorligini beradi, bu asimptotik jihatdan optimaldir. Misol uchun, agar har bir qadamda mediana pivot sifatida tanlansa, algoritm O(n log n) da ishlaydi. Medianlarni, masalan, medianlarning medianasi bo'yicha tanlash algoritmini topish saralanmagan ro'yxatlar bo'yicha O(n) operatsiyasi bo'lib, shuning uchun saralash uchun katta xarajatlarni talab qiladi. Amalda tasodifiy pivotni tanlash deyarli O(n log n) unumdorligini beradi.

Shellsort

Shellsort, qabariqli tartibdan farq qiladi, chunki u elementlarni ko'plab almashuv joylariga o'tkazadi.

Asosiy maqola: Shellsort
Shellsort 1959 yilda Donald Shell tomonidan ixtiro qilingan.[29] Bu tartibsiz elementlarni bir vaqtning o'zida bir nechta pozitsiyaga ko'chirish orqali joylashtirish saralashda yaxshilanadi. Shellsort kontseptsiyasi shundan iboratki, qo'shish tartiblash {\displaystyle O(kn)}O(kn) vaqt ichida amalga oshiriladi, bu erda k - ikkita joydan tashqari element orasidagi eng katta masofa. Bu shuni anglatadiki, ular odatda O(n2) da ishlaydi, lekin faqat bir nechta elementlar joyida bo'lmagan holda, asosan tartiblangan ma'lumotlar uchun ular tezroq ishlaydi. Shunday qilib, birinchi navbatda elementlarni uzoqdan saralash va saralash uchun elementlar orasidagi bo'shliqni bosqichma-bosqich qisqartirish orqali yakuniy saralash tezroq hisoblab chiqadi. Bitta dasturni ikki o'lchovli massivda ma'lumotlar ketma-ketligini tartibga solish va keyin qo'shish tartibidan foydalanib massiv ustunlarini saralash sifatida tavsiflash mumkin.

Shellsort-ning eng yomon vaqt murakkabligi ochiq muammo bo'lib, ishlatiladigan bo'shliqlar ketma-ketligiga bog'liq bo'lib, ma'lum murakkabliklari O(n2) dan O(n4/3) va D(n log2 n) gacha. Bu Shellsort o'z o'rnida ekanligi bilan birga, faqat nisbatan kichik miqdordagi kodni talab qiladi va qo'ng'iroqlar to'plamidan foydalanishni talab qilmaydi, uni xotira yuqori bo'lgan holatlarda, masalan, o'rnatilgan tizimlarda foydali qiladi. va operatsion tizim yadrolari.

Pufakchani saralash va variantlari
Pufakcha tartiblash va Shellsort va kokteyl kabi variantlar oddiy, juda samarasiz tartiblash algoritmlaridir. Ular tahlil qilish qulayligi tufayli kirish matnlarida tez-tez uchraydi, lekin amalda kamdan-kam qo'llaniladi.

Pufakcha tartiblash

Pufakchali saralash, saralash algoritmi roʻyxat boʻylab doimiy ravishda qadam tashlab, elementlarni toʻgʻri tartibda paydo boʻlguncha almashtiradi.
Asosiy maqola: Pufakchani saralash
Bubble sort oddiy tartiblash algoritmidir. Algoritm ma'lumotlar to'plamining boshidan boshlanadi. U birinchi ikkita elementni taqqoslaydi va agar birinchisi ikkinchisidan katta bo'lsa, ularni almashtiradi. U ma'lumotlar to'plamining oxirigacha bo'lgan har bir qo'shni elementlar juftligi uchun buni davom ettiradi. So‘ngra u dastlabki ikki element bilan qaytadan boshlanadi va oxirgi o‘tishda hech qanday almashtirish sodir bo‘lmaguncha takrorlanadi.[30] Bu algoritmning oʻrtacha vaqti va eng yomon holatda ishlashi O(n2) dir, shuning uchun u katta, tartibsiz maʼlumotlar toʻplamlarini saralash uchun kamdan-kam qoʻllaniladi. Bubble sort kichik sonli elementlarni saralash uchun ishlatilishi mumkin (uning asimptotik samarasizligi yuqori jazo emas). Pufakcha saralash deyarli tartiblangan har qanday uzunlik ro'yxatida ham samarali ishlatilishi mumkin (ya'ni, elementlar sezilarli darajada joylashmagan). Misol uchun, agar biron-bir sonli elementlar faqat bitta pozitsiyaga mos kelmasa (masalan, 0123546789 va 1032547698), qabariqli tartib almashish ularni birinchi o'tishda tartibda oladi, ikkinchi o'tish esa barcha elementlarni tartibda topadi, shuning uchun tartiblash faqat 2n vaqtni oling.
Taroqli saralash
Asosiy maqola: Taroqli saralash
Taroqli saralash pufakchali saralashga asoslangan nisbatan oddiy tartiblash algoritmi boʻlib, dastlab 1980-yilda Vłodzimierz Dobosiewicz tomonidan ishlab chiqilgan.[32] Keyinchalik u Stiven Leysi va Richard Box tomonidan 1991-yil aprel oyida chop etilgan Bayt jurnalida chop etilgan maqolasi bilan qayta kashf qilindi va ommalashtirildi. Asosiy gʻoya toshbaqalarni yoki roʻyxat oxiridagi kichik qiymatlarni yoʻq qilishdir, chunki qabariqda ular saralashni sekinlashtiradi. nihoyatda. (Quyonlar, roʻyxat boshidagi katta qiymatlar, qabariq bilan tartiblashda muammo tugʻdirmaydi) Buni dastlab massivda bir-biridan maʼlum masofada joylashgan elementlarni almashtirish orqali amalga oshiradi, agar ular qoʻshni boʻlsa, faqat elementlarni almashtirish oʻrniga. bir-biriga o'tkazing, so'ngra tanlangan masofani oddiy pufakcha sifatida ishlaguncha qisqartiring. Shunday qilib, agar Shellsort-ni bir-biridan ma'lum masofada joylashgan elementlarni almashtiradigan kiritish tartibining umumlashtirilgan versiyasi sifatida ko'rib chiqish mumkin bo'lsa, taroqli tartibni pufakchali tartiblash uchun qo'llaniladigan bir xil umumlashtirish sifatida ko'rish mumkin.

Almashtirish tartibi

Algoritmlar aslida bir-biridan farq qiladigan bo'lsa-da, ba'zan almashinish tartibini pufakchali tartiblash bilan aralashtirib yuborishadi.[33][34] Birja saralash birinchi elementni uning ustidagi barcha elementlar bilan solishtirish, kerak bo'lganda almashtirish orqali ishlaydi va shu bilan birinchi element oxirgi tartiblash tartibiga to'g'ri kelishini kafolatlaydi; keyin ikkinchi element uchun xuddi shunday qilishni davom ettiradi va hokazo. Agar roʻyxat allaqachon tartiblangan boʻlsa, qabariqli saralashning bir oʻtishda aniqlash afzalligi yoʻq, lekin u doimiy koeffitsient boʻyicha pufakchali tartiblashdan tezroq boʻlishi mumkin (saralash kerak boʻlgan maʼlumotlardan bir marta kam; umumiy taqqoslashlarning yarmi) eng yomon holatlar. Har qanday oddiy O(n2) saralash singari, u juda kichik ma'lumotlar to'plamlari uchun juda tez bo'lishi mumkin, lekin umuman olganda kiritish tartiblash tezroq bo'ladi.

Tarqatish turlari

Shuningdek qarang: Tashqi tartiblash
Tarqatish saralash har qanday saralash algoritmiga ishora qiladi, bunda ma'lumotlar kirishdan bir nechta oraliq tuzilmalarga taqsimlanadi, ular keyinchalik yig'iladi va chiqishga joylashtiriladi. Masalan, paqir va flesh-sort ham taqsimotga asoslangan tartiblash algoritmlaridir. Tarqatishni saralash algoritmlari bitta protsessorda ishlatilishi mumkin yoki ular taqsimlangan algoritm bo'lishi mumkin, bunda alohida kichik to'plamlar turli protsessorlarda alohida tartiblanadi, keyin esa birlashtiriladi. Bu bitta kompyuter xotirasiga sig'maydigan darajada katta bo'lgan ma'lumotlarni tashqi tartiblash imkonini beradi.