Reja: 1 Binar qidiruv

Algoritm samaradorlig: 
O(n log n) – eng samarali usul. 
SHell saralashi (qisqarib boruvchi qadamlar orqali saralash) 
To‟g‟ri qo‟shish usulini 1959 yilda D. SHell tomonidan mukammallashtirish taklif qilingan. 
Quyidagi chizmada ushbu usul tasvirlangan: 

---

Boshida bir biridan 4 qadamda joylashgan elementlar o‟zaro guruhlanib saralash amalga 
oshiriladi. Bunday jarayon to‟rtlik saralash deb ataladi. Birinchi o‟tishdan keyin elementlar qayta 
guruhlanib, endi har ikki qadamdagi elementlar taqqoslanadi. Bu esa ikkilik saralash deb nomlanadi. Va 
nihoyat, uchinchi o‟tishda oddiy yoki yakkalik saralashi amalga oshiriladi.
Bir qarashda mazkur usul bilan saralash amalga oshirilganda saralash jarayoni kamayish o‟rniga 
ortib boradigandek tuyulsada, elementlarni o‟rin almashtirishlar nisbatan kam amalga oshiriladi.
Ko‟rinib turibdiki, bu usul natijasida tartiblangan massiv hosil bo‟lib, har bir o‟tishdan keyin 
saralashlar kamayib boradi. Eng yomon holatda oxirgi ishni yakkalik saralash amalga oshiradi.
Barьer usulidan foydalanilganda har bir saralash o‟zining barьeriga ega bo‟lishi lozim hamda 
dastur uning joyini aniqlashi uchun uni iloji boricha osonlashtirish lozim. SHuning uchun massivni [-
h1..N] gacha kengaytirish lozim bo‟ladi. 
h[1..t] – qadamlar o‟lchami massivi 
a[1..n] - saralanayotgan massiv 
k – saralash qadami 
x – qo‟shilayotgan element qiymati 
Subroutine ShellSort 
const t = 3; 
h(1) = 5; 
h(2) = 3; 
h(3) = 1; 
var 
h: array [1..t] of integer; 
a: array [1..n] of integer; 
k, x, m, t, i, j: integer; 
begin 
for m = 1 to t do 
begin 
k:= h(m); 
for i = k + 1 to n do 
begin 
x:= a(i);
for j = i-k downto k do 
begin 
if x < a(j ) then 
a(j+k):= a(j); 
else
goto 1; 
end ; 
end; 
end; 
1: a(j+1) = x ; 
end;
end . 
Umuman olganda, qanday qadamlar tanlanganda eng yaxshi natija olinishi isbotlanmagan 
bo‟lsada, lekin bu qadamlar biri ikkinchisini ko‟paytuvchilari bo‟lmasligi lozimligi aniqlangan. 

---

D. Knut qadamlarni quyidagicha ketma-ketligini taklif qilgan (teskari tartibda): 1,3,7,15,31,…,ya‟ni: 
h
m-1
=2h
m
+1, h
t
=1, t = [log
2
n] - 1. Agar qadamlar ushbu ko‟rinishda, algoritm samaradorligi tartibi
O(n
1.2
). 
Algoritm so`zi barchamizga ma`lum bo`lganidek, vatandoshimiz Muhammad ibn Muso al-
Xorazmiyning ismini yevropacha talaffuzidan kelib chiqqan. Demak, hozirda keng foydalanilayotgan 
algoritmlashning asosi bizning Vatanimizdan boshlangan. 
Maktab informatika kursidan ma`lumki, algoritm bu – ma`lum masalani hal qilish uchun bajarish kerak 
bo`lgan amallar ketma-ketligi. O`sha mashhur choy damlash algoritmidan chekingan holda hayotiy 
misol keltiramiz. Hayotda eng ko`p bo`ladigan holatimiz bu uyqu. Ko`pchilik rejim bilan uxlaydi, ya`ni 
uxlashga ma`lum bir vaqtni belgilagan. Misol uchun siz uxlashga yotish uchun 22:00ni tanladingiz. Har 
safar soatga qaraganingizda uxlash vaqti bo`lgan yoki bo`lmaganini tekshirasiz. Miyangizda esa 
quyidagi jarayon bo`ladi: 
Bu oddiy uyquga yotish algoritmi edi. Hayotda o`zimiz bilmagan holatda algoritmlardan foydalanamiz. 
Miyamiz juda tez ishlagani sabab qadamlar ketma-ketligi haqida o`ylab ko`rmaymiz. 
Endi maqolamizning asosiy qismi, dasturlashda algoritmlashga o`tamiz. Dasturlashda algoritm bu – 
masalani yechish uchun bajarilishi kerak bo`lgan amallar ketma-ketligini kodga o`girilgan varianti. 
Bunda masalani yechish uchun miyamizda kechayotgan jarayonni kompyuter tushunadigan qilib yozish 
talab etiladi. 
Algoritmlashning asosi matematika hisoblanadi. Bunda fikrlash muhim rol o`ynaydi. So`zimni 
quyidagicha isbot qilaman. Dasturlash sanoatida gigant korporatsiya hisoblangan Microsoftning 
asoschisi Bill Geytsning shunday so`zlari dasturchilar orasidda mashhur:"Qo`shish va ayirishni 

