8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja


Tezkor saralash (quicksort)



Download 184,65 Kb.
bet5/14
Sana06.08.2022
Hajmi184,65 Kb.
#846556
1   2   3   4   5   6   7   8   9   ...   14
Bog'liq
8-m

Tezkor saralash (quicksort). Baʻzi mos yozuvlar elementini tanlaylik. Shundan so‘ng chapdan kichik bo‘lgan barcha elementlarni, katta bo‘lganlarini esa o‘ng tomonga harakatlantiramiz. Takrorlanuvchi qismlarning har biridan rekursiv chaqirish mumkin. Natijada tartiblangan massivga ega bo‘lamiz, chunki har bir katta elementdan oldin massivdan kichik bo‘lgan har bir element joylashtirilgan. Murakkabligi: O(nlogn) o‘rtacha va eng yaxshi holda, O (n2) eng yomon holda. Malumot elementi noto‘g‘ri tanlanganda eng yomon reytingga erishiladi. Bu algoritmni amalga oshirish butunlay standart hisoblanadi, bir vaqtning o‘zida chapga va o‘ngga borib, elementlarni juft topish, bunda chap element mos yozuvlari tanlangandan katta ekanligini va o‘ng kichik, ular almashtiriladi. Sof tezkor tartiblashdan tashqari, elementlar soni kam bo‘lganda tartiblashni joylashtirishga, taqqoslashda ham saralash ishtirok etdi. Qo‘shish orqali saralash vazifa uchun mos bo‘lgan eng yaxshi saralashdir va doimiy sinov orqali tanlanadi.
8.10-dastur. Saralashni amalga oshirish.
Birinchi variant
void quicksort(int* l, int* r) { if (r - l <= 1) return; int z = *(l + (r - l) / 2); int* ll = l, *rr = r - 1; while (ll <= rr) {
while (*ll < z) ll++; while (*rr > z) rr--; if (ll <= rr) {
swap(*ll, *rr); ll++;
rr--;
}
}
if (l < rr) quicksort(l, rr + 1); if (ll < r) quicksort(ll, r);
}
Ikkinchi variant
void quickinssort(int* l, int* r) { if (r - l <= 32) {
insertionsort(l, r); return;
}
int z = *(l + (r - l) / 2); int* ll = l, *rr = r - 1; while (ll <= rr) {
while (*ll < z) ll++; while (*rr > z) rr--; if (ll <= rr) {
swap(*ll, *rr); ll++;
rr--;
}
}
if (l < rr) quickinssort(l, rr + 1); if (ll < r) quickinssort(ll, r);
}
Birlashtirish orqali saralash (Merge sort). Bo‘lish-boshqarish paradigmasi asosida tartiblash. Massivni ikkiga bo‘lamiz, qismlarni rekursiv ravishda tartiblang va keyin birlashtirish protsedurasini bajaring. Birinchi qismning joriy elementiga, ikkinchisi ikkinchi qismning joriy elementiga ikkita ko‘rsatkichni qo‘llang. Bu ikki elementdan minimumni tanlab, javobga joylashtiring va minimumga mos keladigan ko‘rsatgichni siljiting. Birlashtirish O(n), barcha logn darajalari uchun ishlaydi, shuning uchun murakkabligi O(nlogn). Bu oldindan vaqtinchalik masiv yaratish va vazifaga argument sifatida o‘tishi samarali bo‘ladi. Bu saralash rekursiv, hamda tez va shuning uchun elementlar soni kam bo‘lgan kvadratik o‘tish mumkin.
8.11-dastur. Saralashni amalga oshirish.
Asosiy funksiya
void merge(int* l, int* m, int* r, int* temp) { int *cl = l, *cr = m, cur = 0;
while (cl < m && cr < r) {
if (*cl < *cr) temp[cur++] = *cl, cl++; else temp[cur++] = *cr, cr++;}
while (cl < m) temp[cur++] = *cl, cl++; while (cr < r) temp[cur++] = *cr, cr++; cur = 0;
for (int* i = l; i < r; i++)
*i = temp[cur++];
}
Birinchi varinat
void _mergesort(int* l, int* r, int* temp) { if (r - l <= 1) return;
int *m = l + (r - l) / 2;
_mergesort(l, m, temp);
_mergesort(m, r, temp); merge(l, m, r, temp);
}
void mergesort(int* l, int* r) { int* temp = new int[r - l];
_mergesort(l, r, temp); delete temp;
}
Ikkinchi varinat
void _mergeinssort(int* l, int* r, int* temp) { if (r - l <= 32) {
insertionsort(l, r); return;
}
int *m = l + (r - l) / 2;
_mergeinssort(l, m, temp);
_mergeinssort(m, r, temp); merge(l, m, r, temp);
}
void mergeinssort(int* l, int* r) { int* temp = new int[r - l];
_mergeinssort(l, r, temp); delete temp;
}

Download 184,65 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   ...   14




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish