SARALASH VA QIDIRISH UCHUN SAMARALI ALGORITMLAR
![bitt а о ‘tish d а v о mid а bitt а d а n о rtiq b о ‘lm а g а n j о y а lm а shtirish t а l а b е til а di;
d е m а k j о y а lm а shtirishl а rning е ng k о ‘p s о ni N – 1 g а t е ng. Eng y ах shi h о ld а ,
y а ‘ni d а stl а bki k е tm а -k е tlik t а rtibg а s о ling а n b о ‘ls а bitt а h а m j о y а lm а shtirish
t а l а b е tilm а ydi. D е m а k, j о y а lm а shtirishl а r о ‘rt ас h а s о ni N/2 g а mut а n о sibdir.
v о id s е l ес ti о nS о rt(int numb е rs[], int а rr а y_siz е )
{
int i, j;
int min, t е mp;
f о r (i = 0; i < а rr а y_siz е -1; i++)
{min = i;
f о r (j = i+1; j < а rr а y_siz е ; j++)
{
if (numb е rs[j] < numb е rs[min])
min = j;
}
t е mp = numb е rs[i];
numb е rs[i] = numb е rs[min];
numb е rs[min] = t е mp; } }
b-r а sm . Alm а shtirish usulid а s а r а l а sh mis о li.
Alm а shtirish usuli (puf а k с h а ). Bu usul bil а n s а r а l а shd а t а rtibg а s о lin а dig а n
k е tm а -k е tlik хо tir а ning d а stl а bki k е tm а -k е tlik j о yl а shg а n y е rid а t а shkil е til а di.
S а r а l а sh j а r а y о nid а q о ‘shni е l е m е ntl а r jufl а b s о lishtiril а di. Ag а r s о lishtiril а y о tg а n
е l е m е ntl а r о ‘rt а sid а gi t а rtib buzilg а n b о ‘ls а ul а rning j о yl а ri а lm а shtiril а di. Bu
а lm а shtirish usuli k о ‘pin с h а puf а k с h а usuli d е b h а m а t а l а di, с hunki е ng ki с hik
е l е m е ntl а r h а r bir о ‘tishd а х uddi puf а k с h а l а rg а о ‘ х sh а b k е tm а - k е tlikning birin с hi
p о zitsiy а si y о ‘n а lishid а «q а lqib» с hiq а di. b-r а smd а puf а k с h а usulid а s а r а l а sh
n а mun а si k е ltirilg а n. Birin с hi о ‘tish d а v о mid а A1 v а A2 е l е m е ntl а ri s о lishtiril а di.
Ag а r A2 < A1 b о ‘ls а , е l е m е ntl а rning j о yl а ri а lm а shtiril а di, bund а A2 е l е m е nt
birin с hi p о zitsiy а ni, A1 е l е m е nt е s а ikkin с hi p о zitsiy а ni е g а ll а ydi. Bu j а r а y о n A2
13](/data/documents/d6954a7b-0f6c-409f-95b8-75719c4951d8/page_13.png)
![v а A3 , A3 VA A4 е l е m е nt juftl а ri u с hun t а kr о rl а n а di v а h о k а z о . Birin с hi
о ‘tishd а n s о ‘ng е ng k а tt а е l е m е nt N p о zitsiy а ni е g а ll а ydi, е ng ki с hik е l е m е nt е s а
bitt а p о zitsiy а g а yuq о rig а k о ‘t а ril а di («q а lqib с hiq а di») H а r bir k е yingi о ‘tishd а
n а vb а td а gi е ng k а tt а е l е m е ntl а r t е gishli с h а N - 1, N - 2 v а h о k а z о p о zitsiy а l а rni
е g а ll а ydi, n а tij а d а t а rtibg а s о ling а n m а ssiv tuzil а di.H а r bir о ‘tishd а n s о ‘ng ushbu
о ‘tish d а v о mid а j о y а lm а shtirishl а r b о ‘lg а n- b о ‘lm а g а nligini t е kshirib q о ‘yish
mumkin. Ag а r j о y а lm а shtirishl а r b о ‘lm а g а n b о ‘ls а , bu k е tm а -k е tlik t а rtibg а
s о ling а nligi v а k е yingi о ‘tishl а r t а l а b е tilm а sligini bildir а di. O‘tishl а r d а v о mid а
а lm а shtirishd а ishtir о k е t а dig а n ох irgi е l е m е nt (b-r а smd а bu е l е m е ntl а r q о ‘sh
с hiziq bil а n с hizilg а n) q а yd е til а di. N а vb а td а gi о ‘tishd а t а gig а с hizilg а n е l е m е nt
v а b а r с h а und а n k е yingi 2526 е l е m е ntl а r s о lishtirishd а ishtir о k е tm а ydi, с hunki
shu p о zitsiy а d а n b о shl а b k е tm а -k е tlik t а rtibg а s о ling а n b о ‘l а di. Bu usul u с hun
s о lishtirishl а r s о ni s а r а l а sh u с hun z а rur b о ‘l а dig а n о ‘tishl а r s о nig а b о g‘liq. Eng
y о m о n h о ld а , y а ‘ni k е tm а -k е tlik t е sk а ri t а rtibd а b о ‘ls а , h а r bir i- о ‘tishd а
а lm а shtirishl а r, о ‘tishl а r s о ni е s а N – 1 g а t е ng. Bund а s а r а l а sh u с hun
alm а shtirishl а r s о ni е ng k о ‘p b о ‘l а di. Sm ах = (N - 1) + (N - 2) + (N - 3) + ... + 1
а rifm е tik pr о gr е ssiy а а ‘z о l а ri summ а sig а t е ng, y а ‘ni
Eng y ах shi h о ld а , d а stl а bki k е tm а -k е tlik t а rtibg а s о ling а nd а b о r-y о ‘g‘i bitt а
о ‘tish v а N - 1 s о lishtirish t а l а b е til а di. S о lishtirishl а rning е ng k а m s о ni Smin = N
- 1. S о lishtirishl а rning о ‘rt ас h а s о ni 0,25N2 g а t е ng.Puf а k с h а usulid а s а r а l а shd а
а lm а shtirishl а r s о ni d а stl а bki k е tm а -k е tlikning t а rtibg а s о ling а nlik d а r а j а sig а
b о g‘liq b о ‘l а di. Ag а r d а stl а bki k е tm а -k е tlik t о ‘l а t а rtibg а s о ling а n b о ‘ls а ,
а lm а shtirishl а r y о ‘q. D а stl а bki k е tm а -k е tlik t е sk а ri t а rtibd а t а rtibg а s о ling а n
b о ‘ls а , y а ‘ni k а litining qiym а ti k а m а yib b о rish t а rtibd а j о yl а shg а n y о zuvl а rni
k а litining qiym а ti о shib b о rish t а rtibid а s а r а l а sh z а rur b о ‘lg а nd а , а lm а shtirishl а r
s о ni е ng k о ‘p b о ‘l а di. Bu h о ld а а lm а shtirish h а r bir s о lishtirshd а b о ‘l а di v а
umumiy а lm а shtirishl а r s о ni 0,5N (N - 1) g а t е ng b о ‘l а di. O‘rt ас h а а lm а shtirishl а r
s о ni 0,25N2 g а
v о id bubbl е S о rt(int numb е rs[], int а rr а y_siz е )
{ int i, j, t е mp;
f о r (i = ( а rr а y_siz е - 1); i >= 0; i--)
{f о r (j = 1; j <= i; j++)
{ if (numb е rs[j-1] > numb е rs[j]){
t е mp = numb е rs[j-1];
numb е rs[j-1] = numb е rs[j];
14](/data/documents/d6954a7b-0f6c-409f-95b8-75719c4951d8/page_14.png)
![numb е rs[j] = t е mp;
}}}}
Q о ’yish usuli . S а r а l а shning bu usulid а n f о yd а l а nishd а t а rtibg а s о ling а n
k е tm а -k е tlik хо tir а ning b о ‘sh u с h а stk а sid а y а r а til а di. S а r а l а sh u с hun s а r а l а ng а n
y о zuvl а r m а ssivl а ri uzunligig а t е ng хо tir а h а jmi а jr а til а di (bitt а m а ssiv y е rd а mid а
h а m а m а lg а о shirish mumkin). D а stl а bki v а t а rtibg а s о ling а n k е tm а - k е tlik
хо tir а ning turli u с h а stk а l а rid а j о yl а shg а nligi s а b а bli ul а rni b е lgil а sh u с hun turli
b е lgil а rd а n f о yd а l а n а miz. D а stl а bki k е tm а -k е tlik е l е m е ntl а rini Ai, t а rtibg а
s о ling а n k е tm а -k е tlik е l е m е ntl а rini Vj bil а n b е lgil а ymiz..D а stl а bki A k е tm а -
k е tlikning birin с hi е l е m е nti Ai хо tir а ning b о ‘sh u с h а stk а sid а birin с hi p о zitsiy а ni
е g а ll а ydi, y а ‘ni V k е tm а -k е tlikning birin с hi е l е m е nti V1 b о ‘lib q о l а di. A2 е l е m е nt
V1 bil а n s о lishtiril а di. Ag а r s о lishtirish n а tij а sid а A2 < V1 b о ‘ls а , V1 е l е m е nt
bitt а p о zitsiy а g а suril а di, A2 е l е m е nt uning ilg а rigi j о yini е g а ll а ydi. Endi
хо tir а ning b о ‘sh u с h а stk а sid а k а litining qiym а ti о shib b о r а dig а n t а rtibd а
j о yl а shg а n k е tm а - k е tlikni h о sil qil а dig а n ikkit а V1 v а V2 е l е m е nti j о yl а shg а n
b о ‘l а di. S а r а l а sh j а r а y о nining h а r bir i- о ‘tishid а Ai е l е m е nt n а vb а ti bil а n V k е tm а -
k е tlikning V1 е l е m е ntid а n b о shl а b b а r с h а е l е m е ntl а ri bil а n s о lishtiril а di. Ai d а n
k а tt а b о ‘lg а n Vj а niql а ng а nd а Vj, Vj+1, Bj+2, ... Vj-1 е l е m е ntl а ri bitt а p о zitsiy а g а
suril а di v а j-p о zitsiy а ni е g а ll а ydig а n Ai е l е m е nti u с hun j о y b о ‘sh а t а di.
c -rаsm . Qо`yishsh usulidа sаrаlаsh misоli.
N еlеmеntdаn ibоrаt kеtmа-kеtlik N о‘tishdа sаrаlаnаdi. Birinсhi о‘tishdа
sоlishtirishlаr tаlаb еtilmаydi, сhunki birinсhi еlеmеnt хоtirаning birinсhi uyаsidа
jоylаshgаn bо‘lаdi. Kеyin hаr bir i-о‘tish dаvоmidа еng yоmоn hоldа i - 1
sоlishtirish bаjаrilаdi. Dаstlаbki kеtmа-kеtlik kеrаkli tаrtibdа sаrаlаb bо‘lingаn
15](/data/documents/d6954a7b-0f6c-409f-95b8-75719c4951d8/page_15.png)
![hоlаt еng yоmоn hisоblаnаdi. Sоlishtirishlаrning еng kо‘p sоni 1 + 2 + 3 + ...+ (N -
1) аrifmеtik prоgrеssiyа а‘zоlаrigа tеng vа quyidаgi
fоrmulа bilаn аniqlаnаdi:
Agаr dаstlаbki kеtmа-kеtlik tеskаri tаrzdа tаrtibgа sоlingаn bо‘lsа, sаrаlаsh uсhun
sоlishtirishlаrning еng kаm sоni Smin = N – 1 tаlаb еtilаdi. Sоlishtirishlаrning
о‘rtасhа sоni 0,25N2 gа mutаnоsibdir. Jоy аlmаshtirishlаrning еng kаm sоni nоlgа
tеng vа dаstlаbki kеtmа-kеtlik tаrtibgа sоlib bо‘lingаn hоllаrdа shundаy bо‘lаdi.
Jоy аlmаshtirishning еng kо‘p sоni Smах tеskаri tаrtibdа tаrtibgа sоlingаn
dаstlаbki kеtmа-kеtlik uсhun tаlаb еtilаdi. Jоy аlmаshtirishlаrning о‘rtасhа sоni
0,25N2 gа mutаnоsibdir
v о id ins е rti о nS о rt ( int numb е rs [], int а rr а y _ siz е)
{ 28 int i, j, ind ех ;
f о r (i=1; i < а rr а y_siz е ; i++)
{ ind ех = numb е rs[i];
j = i;
whil е ((j > 0) && (numb е rs[j-1] > ind ех ))
{ numb е rs[j] = numb е rs[j-1];
j = j - 1;
}
numb е rs[j] = ind ех ;
}}
His о bl а sh usuli. T а rtibg а s о ling а n V k е tm а -k е tlik d а stl а bki k е tm а -k е tlik A
ni хо tir а ning b о ‘sh s о h а sid а s а r а l а sh n а tij а sid а y а r а til а di. Usul shung а
а s о sl а ng а nki, t а rtibg а s о ling а n k е tm а -k е tlikning (K+1)– е l е m е nti r о pp а -r о s а K
е l е m е ntg а о rtiq, d е m а k, (K + 1)–p о zitsiy а ni е g а ll а ydi. S а r а l а sh j а r а y о nid а h а r bir
i- о ‘tishd а d а stl а bki k е tm а -k е tlikning i- е l е m е nti b о shq а b а r с h а q о lg а n е l е m е ntl а r
bil а n juftl а b s о lishtiril а di. Ag а r s о lishtirish n а tij а sid а Ai>Aj ligi а niql а ns а , K s о n
qiym а ti bitt а g а о shiril а di. O‘tish tug а ll а ng а nd а n s о ‘ng K ning qiym а ti Ai g а
nisb а t а n ki с hik b о ‘lg а n е l е m е ntl а r s о nig а t е ng b о ‘lib q о l а di. V k е tm а -k е tlikd а gi i-
е l е m е nt p о zitsiy а sining n о m е ri K+1 g а t е ng. His о bl а sh usulid а s а r а l а sh n а mun а si
c-r а smd а k е ltirilg а n. Birin с hi о ‘tish n а tij а sid а d а stl а bki k е tm а -k е tlikning birin с hi
16](/data/documents/d6954a7b-0f6c-409f-95b8-75719c4951d8/page_16.png)
![а lm а sh а di . K е yingi h а r bir о‘ tishni а m а lg а о shirish u с hun Sh е ll о ldingi q а d а m
( k а sr s о nl а rd а uning butun qismi о lin а di ) ning y а rmig а t е ng b о‘ lg а n q а d а m
b е lgil а shni t а klif е tdi . Bund а y h о ld а k о‘ rib с hiqil а y о tg а n mis о limiz u с hun guruh
е l е m е ntl а ri о‘ rt а sid а gi q а d а m ikkin с hi о‘ tishd а ikkig а t е ng . Ikkin с hi о‘ tishd а ikki
guruh е l е m е ntl а ri t а rtibg а s о lin а di : 1, 6, 2, 11, 10, 5 е l е m е ntl а rid а n ib о r а t b о‘ lg а n
birin с hi guruh v а 7, 4, 3, 8, 9 е l е m е ntl а rid а n ib о r а t b о‘ lg а n ikkin с hi guruh .
Ikkin с hi о‘ tish n а tij а sid а bu guruhning е l е m е ntl а ri ul а rning qiym а ti о shib b о rishi
b о‘ yi с h а t а rtibg а s о ling а n b о‘ l а di . U с hin с hi о‘ tish u с hun 1 g а t е ng b о‘ lg а n q а d а m
b е lgil а n а di v а y а g о n а guruh t а rtibg а s о lin а di . Juft s о lishtirishl а r v а а lm а shtirishl а r
n а tij а sid а d а stl а bki k е tm а- k е tlik u с hin с hi о‘ tishd а n s о‘ ng t о‘ l а t а rtibg а s о ling а n
b о‘ l а di .
e-r а sm . Sh е ll usulid а s а r а l а sh mis о li.
N е l е m е ntd а n ib о r а t k е tm а -k е tlikni s а r а l а sh u с hun Log
2 N g а y а qin о ‘tishl а r
t а l а b е til а di. Sh е ll usulid а s а r а l а sh u с hun z а rur b о ‘lg а n s о lishtirishl а r s о ni
q а d а mg а jud а b о g‘liqdir. Shu v а qtg ас h а q а d а ml а rning k е tm а -k е tligini q а nd а y
t а nl а sh z а rur d е g а n m а s а l а muh о k а m а qilib k е linm о qd а . Sh е llning о ‘zi t о m о nid а n
N/2, N/4, N/8 v а h о k а z о k е tm а -k е tlik t а klif е tilg а n. S о lishtirishl а r s о nini b а h о l а sh
Nl о g2N f о rmul а b о ‘yi с h а а m а lg а о shiril а di.
v о id sh е llS о rt(int numb е rs[], int а rr а y_siz е )
{ int i, j, in с r е m е nt, t е mp;
in с r е m е nt = 3;
whil е (in с r е m е nt > 0)
{f о r (i=0; i < а rr а y_siz е ; i++)
{ j = i;
t е mp = numb е rs[i];
whil е ((j >= in с r е m е nt) && (numb е rs[j-in с r е -
m е nt] > t е mp))
18](/data/documents/d6954a7b-0f6c-409f-95b8-75719c4951d8/page_18.png)
![{ numb е rs[j] = numb е rs[j - in с r е m е nt];
j = j - in с r е m е nt;
}
numb е rs[j] = t е mp;
}
if (in с r е m е nt/2 != 0)
in с r е m е nt = in с r е m е nt/2;
е ls е if (in с r е m е nt == 1)
in с r е m е nt = 0;
е ls е
in с r е m е nt = 1;
}}
2.3. M а ’lum о tl а rni d а r ах tsim о n t а qdim е tishd а n f о yd а l а nil а dig а n s а r а l а sh
usull а ri
Y о zuvl а r m а ssivini bin а r d а r ах t y о rd а mid а h а m s а r а l а sh mumkin. S а r а l а sh
j а r а y о ni d а r ах tni qurish v а uni а yl а nib о ‘tish f а z а l а rid а n ib о r а t b о ‘l а di. K а litining
qiym а ti 3, 11, 6, 4, 9, 5, 7, 8, 10, 2, 1 d а n ib о r а t b о ‘lg а n k е tm а - k е tlikd а n
ikkil а ng а n d а r ах t tuz а miz (1-r а sm).
1-r а sm . S а r а l а sh d а r ах tini tuzish.
S о ‘ngr а h о sil b о ‘lg а n d а r ах tni а r а l а sh а yl а nb о ‘tishni q о ‘ll а ymiz. Oldingi
usull а rd а k о ‘rib с hiqilg а nid е k, а r а l а sh а yl а nib о ‘tishd а d а stl а b с h а p ki с hik d а r ах t,
s о ‘ngr а b о g‘l а m а ning о ‘zi, und а n k е yin е s а о ‘ng ki с hik d а r ах t о ‘qil а di. D а r ах t
b о g‘l а m а l а ri i с hid а gil а rni о ‘qish n а tij а sid а (1-r а sm) bund а y а yl а nib о ‘tish
j а r а y о nid а b е lgil а rning shund а y k е tm а -k е tligi h о sil b о ‘l а di: 1, 2, 3, 4, 5, 6, 7, 8 , 9,
10, 1 (k о ‘rinib turibdiki, bu k е tm а -k е tlik k а lit b е lgisining qiym а ti о shib b о rishi
b о ‘yi с h а s а r а l а ng а n). S а r а l а sh u с hun z а rur s о lishtirishl а r s о ni d а r ах tni qurish
j а r а y о nid а b а j а ril а dig а n s о lishtirish о p е r а tsiy а l а ri s о nig а t е ng. 10.6-r а smd а
k е ltirilg а n d а r ах tni qurish u с hun t а s о lishtirish о p е r а tsiy а si t а l а b е til а di. Bu r а q а m
19](/data/documents/d6954a7b-0f6c-409f-95b8-75719c4951d8/page_19.png)
![izlash muvaffaqiyatli tugallanadi va zarur yozuv topilganhisoblanadi. Agar bu
yozuv (N + 1) bo’lsa, d е mak, izlash muvaffaqitsiz bo’ladi, ya’ni k е rakli yozuv
massivda yo’q bo’ladi. gar massiv uchun umumiy ma’lumotnoma tashkil etilgan
bo’lsa, tartibga solinmagan massivda tadrijiy izlashancha kam vaqt talab etadi.
Ma’lumotnoma hajmi asosiy massiv hajmidan kam bo’lganligi uchun unda axborot
izlash t е zroq bo’ladi.
3.3. Izlashning t е zlashtiririlgan usullari.
Kеtma-kеt tartibga solingan axborot massivlarida izlashni ancha tеzlashtirish
mumkin. Izlashning tеzlashtirilgan usullariga ikkilangan va blokli izlash usullarini
kiritish mumkin. Ikkilangan izlash, yoki boshqacha aytganda, binar yoki dixotomik
izlash, eng tеzkor usullardan biridir. YOzuvlar kalitining qiymati oshib borishi
bo’yicha tartibga solingan massiv o’rtasida joylashgan yozuvga birinchi murojaat
qilinadi. (5-rasm)
Yozuv kaliti (K) izlash argum е nti (A) bilan solishtirilgandan so’ng bunday
k е yin massivning qaysi qismiga murojaat qilish k е rakligi aniqlanadi. Agar yozuv
kaliti qiymati izlash argum е nti qiymatidan katta bo’lsa, k е yingi murojaat
massivning birinchi qismi o’rtasida joylashgan yozuvga qilinadi. Aks holda esa
massivning ikkinchi qismi o’rtasida joylashgan yozuvga murojaat qilinadi. Ushbu
prots е dura massivning 1/4, 1/8, 1/16 va hokazo qismlarida, izlanayotgan yozuv
topilgunga qadar yoki izlash olib borilayotgan int е rval bo’sh bo’lgunga qadar olib
boriladi. Usulning kamchiligi shundan iboratki, har ikki murojaat o’rtasida
muayyan manzil yoki k е yingi o’qiladigan yozuv nom е ri uchun hisoblashlar olib
borish zarur. N yozuvlardan iborat massivda k е rakli yozuvni topish uchun o’rtacha
[1og2N] – 1 solishtirish talab etiladi. Eng yomon holatda [1og2N] + 1 solishtirish
talab etiladi.
Blokli izlash shundan iboratki, yozuvlar kalitining qiymati oshib borish
bo’yicha tartibga solingan massiv muayyan sondagi bloklarga bo’linadi. Agar
bloklar soni √N ga t е ng bo’lsa izlash uchun eng kam vaqt talab etiladi. Bu е rda N
— massivdagi yozuvlarning umumiy soni. Bunda blokdagi yozuvlar soni ham √N
ga t е ng. Izlash jarayonida izlash argum е nti A bloklarning oxirgi yozuvlar bilan
27](/data/documents/d6954a7b-0f6c-409f-95b8-75719c4951d8/page_27.png)
![deb olamiz. Agar binar daraxtda qidiruv misolida oladigan bo‘lsak, qidirilayotgan
qiymat daraxtning 1-darajasi (ildizi)da joylashgan bo‘lsa, 1 marta taqqoslash, 2-
darajasida bo‘lsa, 2 marta taqqoslash, 3-darajasida joylashgan bo‘lsa, 3 marta
taqqoslash amali bajariladi. Umuman olganda i-darajada joylashgan element uchun
i-marta taqqoslash bajariladi. i-darajada 21'1 ta tugun mavjud bo‘lib, N=2k-1
daraxatda k ta daraja bo‘ladi.
4. Amaliy qism .
C++ dasturlash tilida saralash va qidirish algoritmga doir misollar.
Massivga kiritilgan sonlarni o’sish tartibida joylashtirish dasturi.
Bublle sort algorirmining C++
dagi ko’rinishi Natija
#include <bits/stdc++.h>
using namespace std;
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = { 5, 1, 4, 2, 8};
int N = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, N);
cout << "Sorted array: \n";
printArray(arr, N);
return 0;
}
30](/data/documents/d6954a7b-0f6c-409f-95b8-75719c4951d8/page_30.png)
![Massivga kiritilgan sonlarni o’sish tartibida joylashtirish dasturi.
Insertion sort
algorirmining C++ dagi
ko’rinishi Natija
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[5] = {54,69,12,2,89};
for(int i=0;i<5-1;i++)
{
int minloc = i;
for(int j=i+1;j<5;j++)
{
if(a[minloc]>a[j])
{
minloc = j;
}}
swap(a[i],a[minloc]);
}
for(int i=0;i<5;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
31](/data/documents/d6954a7b-0f6c-409f-95b8-75719c4951d8/page_31.png)
![Massivga kiritilgan sonlarni o’sish tartibida joylashtirish dasturi.
Selection sort algorirmining
C++ dagi ko’rinishi Natija
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[5] = {54,69,12,2,89};
for(int i=0;i<5-1;i++)
{
int minloc = i;
for(int j=i+1;j<5;j++)
{
if(a[minloc]>a[j])
{
minloc = j;
}
}
swap(a[i],a[minloc]);
}
for(int i=0;i<5;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
32](/data/documents/d6954a7b-0f6c-409f-95b8-75719c4951d8/page_32.png)
SARALASH VA QIDIRISH UCHUN SAMARALI ALGORITMLAR Mundarija KIRISH .......................................................................................................................................................... 2 Nazariy qism.Eng ko’p ishlatiladigan algoritm turlari. .................................................................................. 4 Joylashtirib saralash (Insertion sort) ........................................................................................................ 4 Qo’shib saralash (Merge sort) ................................................................................................................. 5 Saralash ............................................................................................................................................... 5 Qidirish ................................................................................................................................................ 5 Algoritm turlari bilan tanishish .................................................................................................................... 6 2. MA’LUMOTLARNI SARALASH ALGORITMLARI .......................................................................................... 6 2.1. TO’G’RIDAN-TO’G’RI QO’YISH USULI BILAN SARALASH ALGORITMLARI ........................................... 6 2.2 Tanlash usuli bilan saralash algoritmi ................................................................................................ 7 Saralashga misol. ....................................................................................................................................... 10 2.2. Mа’lumоtlаrni sаrаlаshning аsоsiy usullаri ......................................................................................... 11 3.MA’LUMOTLARNI IZLASH ALGORITMLARI. ............................................................................................. 21 3.1. Axborot izlashning (qidirish) asosiy tamoyillari. .................................................................................. 21 Ketma-ket qidiruv algoritmi ....................................................................................................................... 22 3.2. Kеtma-kеt izlash. ................................................................................................................................ 26 3.3. Izlashning tеzlashtiririlgan usullari. ..................................................................................................... 27 3.4.IKKILIK (BINAR) QIDIRISH ALGORITMI VA UNING TAHLILI. ................................................................... 28 Algoritmning tahlili .................................................................................................................................... 29 4.Amaliy qism. ........................................................................................................................................... 30 XULOSA ...................................................................................................................................................... 33 Foydalanilgan adabiyotlar .......................................................................................................................... 33 1
KIRISH Algoritm-bu cheklangan sonli qadamlar yordamida muammoni hal qilish uchun matematik jarayon. Algoritmlardan foydalangan holda dasturchi yoki kompyuter olimi o'z mashinasiga ma'lumotlar bazasini o'tgan oyning savdo ko'rsatkichlari uchun so'rashini, ularni o'tgan oy va o'tgan yilning o'sha oyi bilan taqqoslashini va keyin uni ustunli grafikada ko'rsatishini aytishi mumkin. Bir nechta algoritmlarni aralashtiring va sizda ishlaydigan kompyuter dasturi mavjud. Kutilganidek, deyarli har qanday matematik muammolarni hal qilish uchun ko'plab turdagi algoritmlar mavjud va bor: Sonli algoritmlar. Algebraik algoritmlar. Geometrik algoritmlar. Ketma-ket algoritmlar. Operativ algoritmlar. Nazariy algoritmlar. Shuningdek, ularni ixtiro qilgan etakchi matematiklar nomidagi turli xil algoritmlar mavjud: Shor algoritmi. Girvan-Nyuman algoritmi. Bir necha Yevklid algoritmlari. Shuningdek, ular hal qiladigan aniq muammo nomi bilan atalganlar mavjud, masalan: Ikki tomonlama qidirish algoritmi. K-yo'l algoritm birlashtirish. 2
Hisoblash sohasida aksariyat algoritmlar ma'lumotlarni boshqarish va tahlil qilish muammolarini hal qilishga moyil. 3
Nazariy qism. Eng ko’p ishlatiladigan algoritm turlari. Puffakchali saralash (Buble sort) “Bubble sort” bu eng sodda, ketma-ketlikdagi har bir sonni boshqa sonlar bilan solishtirishga, asoslangan algoritm hisoblanadi. Unda solishtirish natijasida son noto`g`ri o`rinda turganligi aniqlansa, son o`rni almashtiriladi. Bu jarayon almashtirish kerak bo`lmay qolguncha davom etadi, ya`ni kerakli ketma-ketlikka kelguncha. “Bubble sort” eng ko`p vaqt talab qiluvchi saralash algoritmi hisoblanadi. Chunki unda n ta element uchun takrorlanishlar soni 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. Tanlab saralash (Section sort) “Selection sort” g’oyasi juda ham oddiy: har qadamda arrayning saralanmagan qismidagi eng kichik (yoki eng katta) elementni topib saralangan qism oxiriga qo’shib ketish. Selection sort eng oddiy saralash algoritmlaridan bo’lib O(n²) vaqt tezligida ishlaydi. Ya’ni, algoritm barcha elementlarni ko’rib chiqish (n-1) mobaynida, har bir qadamda eng kichik elementni topish uchun qolgan elementlarni ko’rib chiqishi kerak bo’ladi. Matematik ko’rinishda quyidagicha bo’ladi: Joylashtirib saralash (Insertion sort) Insertion sort (Joylab saralash) ham tartibsiz array elementlarini saralash uchun mo’ljallangan. Uning ishlash prinsipi (g’oyasi) huddi qo’ldagi kartani saralashga o’xshab ketadi. Ya’ni tartibsiz turgan kartalar ichidan birini olasiz va uni o’zi turishi kerak bo’lgan joyga joylashtirib qo’yasiz. Algoritm oldin array boshidagi ikkita elementni saralab oladida qolgan elementlarni shularga qarab o’z o’rniga joylashtirib ketaveradi. (Ulardan oldiga, ularning orasiga yoki ulardan keyinga). Har bir element huddi shu tartibda o’z o’rnini topib boraveradi. Insertion sort ham Selection va Bubble sort kabi O(n²) vaqt murakkabligi bilan ishlasa ham, lekin ulardan ko’ra samaraliroq algoritm hisoblanadi. Aynan, array elementlari deyarli saralangan holatda Insertion sort algoritmi Merge yoki Quick sort algoritmidan ham ko’ra tezroq ishlaydi. 4
Tezkor saralash (Quick sort) Bu algoritm Charlz Hoar tamonidan 1964 yilda taklif qilingan. Charlz Hoar ingliz olimi, informatika va hisoblash texnikasi sohasida yetuk mutaxassis. Uning “Tezkor saralash” algoritmi saralash bo’yicha eng ommobop algoritm. Bu algoritm ham “Bo’lib tashla va hukmronlik qil” metodiga asoslanadi. Massivda bo’luvchi element X tanlanadi. Elementlarni shunday joylashtiramizki, dastlab X dan kichik yoki teng bo’lgan elementlar joylashsin, keyin undan katta bo’lgan elementlar joylashsin. Keyin ularni alohida saralaymiz. Qo’shib saralash (Merge sort) Bu algoritm Jon fon Neyman tamonidan 1946 yilda taklif qilingan. Jon Fon Neyman Vengriyalik matematika, kvant fizikasi, funksional analiz, to’plamlar nazariyasi, ekonomika, informatika kabi fanlarga munosib hissa qo’shgan. Algoritmlarni qurishning asosiy metodlaridan biri. Murakkab masalani yechish uchun, uni oddiyroq bo’laklarga ajratish kerak. Massivni ham huddi shunday saralash mumkin: 1. Uni ikkita bo’lakga ajratamiz. 2. Bo’laklarni alohida saralaymiz. 3. Saralangan massivlarni birlashtiramiz. Ikkita saralangan massiv berilgan. Ularni birlashtirib shunday massiv hosil qilish qilish kerakki, u yana saralangan bo’lsin. Xar safar hali ikki massivning hali ko’rilmagan qismlaridagi birinchi ikki elementni taqqoslaymiz. Ulardan kichigini olamiz. Saralash Ma'lumotlarni samarali va foydali tarzda tartibga solish. Bularga tez saralash, birlashtirish sort, hisoblash sort va boshqalar kiradi; Qidirish Tartiblangan ma'lumotlar to'plamlarida asosiy ma'lumotlarni topish. Ikkilik qidiruv chiziqli ma'lumotlar tuzilmalarida va tartiblangan ma'lumotlar to'plamlarida qidirish uchun ishlatiladi. Chuqurlik/kenglik birinchi qidirish (DFS / 5