---

biladigan har qanday inson dasturchi bo`la oladi". Bu so`zlarni mag`zini chaqish uchun sizlarni 
boshlang`ich sinflarga qaytishga taklif etaman. Har birimiz boshlang`ich sinflarda qo`shish va ayirish 
amallarini o`rgangan edik. Ko`pchilik buni barmoqlari orqali bajargan. Chunki barmoqlar 10ta va 
raqamlarni qo`shish va ayirishda qo`l keladi. Keyinchalik matematik evolutsiyamiz sonlar bilan qo`shish 
va ayirish amallarini bajarish bosqichiga yetib keladi. Bu rivojlanish jarayoni yangi amallar bilan boyidi 
va endi bir xil raqamlarni bir necha marta qo`shishni osonlashtirish uchun ko`paytirish jadvalini 
o`rgandik. E`tibor bering, ko`paytirish algoritmi qo`shish algoritmining asosiga qurilgan. 
Rivojlanishimiz davom etib, endilikda qoldiqli bo`lish va shu kabi murakkabroq amallarga o`tamiz. 
Maktabni bitirish vaqtida esa juda murakkab amallarni ham bajara oladigan darajada bo`lamiz. Ana 
ko`rdingizmi, hamma murakkab amallarning asosi qo`shish va ayirishdan boshlanadi. U yog`i esa 
fikrlash doirangiz kengligiga bog`liq. Demak, dasturlashdagi asosiy masalalar matematik fikrlashga 
bog`liq. 
Algoritmlashning asosiy shartlaridan biri bu – dasturning ishlash tezligi. Kod qanchalik optimal bo`lsa, 
dastur shuncha tez ishlaydi. Dastur tezligini pasaytiruvchi omillar bu – loop , ya`ni takrorlanishlar. Sikl 
ichida sikl ochish yoki sikl ichida shart tekshirish dastur tezligini ma`lum darajada pasaytiradi. Hayotiy 
misol keltiraman: 7ta 45ni bir biriga qo`shing. Har birini alohida qo`shib chiqish uchun vaqt talab 
etiladi. Ya`ni 7 marta bir xil amalni bajarish kerak. Xuddi shuni ko`paytirish amali orqali kamroq vaqt 
sarflab amalga oshirish mumkin. Har birimiz arifmetik progressiya haqida tushunchaga egamiz. Hadlari 
bir biridan ma`lum d songa farq qiladigan sonli ketma-ketlik. Shuni nta hadi yig`indisini topish uchun n 
marta har safar yangi hadni topish va uni oldingi sonlar yig`indisiga qo`shish talab etiladi. Bu esa juda 
ko`p vaqt talab qiladi. Aynan shu muammo matematikada oddiy formula orqali hal etilgan. Bu 
muammoni hal etish formulasi esa albatta tafakkur mahsuli hisoblanadi. Siz ham yuqori darajali 
masalalarni yechishda ana shunday ixtirolar qilasiz yoki boshqa ixtirolardan foydalanasiz. 
Dasturlashda algoritmlashning asosan 4 turi mavjud: 
1.
Saralash 
2.
Qidirish 
3.
Grafiklar 
4.
Stringlar 
Ularning har biriga keyingi maqolalarimizda alohida to`xtalib o`tishga harakat qilamiz. Hozir esa oddiy 
algoritmlaning kodga o`girilish jarayonini ko`rib chiqamiz. Biz bu misollarni O`zbekistonda anchagina 
mashhur bo`lgan Java dasturlash tili negizida ko`rib chiqamiz. 
Misol: a sonini qiymatini b soniga, b sonini qiymatini a soniga o`zlashtirish dasturini tuzing. 
Misol uchun a = 2 , b = 7; 
Dastur Java dasturlash tilida quyidagicha bo`ladi: 
package dasturchi_uz;
public class Almashtirish1 {
public static void main(String[] args) { 
int a = 2;
int b = 7;//Sonlar kiritildi
int temp; // oraliq o`zgaruvchi
temp = a; // a ning qiymatini vaqtincha saqlab turish
a = b; // b ning qiymatini a ga o`zlashtirish
b = temp; // b ga a ning saqlangan qiymatini o`zlashtirish
System.out.println("a = " + a);
System.out.println("b = " + b); 
}
} 
Aynan shu misolni yechishda xotiradan ortiqcha joy olmaslik talab etilishi mumkin, ya`ni o`rtadagi 
o`zgaruvchi "temp" ishlatilmasligi talab etiladi. Buni quyidagicha amalga oshirsa bo`ladi: 
package dasturchi_uz; 
public class Almashtirish2 { 
public static void main(String[] args) { 
int a = 2; 
int b = 7;// sonlar kiritildi 

---

a = a + b;// a ning qiymatini yig`indiga tengladik a = 2 + 7 = 9 
b = a - b;// b ga a ning eski qiymatini o`zlashtiramiz b=9 – 7 = 2 
a = a - b;// a ga b ning eski qiymatini o`zlashtiramiz a=9 – 2 = 7 
System.out.println("a = " + a); 
System.out.println("b = " + b); 
} 
} 
Yuqoridagi misolda biz dasturda yangi qiymat o`zlashtirish orqali eskisini unutish usulidan foydalandik. 
Misol: Bo`lish amalidan foydalanmasdan faqat qo`shish va ayirish amallari orqali bo`linmani hisoblang: 
676 : 26; 
Java dasturlash tilidagi dasturi quyidagicha bo`ladi: 
package dasturchi_uz; 
public class Bolinma { 
public static void main(String[] args) { 
int bolinuvchi = 676;// bo`linuvchi kiritiladi 
int boluvchi = 26; // bo`luvchi kiritiladi 
int bolinma = 0; // bo`linmaning boshlang`ich qiymati 0 bo`ladi 
do { 
bolinuvchi-=boluvchi; // har safar bo`linuvchidan bo`luvchi ayiriladi 
bolinma ++; //har bir marta ayirish amalga oshirilganda bo`linma qiymati bittaga oshib boradi bu esa 
bolinuvchi bo`luvchini ichida necha marta joylashganini aniqlashga yordam beradi. 
}while (bolinuvchi >= boluvchi); // bu takrorlanish bo`linuvchi 0ga teng bolguncha davom etadi. 
System.out.println(bolinma);// natija ekranga chiqariladi. 
} 
} 
Bir o'lchovli massivda saralash 

