Dasturlash asoslari

4.1 Oddiy misol: Bubblesort

Ma’lumotlar maydonini tez-tez ko‘tariluvchi va pasayuvchi yo‘nalish bo‘yicha navlab turish zarur (Array). Buning uchun bir nechta algoritmlar mavjud. BubbleSort algoritmi juda tez algoritim hisoblanmaydi, lekin u etarlicha soda bo‘lgani tufayli endigina ushbu sohaga kiruvchilarga ham tushunarli. BubbleSort deb atalishiga sabab - bunda yirik elementlar sovun ko‘pigi kabi ko‘piradi, natijada eng yirik elementlar yuqorida va eng kichik elementlar esa pastga cho‘kadi.

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 funktsionalligini yaxshi Nassi/Shneidermann-Diagramm diagrammasi bilan ham ko‘rsatish mumkin edi, unga mos kodlash (deyarli) har qanday dasturlash tilida 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 o‘zidan keyingi elementdan katta emasligini tekshirishdan navbatdagi tekshirish amalga oshiriladi. Ikkinchi so‘roqda ma’lumotlar maydoning y+1 indeksi foydalanishi sababli y indeksi ma’lumotlar maydonining eng yuqori indeksidan (ArrayLength) kichik bo‘lishi kerak. y 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 ketma-ketlikda saralash o‘tkaziladi. Agar saralashni pasayuvchi ketma-ketlikda olib borish zarur bo‘lsa, qiyoslashni atigi “nisbatan katta”dan “nisbatan kichikka o‘zgartirish kerak bo‘ladi”.