Sharof rashidov nomidagi samarqand davlat universiteti amaliy matematika yo

2. Mashhur saralash algoritmlari va oddiy usullar

Shellsort tomonidan ixtiro qilingan Donald Shell 1959 yilda.^[32] Bu buyurtma elementlarini bir vaqtning o'zida bir nechta pozitsiyadan chiqib ketish orqali qo'shish tartibini yaxshilaydi. Shellsortning kontseptsiyasi shundan iboratki, qo'shish tartibini amalga oshiradi  vaqt, bu erda $ k $ - joyidan ikkita element orasidagi eng katta masofa. Bu shuni anglatadiki, ular umuman olganda O(n²), lekin asosan saralangan, faqat bir nechta elementlari bo'lmagan ma'lumotlar uchun ular tezroq ishlaydi. Shunday qilib, avval elementlarni uzoqdan saralash va saralash uchun elementlar orasidagi bo'shliqni asta-sekin qisqartirish orqali yakuniy saralash ancha tezroq hisoblab chiqiladi. Bitta dasturni ma'lumotlar ketma-ketligini ikki o'lchovli massivda joylashtirish va keyin qo'shma tartib yordamida massiv ustunlarini saralash deb ta'riflash mumk

Shellsortning eng yomon vaqt murakkabligi - bu ochiq muammo va ma'lum bo'lgan murakkabliklar bilan ishlatilgan bo'shliqlar ketma-ketligiga bog'liq O(n²) ga O(n^4/3) va Θ (n jurnal² n). Bu, Shellsort ekanligi bilan birlashtirilgan joyida, faqat nisbatan kam miqdordagi kodga muhtoj va undan foydalanishni talab qilmaydi chaqiruv to'plami, kabi xotira yuqori darajadagi holatlarda foydalidir o'rnatilgan tizimlar va operatsion tizim yadrolari.
Bubble sort va variantlari
Bubble sort, va kabi variantlar qobiq saralash va mexnat turi, oddiy, juda samarasiz saralash algoritmlari. Tahlil qilish qulayligi tufayli ular kirish matnlarida tez-tez uchraydi, ammo amalda kamdan kam qo'llaniladi.
Bubble sort oddiy tartiblash algoritmi. Algoritm ma'lumotlar to'plamining boshidan boshlanadi. U dastlabki ikkita elementni taqqoslaydi va agar birinchisi ikkinchisidan kattaroq bo'lsa, ularni almashtiradi. Ma'lumotlar to'plamining oxirigacha qo'shni elementlarning har bir juftligi uchun buni davom ettiradi. Keyin yana dastlabki ikkita element bilan boshlanadi va oxirgi o'tkazishda hech qanday svop bo'lmaguncha takrorlanadi.^[33] Ushbu algoritmning o'rtacha vaqti va eng yomon ko'rsatkichi O (n²), shuning uchun u kamdan-kam hollarda katta, tartibsiz ma'lumotlar to'plamlarini saralash uchun ishlatiladi. Bubble sorti oz sonli narsalarni saralash uchun ishlatilishi mumkin (bu erda uning asimptotik samarasizligi yuqori jazo emas). Ko'pikni saralash deyarli har qanday uzunlikdagi ro'yxatda ham samarali ishlatilishi mumkin (ya'ni, elementlar sezilarli darajada joyida emas). Misol uchun, agar biron bir sonli element faqat bitta pozitsiya bilan mos kelmasa (masalan, 0123546789 va 1032547698), qabariq tartiblash almashinuvi ularni birinchi o'tish paytida tartibda oladi, ikkinchi o'tish barcha elementlarni tartibda topadi, shuning uchun tartiblash bo'ladi faqat 2 ni olingn vaqt.
Taroq saralash
Asosiy maqola: Taroq saralash
Taroq saralash ga asoslangan nisbatan sodda tartiblash algoritmi qabariq turi va dastlab Wlodzimierz Dobosiewicz tomonidan 1980 yilda ishlab chiqilgan. Keyinchalik u Stiven Leysi va Richard Boks tomonidan qayta kashf etilib, ommalashtirildi Bayt Jurnal 1991 yil aprelda chop etilgan maqola. Asosiy g'oya yo'q qilishdir toshbaqalaryoki ro'yxat oxiriga yaqin kichik qiymatlar, chunki ko'pikli tartibda ular saralashni juda sekinlashtiradi. (Quyonlar, ro'yxat boshidagi katta qiymatlar, qabariq tartibida muammo tug'dirmaydi) Bunga dastlab elementlarni faqat bir-biriga ulashgan holda almashtirish o'rniga, qatorda bir-biridan ma'lum masofada joylashgan elementlarni almashtirish orqali erishiladi. va keyin tanlangan masofani oddiy pufakchali tartibda ishlaguncha qisqartiradi. Shunday qilib, agar Shellsort bir-biridan ma'lum masofada joylashgan elementlarni almashtiradigan qo'shimchalash tartibining umumlashtirilgan versiyasi deb qaralishi mumkin bo'lsa, taroq turini qabariq turiga nisbatan qo'llaniladigan bir xil umumlashma deb hisoblash mumkin.

Tarqatish tartibi

Shuningdek qarang: Tashqi tartiblash
Tarqatish tartibi ma'lumotlar har qanday saralash algoritmiga ishora qiladi, bu erda ma'lumotlar ularning kiritilishidan bir nechta oraliq tuzilmalarga tarqatiladi, keyinchalik ular yig'ilib chiqishga joylashtiriladi. Masalan, ikkalasi ham chelak navi va fleshsort tarqatish asosida saralash algoritmlari. Tarqatishni saralash algoritmlari bitta protsessorda ishlatilishi mumkin yoki ular bo'lishi mumkin taqsimlangan algoritm, bu erda alohida kichik to'plamlar turli xil protsessorlarda alohida saralanadi, so'ngra birlashtiriladi. Bu imkon beradi tashqi tartiblash bitta kompyuter xotirasiga sig‘maydigan darajada katta ma'lumotlar.
Sanoq turi
Asosiy maqola: Sanoq turi
Har bir kirishning ma'lum bir to'plamga tegishli ekanligi aniqlanganda, hisoblash tartibini qo'llash mumkin, S, imkoniyatlar. Algoritm O (|) da ishlaydiS| + n) vaqt va O (|S|) xotira qaerda n kirish uzunligi. U | butun o'lchovli massiv yaratish orqali ishlaydiS| va yordamida menning paydo bo'lishini hisoblash uchun th mena'zosi S kirishda. Keyin har bir kirish mos keladigan axlat qutisi qiymatini oshirish orqali hisoblanadi. Shundan so'ng, barcha kirishlarni tartibda tartibga solish uchun hisoblash massivi aylanib o'tiladi. Ushbu saralash algoritmidan ko'pincha foydalanish mumkin emas, chunki S algoritm samarali bo'lishi uchun juda kichik bo'lishi kerak, lekin u juda tez va juda yaxshi asimptotik harakatni namoyish etadi n ortadi. Bundan tashqari, barqaror xatti-harakatni ta'minlash uchun uni o'zgartirish mumkin.
Paqir navi
Asosiy maqola: Paqir navi
Paqir navi a bo'ling va zabt eting umumlashtiruvchi saralash algoritmi hisoblash turi qatorni sonli chelaklarga bo'lish orqali. Keyin har bir chelak alohida saralash algoritmidan foydalangan holda yoki chelakni saralash algoritmini rekursiv ravishda qo'llagan holda alohida-alohida saralanadi.
Ma'lumotlar to'plami elementlari barcha chelaklarga teng ravishda taqsimlanganda, paqir saralash eng yaxshi ishlaydi.
Radix sort
Asosiy maqola: Radix sort
Radix sort alohida raqamlarni qayta ishlash orqali raqamlarni saralash algoritmi. n iborat raqamlar k har bir raqam O (n · k) vaqt. Radix tartibida har bir sonning raqamlari kamida muhim raqam (LSD) yoki dan boshlab eng muhim raqam (MSD). LSD algoritmi avval barqaror tur yordamida nisbiy tartibini saqlab, ro'yxatni eng kichik raqamlar bo'yicha saralaydi. Keyin ularni keyingi raqamlar bo'yicha saralaydi va hokazo tartiblangan ro'yxat bilan yakunlanib, eng ahamiyatsizdan eng ahamiyatli tomonga qadar. LSD radix saralash barqaror turdan foydalanishni talab qilsa, MSD radix saralash algoritmi talab qilmaydi (barqaror saralash kerak bo'lmasa). O'z o'rnida MSD radix saralash barqaror emas. Bu odatiy holdir hisoblash turi ichki radius tartibida ishlatiladigan algoritm. A gibrid foydalanish kabi saralash yondashuvi qo'shish tartibi kichik qutilar uchun radix turini sezilarli darajada yaxshilaydi.
Xotiradan foydalanish tartibi va indekslarni saralash
Tartibga solinadigan massivning hajmi mavjud bo'lgan asosiy xotiraga yaqinlashganda yoki undan oshib ketganda (juda sekinroq) disk yoki almashtirish maydoni ishlatilishi kerak bo'lsa, tartiblash algoritmining xotiradan foydalanish tartibi muhim ahamiyat kasb etadi va algoritm juda adolatli bo'lishi mumkin edi. Qator RAMga osonlikcha sig'adigan bo'lsa, samarasiz bo'lishi mumkin. Ushbu stsenariyda taqqoslashlarning umumiy soni (nisbatan) unchalik ahamiyatli bo'lmaydi va xotira qismlarining diskka nusxa ko'chirilishi yoki almashtirilishi va algoritmning ishlash xususiyatlarida ustunlik qilishi mumkin bo'lgan soni. Shunday qilib, o'tish soni va taqqoslashning lokalizatsiyasi taqqoslashning dastlabki sonidan ko'ra muhimroq bo'lishi mumkin, chunki yaqin atrofdagi elementlarni bir-biriga taqqoslash sodir bo'ladi tizim avtobusi tezlik (yoki keshlash bilan, hatto Markaziy protsessor disk tezligi bilan taqqoslaganda deyarli bir zumda).
Masalan, mashhur rekursiv tezkor algoritm etarli RAM bilan etarli darajada oqilona ishlashni ta'minlaydi, ammo massivning qismlarini nusxalashning rekursiv usuli tufayli qator RAMga mos kelmasa, unchalik amaliy bo'lmaydi, chunki bu bir qator sekin nusxalashga yoki operatsiyalarni ko'chirishga olib kelishi mumkin. diskdan. Ushbu stsenariyda, agar ko'proq taqqoslashni talab qiladigan bo'lsa ham, boshqa algoritm afzalroq bo'lishi mumkin.
Murakkab yozuvlar paytida yaxshi ishlaydigan ushbu muammo ustida ishlashning bir usuli (masalan, a relyatsion ma'lumotlar bazasi ) nisbatan kichik kalit maydon bo'yicha saralanmoqda, massivda indeks yaratish va keyin butun qatorni emas, indeksni saralash. (Keyinchalik butun massivning tartiblangan versiyasi indeksdan o'qish bilan bitta o'tish yo'li bilan ishlab chiqarilishi mumkin, lekin ko'pincha bu keraksiz, chunki tartiblangan indeks etarli bo'ladi.) Indeks butun massivdan ancha kichik bo'lgani uchun diskni almashtirish muammosini samarali ravishda yo'q qilib, butun massiv ishlamaydigan xotiraga osongina joylashadi. Ushbu protsedura ba'zan "yorliqlarni saralash" deb nomlanadi.
Xotira hajmi muammosini bartaraf etishning yana bir usuli qo'llaniladi tashqi tartiblash, for example one of the ways is to combine two algorithms in a way that takes advantage of the strength of each to improve overall performance. For instance, the array might be subdivided into chunks of a size that will fit in RAM, the contents of each chunk sorted using an efficient algorithm (such as tezkor ), and the results merged using a k-way merge similar to that used in mergesort. This is faster than performing either mergesort or quicksort over the entire list.^[37][38]
Techniques can also be combined. For sorting very large sets of data that vastly exceed system memory, even the index may need to be sorted using an algorithm or combination of algorithms designed to perform reasonably with virtual xotira, i.e., to reduce the amount of swapping required.

Tegishli algoritmlar

Bunga tegishli muammolar kiradi partial sorting (sorting only the k smallest elements of a list, or alternatively computing the k smallest elements, but unordered) and tanlov (computing the kth smallest element). These can be solved inefficiently by a total sort, but more efficient algorithms exist, often derived by generalizing a sorting algorithm. The most notable example is tez tanlash bilan bog'liq bo'lgan tezkor. Conversely, some sorting algorithms can be derived by repeated application of a selection algorithm; quicksort and quickselect can be seen as the same pivoting move, differing only in whether one recurses on both sides (quicksort, bo'ling va zabt eting ) or one side (quickselect, decrease and conquer ).
A kind of opposite of a sorting algorithm is a shuffling algorithm. These are fundamentally different because they require a source of random numbers.
Yuqorida tavsiflangan klassik qidirish muammolari va veb-qidiruv ikkalasi ham muammo ma'lumot olish, lekin odatda alohida subfield sifatida o'rganiladi va har xil echiladi va baholanadi. Veb-qidiruv muammolari odatda odamlarning so'rovlariga eng mos keladigan hujjatlarni filtrlashga va topishga qaratilgan. Klassik qidiruv algoritmlari odatda echimni qanchalik tez topa olishlari va ushbu echimning maqbul bo'lishiga kafolat berilishi bo'yicha baholanadi. Axborotni qidirish algoritmlari tezkor bo'lishiga qaramay, sifati reyting yaxshi natijalar qoldirilganmi va yomon natijalar kiritilganmi, muhimroqdir.
Tegishli qidiruv algoritmi ko'pincha qidirilayotgan ma'lumotlar tuzilmasiga bog'liq bo'lib, ma'lumotlar haqida oldingi bilimlarni ham o'z ichiga olishi mumkin. Ba'zi ma'lumotlar bazasi tuzilmalari qidirish algoritmlarini tezroq yoki samaraliroq qilish uchun maxsus tuzilgan, masalan qidirish daraxti, xash xaritasi yoki a ma'lumotlar bazasi ko'rsatkichi.
Qidiruv algoritmlarini qidirish mexanizmiga qarab tasniflash mumkin. Lineer qidirish algoritmlar har bir yozuvni chiziqli ravishda maqsadli kalit bilan bog'liqligini tekshiradi.^[3] Ikkilik yoki yarim intervalli qidiruvlar, qidiruv strukturasining markazini bir necha bor nishonga oling va qidiruv maydonini yarmiga bo'ling. Taqqoslash qidirish algoritmlari maqsadli yozuv topilmaguncha tugmachalarni taqqoslash asosida yozuvlarni ketma-ket yo'q qilish orqali chiziqli qidiruvni yaxshilaydi va belgilangan tartibda ma'lumotlar tuzilmalarida qo'llanilishi mumkin.^[4] Raqamli qidirish algoritmlari raqamli kalitlardan foydalanadigan ma'lumotlar tuzilmalaridagi raqamlarning xususiyatlariga asoslanib ishlaydi. Nihoyat, hashing to'g'ridan-to'g'ri yozuvlar uchun kalitlarni xaritalar asosida xash funktsiyasi.^[6] Chiziqli qidiruvdan tashqaridagi qidiruvlar ma'lumotlarning qandaydir tartibda bo'lishini talab qiladi.
Algoritmlar ko'pincha ular tomonidan baholanadi hisoblash murakkabligi yoki maksimal nazariy ish vaqti. Ikkilik qidirish funktsiyalari, masalan, maksimal darajada murakkablikka ega O(log n), yoki logaritmik vaqt. Bu shuni anglatadiki, qidiruv maqsadini topish uchun zarur bo'lgan maksimal operatsiyalar soni qidiruv maydoni hajmining logaritmik funktsiyasidi.