27- амалий машғулот Mavzu: Massivlarni tartiblash va saralash doir dastur tuzish

27- амалий машғулот  
Mavzu: Massivlarni tartiblash va saralash doir dastur tuzish.  
Reja:  
1.  
Massivlarni tartiblash va saralash doir dastur tuzish.  
2.  
Mustaqil topshiriqlar bajarish.  
  
Mashg’ulotning  maqsadi:  
1.  
Massivlarni tartiblash va saralash doir dastur tuzishni o’rganish.  
2.  
Massivlarni tartiblash va saralash doir dastur tuzish ko’nikmalarini  
shakllantirish.  
    
  
Dars o’tish usuli: Takrorlash, suhbat va savol-javob, mavzu mazmunidan  
kelib chiqib talabalarga mustaqil topshiriqlar berish va ularni tasavvurini bilish.  
  
Dars o’tish vositalari:  Doska,o’uv va uslubiy qo’llanma, topshiriqlar  
majmuasi.  
  
Dars mazmuni:  
  
Darsning xronologik xaritasi – 80 minut.  
1.  
Tashkiliy qism – 2 minut  
2.  
Talabalar bilimi darajasini aniqlash – 10 minut  
3.  
Yangi mavzu o’tish (komputerda mustaqil topshiriq) – 50 minut  
4.  
Yangi mavzu ni o’zlashtish darajasini aniqlash- 10 minut.  
5.  
Sinov savollari – 5 minut.  
6.  
Uyga vazifa – 3 minut  
  
  
  
  
  
  

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