8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja


Havo sharcha kabi saralash (Bubble sort)



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

Havo sharcha kabi saralash (Bubble sort). Massivda chapdan o‘ngga qarab amal bajariladi. Agar joriy element keyingisidan katta bo‘lsa, ularni almashtiramiz. Buni massiv tartiblanmaguncha bajaramiz. Eʻtibor bering, birinchi iterasiyadan keyin eng katta element massivning oxirida, to‘g‘ri joylashagan bo‘ladi. Ikkita iterasiyadan keyin ikkinchi eng katta element to‘g‘ri joylashgan bo‘ladi va hokazo. Ravshanki, n ta iterasiyadan ko‘p bo‘lmagandan keyin massiv tartiblangan bo‘ladi. Shunday qilib, eng yomon va o‘rtacha holatda murakkabligi O(n2), eng yaxshi holatda esa O(n) bo‘ladi.
Shaker saralash (Shaker sort, bundan tashqari, aralashgan saralash va koktel saralash sifatida tanilgan). Havo sharcha saralash oxirida kichik elementlar joylashtirilgan testlarda sekin ishlaydi (baʻzan "tashboqa" deb ataladi). Bu element algoritmning har bir qadamida chap tomonga faqat bitta pozitsiyaga harakat qiladi. Shuning uchun nafaqat chapdan o‘ngga, balki o‘ngdan chapga ham o‘tadi. Massivning tartiblanmagan qismini aniqlash uchun ikkita begin va end ko‘rsatikichni qo‘llab quvvatlaydi. Keyingi iterasiyada endga etganimizda undan birini ayiramiz va o‘ngdan chapga ko‘chamiz. Xuddi shunday, beginga etganimizda unga birini qo‘shamiz va chapdan o‘ngga ko‘chamiz . Algoritm havo sharcha saralash bilan bir xil murakkabligi bor, lekin real vaqtda yaxshi ishlaydi.
void shakersort(int* l, int* r) { int sz = r - l;
if (sz <= 1) return; bool b = true;
int* beg = l - 1; int* end = r - 1; while (b) {
b = false; beg++;
for (int* i = beg; i < end; i++) { if (*i > *(i + 1)) {
swap(*i, *(i + 1)); b = true;
}
}
if (!b) break;
end--;
for (int* i = end; i > beg; i--) { if (*i < *(i - 1)) {
swap(*i, *(i - 1)); b = true;
}}}}
Taroqsimon caralash (Comb sort). Shaker saralashning yana bir o‘zgartirilgani. "Toshbaqalar" dan qutulish uchun masofada turgan elementlarni qayta tashkil qilamiz. Keling, uni tuzatamiz va chapdan o‘ngga boramiz, bu masofada turgan elementlarni taqqoslaymiz, agar kerak bo‘lsa, ularni qayta tartibga solaylik. Shubhasiz, bu "toshbaqalar"ni tez qator boshiga olish imkonini beradi. Dastlab qator uzunligiga teng masofani olib, so‘ngra uni taxminan 1.247 ga teng bo‘lgan biror koeffitsientga bo‘lish maqbuldir. Masofa bir biriga teng bo‘lganda shaker saralash bajariladi. Eng yaxshisi, murakkabligi O(nlogn), eng yomoni, u O(n2). O‘rtacha murakkabligi nima uchun juda aniqmas, amalda O(nlogn) kabi ko‘rinadi.

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