|
k-қадам. k-1 қадамда ҳосил бўлган кетма-кетлик оддий қўшиш усули орқали сараланади.
Эслатма: r1>r2>…>rk-1>rk=1.
Мисол:
1-қадам. r1=8, яъни (a[0], a[8]), (a[1], a[9]), ... , (a[7], a[15]).
12
|
8
|
14
|
6
|
4
|
9
|
1
|
8
|
13
|
5
|
11
|
3
|
18
|
3
|
10
|
9
|
12
|
8
|
14
|
6
|
4
|
9
|
1
|
8
|
13
|
5
|
11
|
3
|
18
|
3
|
10
|
9
|
2-қадам. r2=4, яъни (a[0], a[4], a[8], a[12]), ..., (a[3], a[7], a[11], a[15]).
12
|
5
|
11
|
3
|
4
|
3
|
1
|
8
|
13
|
8
|
14
|
6
|
18
|
9
|
10
|
9
|
3-қадам. r3=2, яъни (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]), (a[1], a[3], a[5], a[7], a[9], a[11], a[13], a[15]).
4
|
3
|
1
|
3
|
12
|
5
|
10
|
6
|
13
|
8
|
11
|
8
|
18
|
9
|
14
|
9
|
4-қадам. r4=1, яъни (a[0], a[2], … , a[15]).
1
|
3
|
4
|
3
|
11
|
5
|
11
|
6
|
12
|
8
|
13
|
8
|
14
|
9
|
18
|
9
|
1
|
3
|
3
|
4
|
5
|
6
|
8
|
8
|
9
|
9
|
10
|
11
|
12
|
13
|
14
|
18
|
Изоҳ
Гарчи таққослашлар сони бир мунча ортиб борсада, элементларни ўринлаштиришлар анча кам бўлади.
Бу усул натижасида ҳар бир ўтишдан кейин саралашлар камайиб боради. Энг ёмон ҳолатда охирги ишни яккалик саралаш амалга оширади.
Эслатма
Шелл саралаш усулининг ягона тавсифи ҳар бир ўтишдан кейин қадамларни тўғри танлашдан иборат.
Қадамларни танлаш:
Р.Седжвик таклиф этган қадамлар:
Усул самарадорлиги:
Ўртача ҳолат - O(n7/6),
Энг ёмон ҳолат - O(n4/3).
Эслатма
Седжвик усули орқали қадамлар танланаётганда, агар 3*inc[s]>n бўлса, у ҳолда энг катта қадам inc[s-1] бўлади.
Шелл саралаши. Дастур коди
void shell(int *items, int count)
{
int i, j, qadam, k;
int x, a[]={7,3,2,1};
for(k=0; k < 4; k++) {
qadam = a[k];
for(i= qadam; i < count; ++i) {
x = items[i];
for(j=i- qadam; (x < items[j]) && (j >= 0); j=j- qadam)
items[j+ qadam] = items[j];
items[j+ qadam] = x;
}
}
}
Пирамидасимон саралаш
Def.
Пирамида деб баландлиги k бўлган шундай бинар дарахтга айтиладики, бунда
- k-1 дарахт идеал мувозанатланган;
- k-1 босқич тўла, k босқич эса чапдан ўнга томон тўлатилади.
<а1,а2,…, аi ,…,an> пирамида i учун (аi ≥ а2i ) (аi ≥ а2i +1 )
Пирамидани массив кўринишида тасвирлаб олиш мақсадга мувофиқ бўлади.
Алгоритм
- Бошланғич кетма-кетликдан пирамида шаклантирилади.
- Кириш ва тайёр кетма-кетлик битта массивда сақланади. Пирамида бошини оламиз ва тайёр кетма-кетликка жойлаштирамиз. Кейин қолган элементлар учун пирамидани тиклаймиз. Мазкур жараён барча элементлар тугагунча давом этилади.
Пирамида қуришга мисол
Қадам
Қадам
Қадам
Қадам
Қадам
Чиқиш
Пирамидани саралаш
алмаштириш
алмаштириш
алмаштириш
алмаштириш
шакллантириш
шакллантириш
шакллантириш
шакллантириш
алмаштириш
шакллантириш
алмаштириш
шакллантириш
алмаштириш
шакллантириш
алмаштириш
шакллантириш
алмаштириш
Самарадорлик: T(n)=O(nlogn)
Тез саралаш (Quicksort)
Алгоритм ғояси
Бу усул алмаштириш усулидаги саралашга тегишли бўлиб унинг асосини калитларни танланган калитга нисбатан алмаштириш ташкил қилади.
Мисол:
Самарадорлик: T(n)=O(nlogn)
Тезкор саралаш дастур коди
void quick_sort(int *items, int left, int right)
{
int i = left; j = right, x = items[(left+right)/2]; /* выбор компаранда */
do {
while((items[i] < x) && (i < right)) i++;
while((x < items[j]) && (j > left)) j--;
if(i <= j) {
int y = items[i];
items[i] = items[j];
items[j] = y;
i++; j--;
}
} while(i <= j);
if(left < j) quick_sort(items, left, j);
if(i < right) quick_sort(items, i, right);
}
Мавзу бўйича назорат саволлари - Shell саралаши
- Пирамида тушунчаси ва уни қуриш
- Пирамидасимон саралаш
- Тез саралаш тушунчаси
Ma'lumotlarni saralash algoritmlari. TAD kafedrasi Sharipov Bahodir Akilovich
Ma'lumotlarni saralash algoritmlari.
- Saralash tushunchasi va uning vazifasi.
- Saralashning qat’iy usullari va ularning samaradorligi.
1. Saralash tushunchasi va uning vazifasi.
Saralash – bu berilgan to‘plam elementlarini biror bir tartibda (o‘sish yoki kamayish) joylashtirish jarayonidir.
Saralash (inglizcha sorting - tasniflash, tartiblash) - tanlangan mezonga qarab biror narsani ketma-ket joylashtirish yoki guruhlarga bo'lish.
Saralash– bu massiv elementlarini tartiblash (o’sish, kamayish, oxirgi raqami, bo’luvchilari bo’yicha, …)
Saralash deb, berilgan obyektlar ketma-ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin.
Ma'lumotlarni saralash - uni qandaydir atributga ko'ra tartibga solishdir.
Saralashdagi qiyinchiliklar quyidagi hollarda mavjud bo’ladi:
❌ ma'lumotlar massivlari katta bo’lganda - minglab, o'nlab va yuz minglab elementlar;
❌ ma'lumotlarga murojaat qilish qiyin bo'lishi mumkin (masalan, ular ma’lumotlar oqimi bo’lganda);
❌ kompyuterning imkoniyatlari yetarli emas va dasturlash tiliga kiritilganidan ko'ra tejamkorroq algoritmlar kerak.
Bunday hollarda saralashning ixtisoslashtirilgan algoritmlarini tanlash kerak, zarurat bo’lsa ularni masalaga qarab optimallashtirish mumkin.
Saralashdan maqsad - tartiblangan to‘plamda kerakli elementni topishni osonlashtirishdan iborat.
- dasturlarni translyasiya qilishda;
- ma’lumotlar majmuasini tashqi xotirada tashkil qilishda;
- kutubxonalar, kataloglar, ma’lumotlar bazasini yaratishda va boshq.
Saralashning tadbiqi
Saralash masalasini formal qo‘yilishi
Berilgan: a1, a2 ,…, an, ob’ektlar to‘plami.
Talab qilinadi: Berilgan ob’ektlarni tartiblash, ularni shunday ap1, ap2 ,…, apn ketma-ketlikda o‘rinlashtirish lozimki, bunda ularning kalitlari kamaymaydigan tartibda joylashsin: kp1 kp2 … kpn.
Def.
Saralash algoritmi turg‘un deyiladi, agarda saralash natijasida bir hil kalitli ob’ektlarlar bir-biriga nisbatan o‘rinlarini o‘zgartirmasa.
Do'stlaringiz bilan baham: |
