Саноатни ахборотлаштириш факультети” “информатика ва ахборот технологиялари” кафедраси

ЎЗБЕКИСТОН РЕСПУБЛИКАСИ


ОЛИЙ ВА ЎРТА МАХСУС ТАЪЛИМ ВАЗИРЛИГИ
НАМАНГАН МУҲАНДИСЛИК – ҚУРИЛИШ ИНСТИТУТИ

“САНОАТНИ АХБОРОТЛАШТИРИШ ФАКУЛЬТЕТИ”

“ИНФОРМАТИКА ВА АХБОРОТ ТЕХНОЛОГИЯЛАРИ” КАФЕДРАСИ

“ ДАСТУРЛАШ ТИЛЛАРИ (С++) ” ФАНИДАН

Мустакил иши 3

Бажарди: 55С-Б-ИАТ-19 гуруҳ
талабаси
Ф. Рахмоналиев


Қабул қилди: М.Тухтасинов
Наманган - 2022 йил


Mavzu: Massivni saralash va unda izlashning samarali algoritmlari
Reja:
1. Ko‘p o‘lchamli massivlar
2. Massivlarni saralash
3. Saralash algoritmlari
4. To‘g‘ridan-to‘g‘ri qo‘shish orqali saralash
5. Xulosa
6. Foydalanilgan adabiyotlar

C++ algoritmik tilida faqat bir o‘lchamli massivlar bilan emas, balki ko‘p

