Dasturiy ta’minot ishlab chiqish masalasining qo‘yilishi 6

4.1 Oddiy misol: Bubblesort

Ma’lumotlar maydonini rez-tez ko‘tariluvchi va pasayuvchi yo‘nalish bo‘yicha navlab turish zarur (Array). Buning uchun bir nechta algoritmlar mavjud. Algoritm BubbleSort shuni bajaradi, eng yirik unsurlar sovun ko‘piklari singari ko‘tariladi, eng yirik sovun ko‘pigi ohirida eng balandda, eng kichigi esa eng pastda joylashadi.

Vazifa
BubbleSort algoritmida har doim ikkita yonma-yon joylashgan unsurlar bir-biri bilan qiyoslanadi. Bir unsur ikkinchisidan katta, unda har ikkala belgilar o‘rni almashtiriladi. So‘zimizga kichkina misol.


Dastlabki holat:
19 5 32 8


Birinchi ko‘rikdan o‘tkazish


19 5 32 8 >> 5 19 32 8
5 19 32 8 >> 5 19 32 8
5 19 32 8 >> 5 19 8 32


Ikkinchi ko‘rikdan o‘tkazish
5 19 8 32 >> 5 19 8 32
5 19 8 32 >> 5 8 19 32
5 8 19 32 >> 5 8 19 32

Har bir o‘tkazishda ma’lumotlar maydonining alohida elementi (Arrayelement) keyingisi bilan qiyoslanadi. Ma’lumotlar maydonining har bir elementida bitta tashqi va bitta ichki sikl bajariladi. Bu holatda bu erda to‘rtta siklik bajaruv bo‘ladi to‘g‘ri, ma’lumotlar maydonining bu namunasida (Array) ikkita ko‘rik o‘tkazuvidan keyinoq to‘g‘ri ajratilgan. Tegishli nazorat tekshiruvi yordamida endi navlarga ajratishni to‘xtatsa ham bo‘ladi, biroq «asosiy versiya» uchun birinchi marta bu kerak emas.

Dasturning bajarilishi
BubbleSort-algoritm funksionalligini yaxshi Nassi/Shneidermann-Diagramm diagrammasi bilan ham ko‘rsatish mumkin edi, unga mos kodlash (deyarli) har qanday tilda amalga oshishi mumkin.

BubbleSort Algorithm
	x from 0 to ArrayLength
		y from 0 to ArrayLength
			y < ArrayLength yes		no
			Array[y] > Array[y+1] yes	no
			temp = Array[y]
			Array[y] = Array[y+1]
			Array[y+1] = temp

4.1-rasm. BubbleSort dasturining Nassi/Shneidermann-Diagramm diagrammasi

Element uning orqasidagi elementdan katta emasligini tekshirishdan keyingi tekshirish mavjud. Ikkinchi so‘roqda ma’lumotlar maydoning y+1 indeksi foydalanishi sababli ma’lumotlar maydonining eng yuqoriga indeksidan (ArrayLength) kichik bo‘lishi kerak. U eng katta element, deb faraz qilamiz, unda y+1 ma’lumotlar maydoni chegarasidan tashqaridagi xotira doirasida yotadi, biroq u mumkin bo‘lgan qiymatga ega bo‘lmaydi. Ba’zi kompilyatorlar (Compiler) bu o‘rinda ushbu so‘roqdan o‘tkazish bo‘lmasa darrov bajarilgan bo‘ladi (bu erda u juda ma’qul va foydalidir).

Shunday qilib «agar» (if-so‘rov) ichki so‘rovda eng muhim element uning ortitagi elementdan kattami, degan savol tekshiriladi. Agar shunday bo‘lsa, har ikkala qiymat o‘rni almashtiriladi.
Bu namunada ko‘tariluvchi izchillikda saralash o‘tkaziladi. Agar saralashni pasayuvchi izchillikda olib borish zarur bo‘lsa, qiyoslashni atigi “nisbatan katta”dan “nisbatan kichikka o‘zgartirish kerak bo‘ladi”.