Oʻzbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi mirzo ulug‘bek nomidagi milliy universitetininig jizzax filiali

OʻZBEKISTON RESPUBLIKASI OLIY TA’LIM, FAN VA INNOVATSIYALAR VAZIRLIGI

MIRZO ULUG‘BEK NOMIDAGI MILLIY UNIVERSITETININIG JIZZAX FILIALI

AMALIY MATEMATIKA FAKULTETI

«KOMPYUTER ILMLARI VA DASTURLASHTIRISH» kafedrasi

“ALGORITMLAR VA BERILGANLAR STRUKTURASI” FANIDAN

4-MUSTAQIL ISHI

Mavzu: Bubble sort algoritmi.
Bajardi: “Axborot tizimlari va texnologiyalari” yoʻnalishi
2-kurs 21-21 guruh talabasi Bo’riboyev Diyor

Tekshirdi: Tojiyev Ma’ruf

Jizzax – 2023
2-variant Bo’riboyev Diyor

Variant	M1	M2	M3	M4
2	2	8	4	27

Mavzu: Bubble sort algoritmi.
Reja:

1. 
   Bubble sort algoritmi haqida umumiy ma’lumot
   
2. 
   Bubble sort algoritmining berilish usullari
   
3. 
   Bubble sortning algoritmi va dasturi
   

Eng ko’p qo’llaniladigan saralash algoritmlaridan biri bu Pufakchali (bubble sort) saralash algoritmidir. Pufakchali saralash algoritmi har bir o'tishda qo'shni elementlarni qayta-qayta taqqoslaydi va almashtiradi (agar kerak bo'lsa) . Bubble Sortning i-o'tish joyida (o'sish tartibida) oxirgi (i-1) ta elementlar allaqachon tartiblangan bo’ladi va i-eng katta element (N-i)-pozitsiyaga joylashadi

Bubble sort ikki qo'shni elementni solishtirish va ular mo'ljallangan tartibda bo'lmaguncha, ularni almashtiradigan tartiblash algoritmidir. Xuddi suv yuzasiga ko'tarilgan havo pufakchalarining harakati kabi, massivning har bir elementi har bir iteratsiyada oxirigacha harakat qiladi. Shuning uchun u pufakchali saralash deb ataladi.
“Bubble sort” bu eng sodda, ketma-ketlikdagi har bir sonni boshqa sonlar bilan solishtirishga asoslangan algoritm hisoblanadi. Unda yonma-yon turgan elementlardan chapdagisi o‘ngdagidan kattaligi aniqlansa, bu ikkala son o`rni almashtiriladi. Bu jarayon almashtirish kerak bo`lmay qolguncha davom etadi, ya`ni barcha elementlar o‘sish tartibida bo‘lib qolguncha.
“Bubble sort” nisbatan ko`p vaqt talab qiluvchi saralash algoritmi hisoblanadi. Chunki unda n ta element uchun takrorlanishlar soni taqriban n*n ga teng. Bu, n kichik son bo`lsa unchalik sezilmaydi. Sababi, hozirgi zamonaviy kompyuterlar uchun bu takrorlanish soni qiyinchilik tug`dirmaydi. Ammo butun boshli ma`lumotlar bazasidagi ma`lumotlarni saralash talab etilsachi? Albatta vaqtdan yutqazamiz. Ammo, bu algoritm saralash algoritmlarini tushunib olish uchun ilk qadam hisoblanadi.
Pufakchali saralash (Bubble sort). Ushbu algoritmda massivni takrorlash bilan boshlaymiz va birinchi elementni ikkinchisiga taqqoslaymiz va agar ular notoʻgʻri tartibda joylashgan boʻlsa, ularni almashtiramiz, keyin ikkinchi va uchinchisini taqqoslaymiz va hokazo. Ushbu takrorlashdan soʻng eng katta element quyida keltirilgan rasmda koʻrsatilgandek massivning oxiriga oʻtadi. Endi eng katta element oʻz joyini egallaydi, shuning uchun biz yana ushbu jarayonni takrorlaymiz va allaqachon oʻz pozitsiyalarida boʻlgan elementlarni qoldiramiz va bu tartiblangan massivni beradi. Butun jarayonni quyidagi bosqichlarda yozishimiz mumkin:
1) Massiv boʻyicha takrorlashni boshlash.
2) Qoʻshni elementlarni solishtirish. Masalan, birinchi va ikkinchi,
ikkinchi va uchinchi va boshqalar.
3) Agar ular tartiblangan boʻlmasa, ularni almashtirish.
4) Toʻgʻri pozitsiyalariga joylashtirilgan elementlardan tashqari, ushbu
amallarni takrorlash.
Quyidagi jadval bo’yicha Bubble sortda ishlash prinsipini ko’rib chiqamiz:

5

1

8

3

9

2

5

1

8

3

9

2

1. Qadam

1

5

8

3

9

2

1

5

3

8

9

2

1

5

3

8

2

9

2. Qadam

1

3

5

8

2

9

1

3

5

2

8

9

3. Qadam

1

3

2

5

8

9

4. Qadam

1

2

3

5

8

9

5. Qadam

Quyidagi misolda Bubble sort algoritmining ketma-ketlik holatini va uning ishlash prinsipini ko’ramiz

“5 1 4 2 8” raqamlari massivini oling va pufakchali tartiblash yordamida massivni eng kichik sondan eng katta raqamga tartiblang. Har bir bosqichda qalin harf bilan yozilgan elementlar taqqoslanadi. Uchta o'tish kerak bo'ladi;
Birinchi o'tish

• 
  (5 1 4 2 8) → (1 5 4 2 8), Bu yerda algoritm dastlabki ikki elementni taqqoslaydi va 5 > 1 dan keyin almashinadi.
  
• 
  (1 5 4 2 8) → (1 4 5 2 8), 5 > 4 dan beri almashtirish
  
• 
  (1 4 5 2 8) → (1 4 2 5 8), 5 > 2 dan beri almashtirish
  
• 
  (1 4 2 5 8) → (1 4 2 5 8), Endi bu elementlar tartibda boʻlgani uchun (8 > 5), algoritm ularni almashtirmaydi.
  

Ikkinchi o'tish

• 
  (1 4 2 5 8) → (1 4 2 5 8)
  
• 
  (1 4 2 5 8) → (1 2 4 5 8), 4 > 2 dan beri almashtirish
  
• 
  (1 2 4 5 8) → (1 2 4 5 8)
  
• 
  (1 2 4 5 8) → (1 2 4 5 8)
  

Endi massiv allaqachon tartiblangan, lekin algoritm uning tugallanganligini bilmaydi. Algoritm tartiblanganligini bilish uchun uni almashtirishsiz yana bitta to'liq o'tish kerak.
Uchinchi o'tish

• 
  (1 2 4 5 8) → (1 2 4 5 8)
  
• 
  (1 2 4 5 8) → (1 2 4 5 8)
  
• 
  (1 2 4 5 8) → (1 2 4 5 8)
  
• 
  (1 2 4 5 8) → (1 2 4 5 8)
  

Algoritmi va dasturi
Quyidagi algoritm C# dasturlash tilida qilingan

using System;

namespace BubbleSort

{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Massiv quyidagicha berilgan: ");
int[] a = { 5, 1, 4, 2, 8 };
int t;
for (int i=0; i{
Console.Write(a[i]+" ");

}
for (int j=0; j
{
for (int i = 0; i < a.Length - 1; i++)
{
if (a[i] > a[i + 1])
{
t = a[i + 1];
a[i + 1] = a[i];
a[i] = t;
}
}
}
Console.WriteLine();
Console.WriteLine("Saralangan holatidagi natija: ");
foreach (int array in a)
Console.Write(array+ " ");
}
}
}