---

Salom men bu maqolamda sizlarga bir o'lchovli massivda saralash qanday amalga oshirish 
mumkinligini ko'rsatib bermoqchiman. Undan oldin massiv o'zi nima? degan savolga javob topaylik. 
Massiv bu bir tip ostida raqamlangan ma'lumotlar jamlanmasidir. 
Massivni e'lon qilish 
#include 
using namespace std; 
int main(){ 
long a[100], double b[100]; 
return 0; 
} 
Biz bu yerda butun tipli a va haqiqiy tipli b massivlarni e'lon qildik va ular saqlay oladigan elementlar 
sonini 100 deb belgiladik . Bu massivlarimiz har biri 101 element bilan ishlay oladi chunki c++ 
dasturlash tlida indeks 0 dan boshlanadi. Massivlarni bunday e'lon qilish xotiradan yutqazishga olib 
keladi, ya'ni foydalanuvchi 101 elementni ishlatmasa ham dastur xotiradan massiv uchun 101 joy ajratib 
turadi. Biz bu muammoni hal qilishimiz uchun foydalanuvchiga kerakli bo'lgan massiv o'lchovini 
kiritishini so'raymiz. 
#include 
using namespace std; 
int main(){ 
long n; 
cin >> n; 
long a[n], double b[n]; 
return 0; 
} 
Foydalanuvchi n o'zgaruvchisiga qiymat bergandan so'ng uning qiymati biz e'lon qilayotgan massiv 
uzunligini belgilab beradi. 
Massiv elementlariga qiymat berish. 
#include 
using namespace std; 
int main(){ 
long n, i; 
cin >> n; 
long a[n]; 
for (i = 1; i <= n; i++) 
cin >> a[i] 
return 0; 
} 
Maqolam boshida massiv indekslari 0 dan boshlanadi degan edim lekin bu yerda massivning birinchi 
indeksli elementidan boshlab qiymat berib boshladim chunki massivning 0 indeksli elementi bizga 
saralash uchun kerak bo'ladi 
Massiv elementlarini chop etish. 
#include 
using namespace std; 
int main(){ 
long n, i; 
cin >> n; 
long a[n]; 
for (i = 1; i <= n; i++) 
cin >> a[i]; 
for (i = 1; i <= n; i++) 
cout << a[i] << " "; 
return 0; 
} 
Massiv elementlarini kiritish va chop etishni o'rganib oldik endi ularni saralashni o'rganamiz. 
#include 
using namespace std; 

---

int main(){ 
long n, i, j; 
cin >> n; 
long a[n]; 
for (i = 1; i <= n; i++) 
cin >> a[i]; 
for (i = 1; i < n; i++) 
for (j = i + 1; j <= n; j++) 
{ 
if (a[i] < a[j]) 
{ 
a[0] = a[i]; 
a[i] = a[j]; 
a[j] = a[0]; 
} 
} 
for (i = 1; i <= n; i++) 
cout << a[i] << " "; 
return 0; 
}
Bu dasturimizda foydalanuvchi tomonidan kiritilgan massiv elementlari kamayish tartibida saralab 
beradi. Sizga aytgan 0 indeksli massiv elementimizni bo'sh idish sifatida ishlatib massivni 
saraladik.Massivni o'sish tartibida saralamoqchi bo'lsangiz chop etishdagi for ning paramertlarini 
o'zgartirishingiz kifoya ya'ni 
for(i=n;i>=1;i--) sizning massiv elementlaringiz o'sish tartibida chop etiladi.