|
Saralash algoritmlari Qo'shishni tartiblash algoritmlari
|
| bet | 1/2 | | Sana | 06.06.2023 | | Hajmi | 42.85 Kb. | | #70122 |
Bog'liq Mundarija Berdiyeva Nilufar Anvar qizi (2), ABDULLA-AVLONIY, 6-sinf adabiyot qisqa ma\'lumotlar
Mundarija
Kirish
1. Saralash algoritmlari
1.1 Qo'shishni tartiblash algoritmlari
1.2 Oddiy tanlov bo'yicha saralash
1.3 Oddiy almashish bo'yicha saralash
1.4. Shell tartiblash
2. Qidiruv algoritmlari
2.1 Ketma-ket qidiruv
2.2 Ikkilik qidiruv
2.3 Substring qidiruvi
Xulosa
Foydalanilgan adabiyotlar ro'yxati
Kirish
So'nggi paytlarda elektron kompyuterlar uchun dasturlash nafaqat ko'plab amaliy sohalarda samarali ishlash uchun muhim bo'lgan vosita, balki ilmiy tadqiqot sohasi hamdir. Ma'lumotlarning tuzilishi haqida qaror qabul qilishda algoritmlarni bilish juda muhim ekanligi ayon bo'ladi. Har kuni hayot tezlashmoqda, tezlashmoqda, har xil ma'lumotlar oqimi o'sib bormoqda. Turli xil ma'lumotlarni saqlash uchun ma'lumotlar bazalari deb nomlanadi. Shu bilan birga, agar ular millionlab elementlarni o'z ichiga olgan bo'lsa, bu ma'lumotlar bazalari bilan ishlash juda qiyin, deyarli imkonsizdir. Amalda, saralashdan foydalanmasdan, bunday hajmdagi ma'lumotlarda yo'qolmaslik mumkin emas, oldindan buyurtma qilingan to'plamdan kerakli ma'lumotlarni nisbatan tez va samarali ajratish imkonini beradi. Shunday qilib, saralash algoritmlari, ayniqsa, axborotni qayta ishlashda muhim ahamiyatga ega. Dasturlashda saralash usullari va uning algoritmlariga katta e'tibor beriladi.
Bugungi kunda turli xil tabiat va ma'lumotlarni qayta ishlash tezligiga ega bo'lgan ko'plab saralash algoritmlari mavjud. Biroq, ularning aksariyati juda muhim kamchilikka ega, aniqrog'i, ularni amalga oshirish muddati elementlar sonining kvadratiga mutanosibdir. Katta hajmdagi ma'lumotlarni saralash sekin bo'ladi va ma'lum bir qiymatga erishgandan so'ng, ulardan amalda foydalanish imkoniyatiga ega bo'lish uchun ular ancha sekinlashadi.
Ushbu ishning ilmiy ahamiyati eng mashhur saralash algoritmlarini tahlil qilish va taqdim etishda keltirilgan. “Qidirish va saralash algoritmlari” mavzusining amaliy ahamiyati har xil turdagi qidirish va saralash algoritmlarini amalga oshirish va qo‘llash muammolarini o‘rganishda taqdim etiladi.
Ushbu kurs ishining asosiy maqsadi ma'lumotlarni qidirish va saralash algoritmlarini tahlil qilish, ushbu algoritmlarni dasturlash ko'nikmalarini egallashdir.
Kurs ishimizda o'rganish ob'ekti ma'lumotlarni saralash algoritmi va ma'lumotlarni qidirish algoritmi bo'ladi.
Kurs ishimizda tadqiqot predmeti yuqori darajadagi algoritmik dasturlashda saralash va qidirish algoritmlaridan foydalanish usullari bo‘ladi.
Darhol ta'kidlash kerakki, algoritmlarni tahlil qilish, guruhlash, tadqiq qilish va ularni dasturlash usullarini turli vaqtlarda Knut D., Ulman J., Levitin A., Zeytlin G.E., Gudman S., Xidetniemi egallagan. S., Aho A., Cottoncroft J., Wirth N., Lauryn G., McConnell J. va boshqalar.
1. Saralash algoritmlari
Algoritm (algoritm) - kirishda (kirishda) har qanday aniq belgilangan hisoblash jarayoni bo'lib, unga qandaydir qiymat yoki qiymatlar to'plami beriladi va amalga oshirish natijasi chiqish (chiqish) qiymati yoki qiymatlar to'plamidir. Bu shuni anglatadiki, algoritm kirish qiymatlarini chiqish qiymatlariga aylantiradigan hisoblash bosqichlarining ma'lum bir ketma-ketligidir.
Algoritm, shuningdek, yaxshi tuzilgan hisoblash masalalarini yechish vositasi sifatida ham taqdim etiladi. Algoritm ushbu munosabatlarni amalga oshirishga erishish uchun ishlatilishi mumkin bo'lgan aniq hisoblash jarayonini tavsiflaydi.
Masalan, sonlar ketma-ketligini kamaymaydigan tartibda saralash zarurati paydo bo'ladi. Bunday muammo amaliyotda juda keng tarqalgan va algoritmlarni ishlab chiqish va tahlil qilishning standart usullarining ko'pchiligi bilan tanishish uchun ajoyib namuna bo'lib xizmat qiladi.
Saralash - ma'lum bir ma'lumotlar to'plamining ob'ektlarini ma'lum tartibda tartiblash tartibi. Saralash jarayonining asosiy maqsadi saralangan ma'lumotlar qatoridagi qiymatlarni keyingi izlash tezligini oshirishdir. Amalda barcha vazifalarda saralash elementlari mavjud. Saralangan elementlar telefon ma'lumotnomalarida, mundarijalarda, kutubxonalarda, lug'atlarda va boshqa ko'plab maqsadlarda mavjud.
Shunga ko'ra, saralash usullari, ayniqsa, axborot ma'lumotlarini qayta ishlashda juda muhimdir. Saralash bir xil vazifani amalga oshiradigan algoritmlarni qurish uchun ko'plab fundamental texnikalar bilan bog'liq bo'lib, ularning ba'zilari qaysidir ma'noda optimaldir va ularning aksariyati qolganlarga nisbatan ma'lum afzalliklarga ega.
Algoritmlarni tanlashning ma'lumotlar tuzilishiga bog'liqligi kuchli. Amaldagi saralash usullari ko'pincha ikki guruhga bo'linadi: fayllarni saralash va massivlarni saralash. Bu ikki guruh ba'zan ichki va tashqi turlar deb ataladi, chunki massivlar kompyuterning "ichki" (operativ) xotirasida (tezkor tasodifiy kirish bu xotira turiga xosdir) va ko'rib chiqilayotgan fayllar unchalik tez emas, balki juda ko'p sig'imli "tashqi" xotira , boshqacha qilib aytganda, mexanik harakatga ega bo'lgan saqlash qurilmasida (disklar, lentalar).
Saralash algoritmlari samaradorligining asosiy mezonlari quyidagilardan iborat:
tezlik;
xotirani tejash;
Dasturchining algoritmni amalga oshirishga sarflagan vaqtini qisqartirish.
Shuning uchun to'plamdagi elementlarning soni, ularning tartibi, tartiblash chastotasi va boshqa omillarga qarab, turli xil saralash va qidirish algoritmlaridan foydalanish kerak.
Saralash va qidirish algoritmlari bilan batafsilroq tanishish uchun kichik fayllar yoki maxsus tuzilmali fayllar bilan ishlashda o'zini yaxshi isbotlagan ba'zi "elementar" tartiblash usullarini ko'rib chiqaylik. Ushbu oddiy usullarni o'rganish kerak bo'lgan ko'plab sabablar mavjud. Birinchidan, ular bizga terminologiya va saralash algoritmlarining asosiy mexanizmlari bilan tanishishning nisbatan oson usulini taqdim etadi va bu bizga murakkabroq algoritmlarni o'rganish uchun zarur bazani olish imkonini beradi. Ikkinchidan, ko'plab tartiblash masalalarida murakkabroq algoritmlardan ko'ra oddiy usullardan foydalanish yaxshidir. Va nihoyat, oddiy usullarning ba'zilari yaxshiroq usullarga aylantirilishi yoki murakkabroqlarini yaxshilash uchun ishlatilishi mumkin.
Ko'pgina saralash dasturlarida oddiy elementar algoritmlardan foydalanish yaxshidir. Saralash dasturlari ba'zan faqat bir marta (yoki bir necha marta) qo'llaniladi. Agar tartiblash kerak bo'lgan elementlar soni kichik bo'lsa (taxminan 500 elementdan kam), elementar algoritmdan foydalanish qiyin algoritmni yangi o'rganish va disk raskadrovka qilishdan ko'ra ko'proq samara beradi. Elementar oddiy usullar har doim kichik fayllar uchun foydalidir (50 dan kam element yoki shunga o'xshash); albatta, bunday fayllar uchun murakkab algoritmni qo'llash oqilona bo'lmaydi, albatta, agar bunday fayllarni ko'p sonini saralash kerak bo'lmasa.
Odatda biz ko'rib chiqayotgan oddiy oddiy usullar N ta tasodifiy tanlangan elementlarni saralash operatsiyalarini bajaradi. Agar N etarlicha kichik bo'lsa, unda bu muammo bo'lmasligi mumkin va agar elementlar tasodifiy tartibga solinmagan bo'lsa, unda bu algoritmlar ba'zan murakkablarga qaraganda tezroq ishlaydi. Ammo shuni yodda tutish kerakki, bu algoritmlarni katta, tasodifiy tartiblangan fayllarga qo'llash shart emas, ko'plab dasturlarda qo'llaniladigan qobiqni tartiblash algoritmidan istisno.
O'zboshimchalik bilan algoritmni ko'rib chiqishdan oldin, atamalar va algoritmlarni saralash bo'yicha ba'zi asosiy konventsiyalarni o'rganish foydali bo'ladi. Biz kalitlarni o'z ichiga olgan yozuv fayllarini saralash algoritmlarini o'rganish niyatidamiz. Yozuvning faqat bir qismi bo'lgan kalitlar (asosan ularning juda kichik qismi) saralash jarayonini boshqarish uchun ishlatiladi. Saralash algoritmining maqsadi - fayldagi yozuvlarni yangi tashkil etish, unda ularning joylashuvi qandaydir qat'iy tartibga solingan tartibda (ko'pincha alifbo yoki raqamli tartibda).
Agar tartiblangan fayl xotiraga to'liq sig'sa (yoki massivga to'liq mos tushsa), buning uchun ichki tartiblash usullari qo'llaniladi. Lenta yoki diskdagi ma’lumotlarni saralash tashqi tartiblash deyiladi. Ularning asosiy farqi shundaki, ichki saralash har qanday yozuvni osongina olish imkonini beradi, tashqi saralash esa yozuvlarni faqat ketma-ket yoki katta bloklarda qo'llashi mumkin. Asosan, quyida muhokama qilinadigan tartiblash algoritmlari ichkidir.
Asosan, odatda algoritmni qiziqtiradigan asosiy narsa uning ishlash muddati hisoblanadi. N elementni saralash uchun quyida muhokama qilingan dastlabki to‘rtta algoritm ish vaqtini ga proportsional oladi, murakkabroq algoritmlar esa ga proportsional ish vaqtini oladi. (Har qanday saralash algoritmi kalitlar orasidagi taqqoslashdan kamroq foydalana olmasligini ko'rsatish mumkin.) Oddiy usullarni o'rganib chiqib, biz ishlash vaqti proportsional bo'lgan murakkabroq usullarni va umumiy davrni qisqartirish uchun kalitlarning binar xususiyatlarini qo'llaydigan algoritmlarni ko'rib chiqamiz. N uchun ishlash.
Saralash algoritmining qo'shimcha xotirasi miqdori ham hisobga olinadigan qo'shimcha omil hisoblanadi. Saralash usullari odatda uch guruhga bo'linadi:
qo'shimcha xotiradan foydalanmasdan saralash usullari, ehtimol kichik stek va/yoki massivdan tashqari;
bog'langan ro'yxatlarni saralash va shuning uchun xotirada N qo'shimcha ko'rsatkichlardan foydalanish holatlarida qo'llaniladigan usullar;
va tartiblangan faylning dublikatini saqlash uchun to'ldirilgan xotiraga muhtoj bo'lgan usullar.
Barqarorlik ham saralash usullarining muhim xususiyati hisoblanadi. Saralash usuli, agar u bir xil kalit bilan yozuvlarning nisbiy tartibini saqlasa, barqaror hisoblanadi. Masalan, o'quvchilarning alifbo tartibidagi ro'yxati baholar bo'yicha tartiblangan bo'lsa, unda barqaror usul bir xil ballga ega bo'lgan talabalarning familiyalari alifbo tartibida tartiblangan ro'yxatni tashkil qiladi va beqaror usulda dastlabki tartib buzilishi mumkin bo'lgan ro'yxat tuziladi. . Oddiy usullarning ko'pchiligi barqaror, ammo taniqli murakkab usullarning aksariyati barqaror emas. Agar barqarorlik zarur bo'lsa, unda saralash jarayonidan oldin kalitga kichik indeks qo'shish yoki kalitni qandaydir tarzda uzaytirish orqali erishish mumkin. Barqarorlik me'yor bilan osonlikcha xato qiladi; odamlarning beqarorlikka nisbatan ishonchsiz munosabati bor. Aslida,
Algoritmning samaradorligini aniqlash uchun C raqamini - kalitlarning kerakli taqqoslashlarini va M - elementlarning tayinlanishini taxmin qilish kerak. Ko'rsatilgan raqamlar tartiblangan elementlarning n sonidan ma'lum formulalar bilan hisoblanadi. Qoniqarli saralash algoritmlari taxminan taqqoslashlardan foydalanadi.
Terminologiya bo'yicha kelishib olaylik: bizda elementlar bor - a 1 , a 2 , …, a n . Saralash protsedurasi ushbu elementlarning quyidagi tartibda almashtirilishini nazarda tutadi: a k1 , a k2 , …, a kn , f (a k1 )<=f(a k2 )<=… munosabati berilgan f tartiblash funksiyasi uchun. <=f(a kn ).
Ko'pincha tartiblash funktsiyasi ma'lum bir qoida bo'yicha aniqlanmaydi, lekin har bir elementga aniq komponent (maydon) sifatida kiritilgan. Ushbu komponentning qiymati elementning kalitidir. a i elementini ifodalash uchun quyidagi ifoda ishlatiladi :
elementni yozing = yozuv
kalit: butun son;
{boshqa elementlarning tavsifi}
oxiri;
Boshqa elementlar - element haqidagi barcha muhim ma'lumotlar to'plami, kalit maydoni faqat elementni aniqlash uchun mo'ljallangan. Biroq, tartiblash algoritmlarini hisobga olsak, biz kalitga egamiz - yagona muhim komponent, qolganlari esa tanlashni talab qilmaydi.
Agar bir xil tugmalar bilan yozuvlar asl tartibda saqlangan bo'lsa, tartib barqaror bo'ladi.
1.1 Qo'shish tartibi
Bu usul asosan karta o'ynaganlar tomonidan qo'llaniladi. Elementlar (xaritalar) shartli ravishda tayyor maxsus ketma-ketlikka va kirish ketma-ketligiga bo'linadi. Doimiy ravishda keyingi bosqichda, I = 2 dan sanab, i ni bir marta oshirib, kirish ketma-ketlikning i-elementi olinadi va uni kerakli joyga qo'yib, tugallangan ketma-ketlikka o'tkaziladi.
|
|
|
|
|
|
|
|
|
|
Manba kalitlari
|
45
|
59
|
12
|
42
|
94
|
18
|
06
|
67
|
|
I=2
|
45
|
59
|
12
|
42
|
94
|
18
|
06
|
67
|
|
I=3
|
12
|
45
|
59
|
42
|
94
|
18
|
06
|
67
|
|
I=4
|
12
|
42
|
45
|
59
|
94
|
18
|
06
|
67
|
|
I=5
|
12
|
42
|
45
|
59
|
94
|
18
|
06
|
67
|
|
I=6
|
18
|
12
|
42
|
45
|
59
|
94
|
06
|
67
|
|
I=7
|
06
|
18
|
12
|
42
|
45
|
59
|
94
|
67
|
|
I=8
|
06
|
18
|
12
|
42
|
45
|
59
|
67
|
94
|
|
|
|
|
|
|
|
|
|
|
|
To'g'ri joyni qidirganda, siz taqqoslash va oldinga siljishlarni o'zgartirishingiz mumkin, xuddi shunday qilib, x "elakdan o'tkazing", uni keyingi element bilan taqqoslang va x qo'shing yoki o'ngga yo'naltirib, chapga o'ting. "Elakdan o'tkazish" ikki xil sharoitda bajarilishi mumkin:
1. X kalitidan kichik element kaliti topildi.
2. Tugallangan ketma-ketlikning chap uchiga yetdi.
Ikkita tugatish shartlariga ega bo'lgan ushbu standart halqa namunasi uydirma elementning ("to'siq") tanish usulini o'rganish imkonini beradi. Agar siz to'siqni o'rnatsangiz, bu holda osongina ishlatiladi.
Saralash tartibi;
Bu yerda i,j : indeks;
x : element;
Boshlanishi
i:=2 dan n gacha bo'lgan vaqt uchun Boshlang
x:=a[i]; a[0]:=x; j:=i-1;
X.key a[j+1]:=a[j];
j:=j-1;
Oxiri;
a[j+1]:=x;
Oxiri;
Oxiri;
Oddiy qo'shimchalar bo'yicha saralashni tahlil qilish. i-chi saralashda kalit taqqoslashlarining qiymati eng katta i-1 va eng kichik 1 bo'ladi, agar biz n tugmachaning barcha tarjimalari teng ehtimollikka ega, o'rtacha i/2 ga teng deb faraz qilsak. O'tkazmalar (topshiriqlar) soni (to'siqni hisobga olgan holda) hisoblab chiqiladi. Shunday qilib, taqqoslash va o'tkazmalarning umumiy qiymatlari quyidagicha hisoblanadi:
Eng kichik raqamlar elementlarning eng boshidan tartiblanganida, eng yomoni esa elementlar teskari tartibda bo'lganda sodir bo'ladi. Shu nuqtai nazardan, qo'shimchalar bo'yicha saralash juda normal ishlaydi. Bundan tashqari, ushbu algoritm barqaror turni ifodalashi aniq: bir xil tugmachalarga ega elementlarning ketma-ketligi bir xil bo'lib qoladi.
Oddiy qo'shimchalar bo'yicha saralash algoritmini keyingi element qo'shilishi kerak bo'lgan tugallangan ketma-ketlik ham o'sha vaqtga qadar tartiblanganligini qo'llash orqali yaxshilash oson. Shuning uchun, inklyuziya joyi tezroq aniqlanadi. Bu erda ikkilik qidiruvdan foydalanish mumkinligi aniq, u tugagan ketma-ketlikning o'rta elementini tekshiradi va qo'shilish nuqtasi topilmaguncha yarmiga bo'linadi. Yaxshilangan tartiblash algoritmi aks holda ikkilik qo'shimchalar bo'yicha tartiblash orqali aniqlanadi.
ikkilik kiritish protsedurasi;
var i,j,l,r,m : indeks;
x : element;
boshlanishi
uchun i:= 2 dan n gacha boshlanadi
x:= a[i];
i := 1;
r := i - 1;
l <= r esa boshlanadi
m := (l+r) div 2;
agar x.key < a[m].key bo'lsa, r:=m - 1
aks holda l := m+1
oxiri;
j uchun := i - 1 dan l gacha do a[j+1] :=a [j];
a[l] := x;
oxiri;
oxiri;
Ikkilik qo'shimchalar bo'yicha saralashni tahlil qilish. Umuman olganda, taqqoslashlar soni elementlarning asl tartibiga juda bog'liq emas. Biroq, qidiruv diapazoni ikki baravar kamaytirilganda yaxlitlash tufayli, i elementlari uchun haqiqiy taqqoslashlar soni ba'zan kutilganidan 1 taga ko'p bo'ladi. Ushbu "qiyshiqlik" ning sababi shundaki, pastki qismdagi qo'shimchalar yuqori qismdagilarga qaraganda o'rtacha bir oz tezroq hisoblanadi. Shuning uchun, elementlar boshidanoq to'g'ri tartibdan uzoqda bo'lsa, bu afzallik. Darhaqiqat, elementlar boshidanoq teskari tartibda bo'lganda, eng kam miqdordagi taqqoslashlar kerak bo'ladi va eng ko'p taqqoslashlar - ular allaqachon buyurtma qilingan bo'lsa. Shunga ko'ra, bu odatiy bo'lmagan tartiblash algoritmi ifodasidir
C = n (Log (n) - Log (e) ± 0,5).
Ikkilik qidiruv usuli yordamida biz erishgan yaxshilanish faqat taqqoslashlar soniga bog'liq, kerakli hopslar soni emas. Darhaqiqat, elementlarning almashinuvi, ya'ni. kalitlar va tegishli ma'lumotlar odatda ikkita kalitni taqqoslashdan ko'ra ko'proq vaqt talab etadi. Bu yaxshilanish hech qanday hal qiluvchi ahamiyatga ega emas: eng muhim ko'rsatkich M hali ham qolmoqda. Darhaqiqat, tartiblangan massivga murojaat qilish keyingi qidiruvda oddiy qo'shimchalar bo'yicha tartiblashdan ko'ra ko'proq vaqt talab etadi! Elementlarni uzatish faqat bitta elementlar uchun va uzoq masofalarga qo'llanilsa, usuldan yaxshiroq natijalarga erishish mumkin. Bu nuqta tanlov tartibiga e'tibor qaratadi.
1.2 Oddiy tanlov bo'yicha saralash
algoritm tartiblash dasturlash qidiruvi
Ushbu usul quyidagi shartlarni o'z ichiga oladi:
1. Eng kichik kalitli element aniqlanadi.
2. Tanlangan element birinchi element a[1] bilan almashtiriladi.
Keyin bu amallar boshqa n - 1 element, keyin cn - 2 element bilan takrorlanadi, faqat bitta element qolmaguncha - eng kattasi.
|
|
|
|
|
|
|
|
|
|
|
44
|
55
|
12
|
42
|
94
|
18
|
06
|
67
|
|
|
06
|
55
|
12
|
42
|
94
|
18
|
44
|
67
|
|
|
06
|
12
|
55
|
42
|
94
|
18
|
44
|
67
|
|
|
06
|
12
|
18
|
42
|
94
|
55
|
44
|
67
|
|
|
06
|
12
|
18
|
42
|
94
|
55
|
44
|
67
|
|
|
06
|
12
|
18
|
42
|
44
|
55
|
94
|
67
|
|
|
06
|
12
|
18
|
42
|
44
|
55
|
94
|
67
|
|
|
06
|
12
|
18
|
42
|
44
|
55
|
67
|
94
|
|
|
|
|
|
|
|
|
|
|
|
Ko'pincha oddiy tanlash saralash deb ataladigan bu usul qaysidir ma'noda oddiy qo'shish tartibiga qarama-qarshidir; keyingi har bir qadamda oddiy qo'shimchalar bo'yicha saralash joriy momentdagi kirish ketma-ketligining faqat bitta keyingi elementini va kiritilgan joyni hisoblash uchun tayyorlangan massivning barcha elementlarini hisoblaydi; oddiy tanlash tartiblash elementni eng kichik kalit bilan aniqlash uchun kirish massivining barcha elementlarini kuzatib boradi va bu keyingi element tugallangan ketma-ketlikka yuboriladi. Umuman olganda, oddiy tanlov bo'yicha tartiblash algoritmi quyidagi shaklda aks ettirilgan:
tartibni tanlash;
bu yerda i,j,k : indeks;
x: element;
boshlanishi
i uchun := 1 dan n - 1 gacha boshlanadi
k := i; h := a[i];
j :=i+1 uchun n qilish
Agar a[j] .key < x .key bo'lsa, boshlang
k := j; x := a[j]
oxiri;
a[k] := a[i]; a[i] := x;
oxiri
oxiri;
Oddiy tanlov bo'yicha tahlillarni saralash. Kalit taqqoslashlarining C qiymati kalitlarning dastlabki tartibidan farq qilishi aniq. Shu munosabat bilan shuni aytish mumkinki, oddiy tanlab olish tartiblash oddiy inklyuziyadan ko'ra sodda tarzda ifodalanadi. Natija
Topshiriqlarning eng kichik qiymati kalitlarga eng boshidan buyurtma berilganda va kalitlar dastlab teskari tartibda buyurtma qilinganda eng katta qiymatga teng bo'ladi. D. Knutning o'rtacha qiymati =0,577216… (Eyler doimiysi) bilan belgilanadi.
Shunday qilib, xulosa qilish mumkinki, umuman olganda, tanlashni tartiblash algoritmi qo'shishni tartiblash algoritmidan ko'ra afzalroqdir, garchi ba'zida tugmalar dastlab tartiblangan yoki biroz tartiblangan bo'lsa ham, kiritish tartibi biroz tezroq natijalar beradi.
1.3 Oddiy almashish bo'yicha saralash
Saralash usullarini guruhlash aniq va aniq ta'rifga ega emas. Yuqorida keltirilgan ikkita usul ixtiyoriy ravishda almashish tartibi sifatida belgilanishi mumkin. Biroq, ikkita elementning almashinuvi jarayonning asosiy xarakteristikasi bo'lgan usul mavjud. Quyida ko'rib chiqilgan oddiy almashuv tartiblash algoritmi barcha elementlar tartiblashtirilgunga qadar ikkita qo'shni elementni solishtirish va almashishga asoslangan.
Ko'rib chiqilayotgan oddiy tanlash usullarida bo'lgani kabi, massiv orqali har safar qolgan to'plamning eng kichik elementini aniqlab, massivning chap chetiga qarab takroriy o'tishlar amalga oshiriladi. Agar o'zgartirish uchun gorizontal emas, balki vertikal ravishda joylashgan massivni ko'rib chiqing va tasavvurning bir qismi yordamida elementlarni kalitlariga mos keladigan "og'irliklari" bo'lgan suv idishidagi pufakchalar sifatida tasavvur qiling, keyin massiv orqali keyingi o'tish "suzuvchi" qabariqni uning og'irligiga mos keladigan darajaga olib keladi. Bu usul hamma uchun pufakchali tartib sifatida tanish.
Bubblesort protsedurasi:
bu yerda i,j: indeks;
x : element;
boshlanishi
uchun i:=1 dan n gacha boshlanadi
j:=n uchun igacha
agar a[j - 1].key > a[j].tugmachasi, keyin boshlang
x:=a[j - 1];
a[j - 1]:=a[j];
a[j]:=x;
oxiri
oxiri
oxiri; {bubblesort]
|
|
|
|
|
|
|
|
|
Manba kalitlari
|
i = 02
|
i = 03
|
i = 04
|
i = 05
|
i = 06
|
i = 07
|
i = 08
|
|
045
|
06
|
06
|
06
|
06
|
06
|
06
|
06
|
|
059
|
045
|
012
|
012
|
012
|
012
|
012
|
012
|
|
012
|
059
|
045
|
018
|
018
|
018
|
018
|
018
|
|
042
|
012
|
059
|
045
|
042
|
042
|
042
|
042
|
|
094
|
042
|
018
|
059
|
045
|
045
|
045
|
045
|
|
018
|
094
|
042
|
042
|
059
|
059
|
059
|
059
|
|
006
|
018
|
094
|
067
|
067
|
067
|
067
|
067
|
|
067
|
067
|
067
|
094
|
094
|
094
|
094
|
094
|
|
|
|
|
|
|
|
|
|
|
Ushbu algoritmni optimallashtirish oson. Ushbu misol shuni ko'rsatadiki, oxirgi uchta o'tish elementlarning tartibiga hech qanday ta'sir qilmaydi, chunki ular allaqachon tartiblangan. Ushbu algoritmni yaxshilashning oson yo'li - bu o'tishda biron bir almashinuv borligini eslab qolishdir. Salbiy javob bo'lsa, bu algoritm jarayonni yopishi mumkinligini anglatadi. Agar nafaqat birjaning o'zi, balki oxirgi birjaning o'rni (indeksi) esda qolsa, ushbu takomillashtirish tartibi davom ettirilishi mumkin. Shubhasiz, qo'shni elementlarning barcha juftlari berilgan k indeksidan kamroq indekslarga ega va allaqachon kerakli tartibda bo'ladi. Shunga ko'ra, keyingi o'tishlar oldindan belgilangan quyi darajaga o'tishdan ko'ra, ma'lum bir indeksda bajarilishi mumkin i. Biroq, agar siz diqqat bilan qarasangiz,
Masalan, massiv
1218424455679406
massivni saralashda qabariq usuli yordamida bir bosqichda tartiblanadi
9406121842445567
ettita o'tishni oladi. Ushbu noodatiy assimetriya uchinchi yaxshilanishga olib keladi: birin-ketin almashinadigan o'tish yo'nalishini o'zgartirish. Shu tarzda taqdim etilgan algoritm ko'pincha shaker sort deb ataladi.
|
|
|
|
|
|
I=2
|
3
|
3
|
4
|
4
|
|
R=8
|
8
|
7
|
7
|
4
|
|
44
|
06
|
06
|
06
|
06
|
|
55
|
44
|
44
|
12
|
12
|
|
12
|
55
|
12
|
44
|
18
|
|
42
|
12
|
42
|
18
|
42
|
|
94
|
42
|
55
|
42
|
44
|
|
18
|
94
|
18
|
55
|
55
|
|
06
|
18
|
67
|
67
|
67
|
|
67
|
67
|
94
|
94
|
94
|
|
|
|
|
|
|
|
protsedura shakersort;
var j,k,l,r: integer;
x: element;
boshlanishi
l := 2; r := n; k:= n;
takrorlang
j:=r uchun l qilishgacha
agar a[j - 1].key > a[j].tugmachasi, keyin boshlang
x := a[j - 1];
a[j-1] := a[j];
a[j] := x;
k := j;
oxiri;
l := k + 1;
j uchun:= l dan r gacha
agar a[j - 1].key > a[j].tugmachasi, keyin boshlang
x := a[j - 1];
a[j - 1] := a[j];
a[j] := x;
k:=j;
oxiri ;
r := k - 1;
l > r gacha;
oxiri; {shakersort}
Pufakchali saralash va silkituvchi saralash tahlili. Oddiy almashtirish algoritmidagi taqqoslashlar soni
Shakerni saralash usuli kabi ilg'or usullarni tahlil qilish juda qiyin. Taqqoslashlarning eng kam soni. Yaxshilangan qabariq usuli uchun D. Knuth o'tishlarning o'rtacha soni proportsional ekanligini va taqqoslashlarning o'rtacha qiymati to'g'ridan-to'g'ri proportsional ekanligini aniqladi. Biroq, bundan oldin taklif qilingan barcha yaxshilanishlar birjalar soniga ta'sir qilmasligi aniq; ular faqat keraksiz qayta tekshirishlar sonini kamaytiradi. Afsuski, lekin ikkita elementni almashtirish operatsiyasi ko'pincha kalitlarni taqqoslashdan ko'ra qimmatroqdir, shuning uchun bizning barcha yaxshilanishlarimiz kutilganidan ancha kichikroq ta'sirga olib keladi.
Tahlil shuni ko'rsatadiki, ayirboshlash turi va uning ba'zi yaxshilanishlari qo'shilish va tanlab olishdan pastroqdir va pufakchali sortning mos keladigan nomdan boshqa afzalliklari borligi shubhali. Shakerni saralash algoritmi, elementlarning asosan buyurtma qilinganligi aniq bo'lganda foydali bo'ladi - juda kam uchraydigan amaliy holat.
Saralash vaqtida har qanday n ta element harakatlanadigan o'rtacha masofa n/3 joy ekanligini ko'rsatish oson. Bu raqam takomillashtirilgan, ancha samarali saralash usullarini topish uchun maslahat beradi. Har bir oddiy usul, asosan, har bir elementni har bir elementar bosqichda bir pozitsiyaga siljitadi. Shunga ko'ra, ular taxminan n 2 ta bunday bosqichga muhtoj. Har bir yaxshilanish har bir tsikl uchun elementlarni kattaroq masofaga yuborish tamoyiliga asoslanishi kerak.
1.4 Shell tartiblash
Oddiy qo'shimchalar bo'yicha saralashda biroz yaxshilanish D.L. Shell 1959 yilda. Biz bu usulni sakkiz elementli misol yordamida ko'rib chiqamiz (4.1-rasm).
4.1-rasm. Shell tartiblash
Birinchi o'tish paytida bir-biridan to'rtta pozitsiyada joylashgan barcha elementlar mustaqil ravishda yig'iladi va tartiblanadi. Bu bosqich 4-tur. Sakkiz elementli misolimizda barcha guruhlar aniq ikkita elementni o'z ichiga oladi. Keyin elementlar yana bir-biridan ikki pozitsiyada joylashgan elementlar bilan guruhlarga birlashtiriladi va yana tartiblanadi. Bu bosqich 2-tur. Nihoyat, uchinchi o'tishda har bir element oddiy tartiblash yoki 1-sort bo'yicha tartiblanadi.
Dastlab, har bir o'tishda barcha elementlar ishtirok etadigan bir nechta saralash o'tkazmalariga ehtiyoj pulni tejashdan ko'ra ko'proq mehnat talab qiladiganga o'xshaydi. Biroq, saralashning har bir bosqichida yoki nisbatan oz sonli elementlar ishtirok etadi yoki ular o'sha vaqtga qadar juda yaxshi tartiblangan va ular nisbatan kamroq almashtirishlarga muhtoj.
Bu usul oxir-oqibat tartiblangan massivni tashkil etishi aniq va har bir o'tish oldingi o'tishning umumiy summasini qo'llashi aniq, chunki har qanday i-sort oldingi 2i-sort bo'yicha tartiblangan ikkita guruhni bog'laydi. Bundan tashqari, oxirgisi 1 ga teng bo'lsa, har qanday o'sish ketma-ketligi amalga oshishi aniq, chunki eng yomon holatda, butun ish oxirgi o'tishda bajariladi. Biroq, agar o'sish ikkining kuchi bo'lmasa, kamayib borayotgan o'sish usuli yaxshi natijalar berishi aniq emas.
Shuning uchun, dastur o'sishlarning ma'lum ketma-ketligidan qat'iy nazar yaratiladi. Barcha t o'sishlar shartli ravishda shartli sifatida belgilanadi.
Har qanday h-sort oddiy inklyuziya tartiblash sifatida dasturlashtirilgan. Va qo'shilish joyini qidirishni tugatish sharti oddiy bo'lishi uchun to'siq qo'llaniladi.
Har bir h-sortning o'ziga xos to'sig'i kerakligi va dastur o'z o'rnini iloji boricha sodda tarzda aniqlashi kerakligi aniq. Shunga ko'ra, a massivga bir komponentni emas, balki [0] komponentini kiritish kerak, shuning uchun endi uni quyidagicha tasvirlash mumkin.
a: elementning massivi [-.. n];
Shell tartiblash algoritmi t = 4 uchun qanday ko'rinishga ega.
protsedura shellsort;
const t = 4;
bu yerda i,j,k,s: indeks;
x: element;
m: 1..t;
h: butun sonli massiv [1..t];
boshlanishi
h[1] := 9; h[2] := 5; h[3] := 3; h[4] := 1;
uchun m := 1 to do boshlanadi
k := h[m];
s := -k; {to'siq joyi}
i uchun := k + 1 dan n gacha boshlanadi
x := a[i]; j := ik;
agar s=0 bo'lsa, s := - k;
s := s + 1; a[s] := x;
esa x .key < a[j] .key boshlanadi
a[j+k] := a[j]; j := jk
oxiri ;
a[j+k] := x;
oxiri
oxiri
oxiri;
Shell tartiblash tahlili. Ushbu algoritmni tahlil qilib, ba'zilari hali hal qilinmagan juda murakkab matematik muammolarga duch kelish kerak. Misol uchun, o'sishlarning qaysi ketma-ketligi eng yaxshi jami hosil qilishi aniq emas. Biroq, ular bir-biridan ko'p bo'lmasligi kerak bo'lgan g'alati printsip kashf qilindi. Bu yuqoridagi misolda ko'rilgan vaziyatdan qochadi, bunda har bir saralash o'tish joyi ilgari hech qanday tarzda o'zaro ta'sir qilmagan ikkita zanjirni bog'laydi. Shu bilan birga, turli zanjirlarning o'zaro ta'siri imkon qadar tez-tez sodir bo'lishi maqsadga muvofiqdir. Shunday qilib, quyidagi nazariya shakllantiriladi:
Agar k-tartiblangan ketma-ketlik i-tartiblangan bo'lsa, u hali ham k-tartiblangan bo'ladi.
D.Knut ko'rsatdiki, o'sishlarning quyidagi ketma-ketligi (teskari tartibda aks ettirilgan) to'g'ri tanlov bo'lishi mumkin:
1, 4, 13, 40, 121, ...,
qayerda va.
Shuningdek, ularga quyidagi ketma-ketlik tavsiya qilindi
1, 3, 7, 15, 31, ...,
qayerda va.
Keyingi tahlil shuni ko'rsatadiki, ikkinchi holatda Shell tartiblash algoritmidan foydalangan holda n ta elementni saralash uchun zarur bo'lgan qo'shimcha xarajatlar n 6/5 ga to'g'ridan-to'g'ri proportsionaldir . Bu n 2 dan ancha yaxshi .
2. Qidiruv algoritmlari
2.1 Ketma-ket qidiruv
Bu algoritm faqat berilgan kalit qiymatiga ega element topilmaguncha (muvaffaqiyatli qidiruv opsiyasi) yoki roʻyxat toʻliq tekshirilgunga qadar, lekin kerakli element topilmaguncha (muvaffaqiyatsiz qidiruv) faqat berilgan roʻyxatning har bir elementini navbatma-navbat qidirish tugmasi bilan taqqoslaydi. . Ko'pincha oddiy qo'shimcha usul qo'llaniladi: agar qidiruv kaliti ro'yxatning eng oxiriga qo'shilsa, qidiruv so'zsiz muvaffaqiyatli bo'ladi, shuning uchun algoritmning har bir iteratsiyasida ro'yxat oxirini boshqarishni olib tashlash mumkin. . Quyida shunday takomillashtirilgan versiyaning psevdokodi keltirilgan; manba ma'lumotlari massiv sifatida taqdim etiladi deb taxmin qilinadi.
SequentialSearch2 algoritmi (A[0..n], K)
// Algoritm yordamida ketma-ket qidiruvni amalga oshiradi
// cheklovchi sifatida qidiruv kaliti
// Dastlabki ma'lumotlar: n ta elementdan iborat A massivi va K qidiruv tugmasi
// Chiqish ma'lumotlari: A[0..n - 1] massivning birinchi elementining joylashuvi,
// uning qiymati K bilan bir xil; element topilmasa,
// qaytariladigan qiymat -1
A[n] = K
i = 0
esa A[i] K
i = i + 1
agar i < p
qaytarish i
boshqa
Qaytish - 1
Agar dastlabki ro'yxat tartiblangan bo'lsa, yana bir yaxshilanishdan foydalanish mumkin: ushbu ro'yxatdagi qidiruv qidiruv kalitidan kattaroq yoki unga teng bo'lgan elementga duch kelgan zahotiyoq yakunlanishi mumkin.
2.2 Ikkilik qidiruv
Ikkilik qidiruv tartiblangan massivni qidirish uchun yuqori samarali algoritmdir. Bu algoritm kerakli K kalitni massivning A[m] o'rta elementi bilan solishtirish orqali ishlaydi. Tenglik bo'lsa, algoritm qidiruvni tugatadi. Aks holda, agar K < A[m] bo'lsa, massivning dastlabki yarmi uchun va K > A [m] bo'lsa, ikkinchi yarmi uchun xuddi shu amal rekursiv ravishda takrorlanadi.
Masalan, massivga ikkilik qidiruv algoritmini qo'llash orqali K = 70 kalitini topamiz. Misol 2.6-rasmda ko'rsatilgan
Guruch. 2.6 Ikkilik qidiruv misoli
Ikkilik qidiruv rekursiyada qo'llanilishi aniq bo'lsa-da, lekin u rekursiv bo'lmagan algoritm sifatida osonlik bilan amalga oshiriladi. Quyida rekursiv bo'lmagan versiyaning psevdokodi keltirilgan
Ikkilik qidiruv algoritmi (A[0..n - 1], K)
// Rekursiv bo'lmagan ikkilik qidiruvni amalga oshiradi
// Dastlabki ma'lumotlar: massiv A[0..n - 1], tartiblangan
// ortib borayotgan tartibda va kerakli qidiruv kaliti K dir
// Chiqish ma'lumotlari: massiv elementi indeksi K ga teng,
// yoki bunday element bo'lmasa -1
l = 0;
r = n - 1
lr qilish esa
t = ;
agar K = A [t]
qaytish m
agar K < A[t] bo'lsa
r = m - 1
boshqa
r = m + 1
Qaytish - 1
Ikkilik qidiruvning ishlashini tahlil qilishning keng tarqalgan usuli - kerakli kalitni massiv elementlari bilan taqqoslash sonini hisoblash. Bundan tashqari, soddalik uchun, uchlik taqqoslashlar qo'llaniladi, deb hisoblang, ya'ni. K va A[m] ni har bir taqqoslash uning A[m] qiymatiga tengligini aniqlash imkonini beradi. K kammi yoki ko'pmi.
Shunday ekan, algoritm n ta elementdan iborat massivda izlash jarayonida qancha taqqoslashni amalga oshirishi kerak? Natija, albatta, nafaqat n ga, balki berilgan topshiriq misoliga ham bog'liq. Keling, eng yomon holatda taqqoslashlar sonini aniqlaylik. Eng yomon holat qidirilayotgan kerakli kalitni o'z ichiga olmagan barcha massivlarni o'z ichiga oladi (shuningdek, ulardan tashqari, ushbu turkumga qidiruv muvaffaqiyatli yakunlanadigan boshqa massivlar ham kiradi).
Masalan, 1000 ta elementdan iborat massivda berilgan qiymatga ega elementni topish uchun (yoki kerakli element yoʻqligini aniqlash uchun) koʻpi bilan 10 ta uch karra taqqoslash kerak boʻladi. million element.
2.3 Substratlarni so'rash
Pastki qatorni qidirish masalasini shakllantirish: matn deb ataladigan n uzunlikdagi belgilar qatori va naqsh (naqsh) deb ataladigan m (m n) uzunlikdagi qator berilgan; matnda naqshga mos keladigan pastki qatorni topishingiz kerak. Boshqacha qilib aytganda, i ni topish kerak - matndagi naqshga mos keladigan birinchi pastki qatorning eng chap belgisi indeksi.
Bunday barcha pastki qatorlarni topish kerak bo'lganda, pastki qatorni qidirish algoritmi matnni yakuniy tekshirishgacha qidiruvni takrorlashi mumkin.
Qo'pol kuch algoritmi quyidagicha: shablon matn boshiga moslashtiriladi va tegishli belgilar juftlari chapdan o'ngga navbatma-navbat moslashtiriladi, to har bir m juftlikdagi belgilar teng bo'lguncha (keyin algoritm tugatilishi mumkin). ), yoki turli xil belgilar juftligi uchraydi. Ikkinchi holda, naqsh bir pozitsiyani o'ngga siljitadi va belgilarning moslashuvi naqshning boshlang'ich belgisidan matnning mos keladigan pozitsiyasidagi belgigacha taqqoslanadi. E'tibor bering, matndagi eng so'nggi pozitsiya, potentsial ravishda qidirilayotgan pastki qatorning boshlanishi bo'lishi mumkin, n - m (matndagi pozitsiyalar 0 dan n - 1 gacha bo'lgan qiymatlar bilan indekslangan bo'lsa). Naqshga mos keladigan matnda bu pozitsiyadan tashqarida juda kam belgilar mavjud. Shunday qilib,
BruteForceStriny Match algoritmi (T[0..n - 1], P[0..t - 1])
// Algoritm pastki qatorni qo'pol kuch bilan qidirishni amalga oshiradi
// Dastlabki ma'lumotlar: n ta belgidan T[0..n - 1] massiv, tashkil etuvchi
// matn; namunani tashkil etuvchi m ta belgidan P[0..m - 1] massiv
// Chiqish ma'lumotlari: matndagi boshlang'ich belgining o'rni
// namunaga mos keladigan dastlabki qidirilayotgan pastki qatorni boshlaydi;
// agar pastki satr topilmasa, - 1 ni qaytaradi
i = 0 dan p - t qilish uchun
j = 0
esa j < t va P[j] = T[i + j] qiladi
d = d + 1
j = m bo'lsa
qaytarish i
qaytish - 1
Algoritmning ishlashi rasmda ko'rsatilgan. 2.7.
Guruch. 2.7. Qo'pol kuch yordamida pastki qatorni qidirishga misol
Shuni ta'kidlash kerakki, ushbu misolda algoritm odatda har doim birinchi belgilarni taqqoslash natijalariga ko'ra naqshni harakatga keltiradi. Shunga qaramay, eng yomon vaziyat senariysi yanada yoqimsiz: algoritm shablonni ko'chirishdan oldin barcha m taqqoslashni amalga oshirishi mumkin va bu har n - m + 1 urinishda sodir bo'ladi. Ammo oddiy tabiiy tilda matndagi so'zni odatiy qidirishda, oz sonli taqqoslashlardan keyin ko'p siljishlar amalga oshirilishi mumkin (ko'rsatilgan misolga qarang). Bu shuni anglatadiki, o'rtacha holatda samaradorlik eng yomon holatda samaradorlikdan ancha yuqori bo'lishi kerak.
Xulosa
Ushbu kurs ishi eng muhim tushuncha - algoritmga, xususan, qidirish va saralash algoritmiga bag'ishlandi.
Kurs ishining birinchi bobi asosan tartiblash algoritmlariga bag'ishlandi. Unda tartiblash algoritmlarining ahamiyati, dolzarbligi va shunchaki zarurligi ko'rsatildi. Turli xil saralash usullari, saralash algoritmlarining asosiy xarakteristikalari o'rganiladi. Kurs ishi doirasi har xil turdagi qidirish va saralash algoritmlarining butun majmuasini batafsil o'rganishga imkon bermaganligi sababli, kurs ishida quyidagilar ko'rib chiqildi:
Kiritish tartibi
Oddiy tanlov bo'yicha saralash;
oddiy almashish bo'yicha saralash;
Shell tartiblash.
Turli xil qidiruv usullaridan quyidagi algoritmlar o'rganildi va taqdim etildi:
|
| |
