|
224
1- vazifa
1)
20
2
1
,...,
,
x
x
x
massivning musbat elementlari yig‘indisini hisoblash algoritmi
va dasturini tuzing.
Masalani yechish dasturi.
Program massiv;
type n=1..20;
var X:array [n] of real; i:integer; S:real;
begin S:=0;
for i:=1 to 20 do read(X[i]);
if X[i]>= 0 then S:=S+X[i];
writeln(‘S=’,S);
end.
Saralash algoritmlari: pufakchalarni saralash va birlashma navlari o'rtasidagi farq
AlgoritmlarJavascript
Joylashtirilgan 10-10-2019
Saralash algoritmlari: pufakchalarni saralash va birlashma navlari o'rtasidagi farq
Saralash kontseptsiyasi server tomonlarini ishlab chiqishda juda katta ahamiyatga ega va informatika uchun juda muhimdir.
Dasturiy ta'minot ishlab chiqaruvchisi bo'lish safari davomida, men algoritmlarni saralash juda qiziqarli ekanligini ko'rdim va bir xil safarda boshqalarga yana ikkita taniqli algoritmlarni tushunishga yordam berishni xohlardim: Bubble Sort va Merge Sort.
Keyingi bo'limlarda, men ikkala algoritmni JavaScript-da - psevdokodda va barchasini bajarishda yurib boraman - o'zingizga o'xshash turlarni qanday amalga oshirish haqida tushunchangizni mustahkamlashga yordam beraman. Men o'zimni algoritmlar bo'yicha mutaxassis deb hisoblamayman; hali ham juda o'quvchi. Shuning uchun, men ushbu echimlarni amalga oshirishda yordamchi funktsiyalardan foydalanaman. Bularning barchasini oxiriga etkazganimizda ko'proq deklarativ kodni (ya'ni oddiy ingliz tilida o'qiydigan kodni) olishimiz qo'shimcha foyda keltiradi.
Pufakchalarni saralash: taqqoslash algoritmi
Bubble Sort tartiblash uchun iterativ yondashuvni - matritsaga o'xshash tarzda elementlarni aylanib o'tishni talab qiladi va birinchi tartiblash algoritmini amalga oshirishni boshlash uchun juda yaxshi joy.
Shunday qilib, u qanday ishlaydi: saralanmagan massiv berilgan bo'lsa, ushbu massivning to'liq uzunligi uchun biz har bir elementdan o'tamiz; uni yonidagi element bilan taqqoslash. Agar birinchi element ikkinchisidan kattaroq bo'lsa, biz ikkita elementni almashtiramiz.
Bu "puflash" effektini yaratadi, unda eng kichik elementlar (bizning holatlarimizda) har bir pas bilan ro'yxatning old tomoniga o'tadi.
Yuqorida aytib o'tganimdek, qabariq turini amalga oshirishda yordamchi funktsiyalardan foydalanish kodni o'qishga osonroq qiladi, shuning uchun men quyidagilarni bajarishni boshlayman.
Bir-biriga mos keladigan taqqoslash funktsiyasi
Birinchidan, biz toza yordamchi funktsiyani aniqlaymiz - kirishni qabul qiladigan va hech narsa o'zgartirmasdan bizga beradigan funktsiyani inAscendingOrder deb nomlaymiz. Ushbu funktsiya berilgan massivda ikkita elementni oladi, ularni taqqoslaydi va natijaga qarab mantiqiylikni qaytaradi.
O'zgartirish funktsiyasi
Keyinchalik, ro'yxatdagi ikkita elementni almashtiradigan funktsiyani aniqlaymiz. Buni toza funktsiya deb atay olmaymiz. Nima uchun? Keyinchalik undan foydalanganda tashqi ta'sir doirasiga (bizning pufakchalarni navbati bilan) ta'sir qiladi.
Pufakning haqiqiy turini joriy qilish
Va nihoyat, biz pufakchalarni saralash algoritmini aniqlamoqchimiz.
Kodni kiritishdan oldin, tushunish uchun foydali bo'lishi mumkin bo'lgan bir nechta narsani eslatmoqchiman:
(1) Men "davlat" tushunchasini ishlatmoqchiman, bu mening funktsiyam metadata o'z-o'zidan saqlanib qoladi va kirish qatorini saralashni tugatgandan keyin bizga xabar bering;
(2) Men ketma-ketlikdan orqaga o'taman. Nima degani bu? Pufakni saralash uchun biz ichkaridan qilingan ko'chadan foydalanamiz. Tashqi pastadir bizning o'tishimiz yo'nalishi va uzunligini boshqaradi, shuning uchun men o'z döngümni massivning oxirgi elementidan boshlayman va 0 ni indekslash uchun harakat qilaman. Nega biz orqaga aylanmoqdamiz? Bu shunday qiladiki, pastadir uchun ichki, almashtirish bilan shug'ullanadigan halqa, o'z ishini bajarish uchun kamroq ish talab qiladi; allaqachon saralangan elementlarni topshirishda qo'shilgan vazifadan qochish. Umid qilamanki, nimani nazarda tutayotganimni ko'rasiz:
Birlashtirish: Rekursiv saralash algoritmi
Birlashtirish Sort, boshqa tomondan, saralashga bo'linish va zabt etish usullarini qo'llaydi; rekord darajadagi kirish massivini buzib tashlaganimizda, biz ko'p o'lchovli subarrayslarni ajratib bo'lmagunimizcha va oxirida yana birlashtirishimiz mumkin.
Birlashtirish tartibini amalga oshirishda yordamchi funktsiyalardan ham foydalanaman (kod deklarativligini saqlash uchun):
Ajralgan yordamchi funktsiyasi
Birlashtirish yordamchisi funktsiyasi
Eslatma: Kodni tahlil qilayotganda, siz o'zingizni qiziqtirgan savol paydo bo'lishi mumkin: kuting, nima uchun u bu qo'shilish funktsiyasini bajarish uchun javascript-ning ichki shifrlash usulidan foydalanmadi. Shiftni ishlatish bizning algoritmimizdan ko'proq ishlashni talab qiladi, chunki har bir elementni o'tib, har birini bittadan siljitish kerak va shu bilan ishlar sekinlashadi. MergeSort samaradorligini optimallashtirish uchun biz buni chiziqli operatsiya sifatida saqlamoqchimiz (bu haqda keyinroq).
Va nihoyat, bu erda ikkala yordamchi funktsiyadan foydalanadigan bizning rekursiv birlashtirish turiga oid echimimiz bor ...
Pufakchalarni saralash va saralash turlarini taqqoslash: vaqt murakkabligini tahlil qilish
Xo'sh, nima uchun birini boshqasidan ustun tanlash kerak?
Ularning ikkalasi ham o'zining ijobiy va salbiy tomonlariga ega, ammo katta hajmdagi ma'lumotlar to'plamini (yoki "katta ma'lumotlar") saralashga kelsak, pufakchali saralash tezda samarasiz bo'ladi. Qayerda bo'lsa, ma'lumotlar to'plami o'sib borishi bilan Merge Sort samaraliroq bo'ladi.
Big-O Notation va vaqt murakkabligi tushunchasi bilan tanishib chiqsangiz, bu yanada mazmunli bo'ladi. Vaqt murakkabligi nimada? Asosan, biz algoritmning ishlashini yoki berilgan kiritish uchun muammoni hal qilishga qancha vaqt ketishini tahlil qilish uchun vaqt murakkabligidan foydalanamiz. Buni chuqurroq o'rganishingizga yordam beradigan hiyla varaqasi.
Eng yaxshi holatda, kichikroq ma'lumotlar to'plamida qabariq turi O (n), eng yomon stsenariy esa O (n²) vaqt murakkabligiga ega (bu juda yomon).
Boshqa tomondan, birlashtirish sort vaqtni O (n log (n)) murakkabligi bilan juda izchil amalga oshiradi. Birlashtiruvchi navlarni ajratish bo'yicha yordamchi funktsiyalarimizning vaqt murakkabligi bunga imkon beradi.
Turlarini o'rganish uchun saralash algoritmlari juda ko'p va bu dasturiy ta'minot muhandisligi, mashinasozlik va boshqa fanlar sohalarida ish yuritayotganlarga eng ommabop ikkita narsani yaxshiroq bilib olishga yordam beradi deb umid qilaman.
Shuningdek qarang
Do'stlaringiz bilan baham: | 