o‘lchamli massivlar bilan ham ishlash mumkin. Agar massiv o‘z navbatida yana
massivdan iborat bo‘lsa, demak ikki o‘lchamli massiv, ya’ni matrisa deyiladi.
Massivlarning o‘lchovi kompyuterda ishlashga to‘sqinlik qilmaydi, chunki ular
xotirada chiziqli ketma-ket elementlar sifatida saqlanadi. Ko‘p o‘lchamli
massivlarni xuddi 1 o‘lchamli massivga o‘xshab e’lon qilinadi, faqat indeks toifasi
sifatida massivning satrlari (qatorlari) va ustunlari toifasi ko‘rsatiladi va ular
alohida [ ][ ] qavslarda ko‘rsatiladi. Masalan: A nomli butun sonlardan iborat 2
o‘lchamli massiv berilgan bo‘lsa va satrlar soni n ta, ustunlar soni m ta b o‘lsa:
int a[n][m]
Ikki o‘lchovli massiv elementlarini kiritish-chiqarish, ular ustida amallar
bajarish ichma-ich joylashgan parametrli sikllar ichida bo‘ladi, ya’ni 1-sikl satrlar
uchun, 2-sikl ustunlar uchun. Masalan:
for ( i=0; i<3; i++)
for ( j=0; j<3; j++)
cin >>a[i][j];
Agar ularni klaviaturadan kiritish kerak bo‘lsa, ya’ni cin operatori yordamida
tashkil etilsa, quyidagicha kiritiladi:
1 2 3
4 5 6
7 8 9
undan tashqari massiv elementlarini e’lon qilish bilan birga ularni inisalizasiya
ham qilish mumkin:
int a[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
Natijalar chiroyli ko‘rinishda bo‘lishi uchun chiqarish operatorini quyidagicha
qilib tashkil etish kerak:
for (int i=0; i<3; i++)
{ for (int j=0; j<3; j++)
cout <<”a[“<cout <getch ( );
}
1-misol. A va B matrisalari berilgan. Quyidagi formula orqali yangi C
matrisasini hosil qiling: Cij = A
ij + B
ij
; bu yerda i=1,3; j=1,2;

Massiv ementlariga son qiymat berishda kompyuter xotirasidagi tasodifiy
butun sonlardan foydalanish ham mumkin. Buning uchun standart kutubxonaning
rand ( ) funksiyasini ishga tushirish kerak. rand ( ) funksiyasi yordamida 0 ÷ 32767
oraliqdagi ixtiyoriy sonlarni olish mumkin. Bu qiymatlar umuman tasodifiydir.
(psevdo – tasodifiy degani).
Agar dastur qayta-qayta ishlatilsa, ayni tasodifiy qiymatlar takrorlanaveradi.
Ularni yangi tasodifiy qiymatlar qilish uchun srand ( ) funksiyasini dasturda bir
marta e’lon qilish kerak. Dastur ishlashi jarayonida ehtiyojga qarab rand ( )
funksiyasi chaqirilaveradi. Tasodifiy qiymatlar bilan ishlash uchun
faylini e’lon qilish zarur. srand ( ) funksiyasidagi qiymatni avtomatik ravishda
o‘zgaradigan holatga keltirish uchun srand ( time (NULL)) yozish ma’qul, shunda
kompyuter ichidagi soatning qiymati time ( ) funksiyasi yordamida o‘rnatiladi va
Boshlanish
Kiritish
А, В
i = 1, 3
J = 1, 2
Cij
= aij
+ bij
Cij
Tamom
srand ga parametr sifatida beriladi. NULL yoki 0 deb yozilsa, qiymat sekundlar
ko‘rinishida beriladi. Vaqt bilan ishlash uchun ni e’lon qilish kerak.
#include
#include
#include
#include
int main ( )
{ srand ( time (0));
int a[5], b[5], i;
for (i = 0; i < 5; i++) a[i] = rand ( );
for (i = 0; i < 5; i++)
{ b[i] = a[i] + 64;
cout << “b=”<getch ( ); }
Izoh: tasodifiy sonlar ichida manfiy sonlarning ham qatnashishini ihtiyor
etsak, a[i] = 1050 - rand ( ); yoki a[i] = rand ( )-1000; deb yozish ham mumkin.
2-misol. A matrisani B vektorga ko‘paytirish algoritmi.

3-misol. 2 ta matrisa berilgan. Ularni o‘zaro ko‘paytirib yangi matrisa hosil
qiling. Bu yerda 1-matrisaning ustunlar soni 2-matrisaning satrlar soniga teng
bo‘lishi kerak.


5-misol. 3 ta qator va 4 ta ustunga ega A matrisa berilgan. Undagi eng kichik
elementni va uning indeksini topish, hamda o‘sha qatorni massiv shaklida
chiqarish dasturini tuzing.
#include
#include
int main ( )
{
int a[3][4] = {{1,2,3,4},{4,5,6,7},{7,8,9,10}}, i, j, k, h, min;
int b[4];
min = a[0][0];
for (i=0; i<3; i++)
for (j=0; j<4; j++)
{ if ( a[i][j] > min) { min = a[i][j]; k = i; h = j; } }
cout << “min=”<for ( j=0; j<4; j++)
{ b[j] = a[k][j];
cout <<”b=”<getch ( );
}
6-misol. Saralash masalasi. Massiv elementlarini o‘sib borish tartibida
saralash dasturini tuzing. (pufaksimon saralash)
Avval bir o‘lchovli massiv elementlarini saralashni ko‘rib o‘tamiz.
#include
#include
#include
#include
int main ( )
{
srand (time (0));
float a[10] , b; int i, j;
for (i = 0; i<10; i ++)
a[i] = rand( ) /33.;
for( j = 0; j<10; j++)
for ( i = 0; i < 10; i ++)
{
if (a[i] < a[i+1])
{ b = a[i];
a[i] = a[i+1];
a[i+1] = b; }
}
cout. precision (3);
for (i = 0; i < 10; i++)
cout << a[i]<getch ( );
}
Endi ikki o‘lchamli massiv elementlarini saralashni ko‘ramiz:
#include
#include
int main ( )
{ float a[3][3] = {{.....},{.....},{.....}}, b;
int i, j, k;
for ( k=0; k<3; k++)
for ( i=0; i<3; i++)
for ( j=0; j<2; j++)
{ if (a[i][j] > a[i][j+1] )
{ b = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = b; } }
for ( i=0; i<3; i++)
{ for ( j=0; j<3; j++)
cout <<”a=”<getch ( );
}
Yuqoridagi dastur saralashni qator bo‘yicha olib borish uchun mo‘ljallangan.
Agar saralashni ustun bo‘yicha amalga oshirish kerak bo‘lsa, quyidagicha yozish
kerak bo‘ladi:
for ( i=0; i< 2; i++)
for ( j=0; j<3; j++)
{ if ( a[i,j] > a[i+1, j] ) { b:= a[i, j]; a[i, j]:= a[i+1, j]; a[i+1, j]:= b; }
Agar saralashni o‘sib borish tartibida amalga oshirish kerak bo‘lsa, if
operatoridagi solishtirish belgisi > bo‘lishi kerak, agar kamayish tartibida kerak
bo‘lsa, solishtirish belgisi < ko‘rinishida bo‘lishi kerak.
Saralash algoritmlari
Umuman olganda saralashning maqsadi berilgan Ob’yektlar to‘plamini aniq
bir tartibda guruhlab chiqish jarayoni ta’riflanadi. Saralashning maqsadi
keyinchalik, saralangan to‘plamning qidirilayotgan elementini topishdan iborat. Bu
qariyb universal, fundamental jarayon. Biz bu jarayon bilan har kuni uchrashamiz
– telefon daftaridagi saralash, kitoblar sarlavhasida, kutubxonalarda, lu g‘atlarda,
pochtada va hokazo .
Xatto yosh bolalar ham o‘z narsalarini tartiblashga o‘rganadi.
Saralashning juda ko‘p usullari mavjud. Ular turli to‘plamlar uchun turlicha
bo‘lishi mumkin. Massivlarni saralash. Massivni saralash uchun ishlatiladigan usul unga
berilgan xotirani ixcham holda ishlatishdir. Boshqacha qilib aytganda,
saralanayotgan massiv xuddi shu massivni o‘zida amalga oshirilishi lozim.
Saralanayotgan a massiv elementlarini kiritib, uni boshqa bir d massivda
saralangan holda saqlanishi bizda hech qanday qiziqish uyg‘otmaydi.
Saralash usullari kam mashina vaqtini talab qilishi lozim. Eng yaxshi tez
algoritmlar n*log n tartibidagi saralashlarni talab etadi.
Biz saralash bo‘yicha bir nechta sodda va ma’lum usullarni ko‘rib chiqamiz.
Ular to‘g‘ri usullar deb aytiladi.
Saralash usullari to‘g‘risida quyidagi fikrlarni bildirish mumkin:
1. To‘g‘ri usullar ko‘plab saralashning asosiy tamoyillarining xarakterini
ochib berishi uchun qulay.
2. Bu usullarni dasturlar oson tushunadi va ular qisqa. Eslatib o‘tamiz,
dasturning o‘zi ham xotira egallaydi.
3. Murakkab usullar ko‘p sondagi amallarni talab qiladi, lekin bu
amallarning o‘zlari yetarlicha murakkab bo‘lganlari uchun, kichik n larda tez va
katta n larda sekin ishlaydi. Ammo ularni katta n larda ishlab bo‘lmaydi.
Bitta massivni o‘zida saralashni ularni mos aniqlangan tamoyillari bilan uch
kategoriyaga ajratish mumkin:
1. Qo‘shish orqali saralash (by insertion);
2. Ayirish orqali saralash (by selection);
3. Almashish orqali saralash (by exchange).



Xulosa
Ushbu bobda Siz sinflarni tashkil etish, ob’ektlardan foydalanish xaqidagi
tushunchaga ega bo‘ldingiz. Sinf turli toifali o‘zgaruvchilardan, shu jumladan
boshqa sinfdan tashkil topgan berilganlar-a’zolarga ega. Bundan tashqari sinf
tarkibiga usullar deb ataluvchi funksiy-a’zolar ham kiradi. Ularning har biri
himoyalsh usulini beruvchi maxsus spetsifikatorga ega bo‘ladi. Agar o‘zgaruvchia’zolar public sifatida tavsiflangan bo‘lsa, ushbu o‘zgaruvchi tarkibiga kirgan sinf
ob’ektlarini ishlatmasdan turib, faqat nomi orqali unga murojaat qilish mumkin.
Statik o‘zgaruvchi a’zolarni ob’ektlar hisobchisi sifatida qo‘llash mumkin.

FOYDALANILGAN ADABIYOTLAR RO‘YXATI
1. Karimov I.A. Xavfsizlik va barqarorlik yo‘lida. 6-jild. Toshkent
“O‘zbekiston”. 1998. 409 b.
2. Horstman C.S. C++ for Everyone, 2 edition-2011, 562 p
3. Herb Sutter. More Exceptional C++. 2007- 304 p.
4. Nazirov Sh.A., Qobulov R.V., Bobojanov M.R., Raxmanov Q.S. С va
С++ tili. “Voris-nashriyot” MCHJ, Toshkent 2013, 488 b
5. Aripov М., Begalov В., Begimqulov U., Mamarajabov М. Axborot
texnologiyalari. Toshkent: Noshir, 2009. -368 s.