Algoritmlash p65. p65

Tash­
qi
sikl  i
O ‘tkazish
Ek
Ich-
ki
sikl j
Shart
tekshirish
Shart
qiymati
U HOLDA
o ‘tkazish
Ek
1
7 = t(1 )^
Zt=7
1
2
7=ZtROST
12=t(2)^Zt=12
2
162

---

T ash-
qi
sikl  i
O
‘tkazish
Ek
Ich-
ki
sikl  j
S hart
tekshirish
S hart
qiymati
U  HOLDA
o ‘tkazish
Ek
3
y = t ( y > ^
Z t = 7
1
2
7 = Z t< t(2 >  =  1 2
ROST
1 2 = t( 2 > —> Z t= 1 2
2
3
1 2 = Z t< t(3 > = 1
YO LG ‘ON
—
2
4
1 2 = Z t < t( 4 > = 4 9
ROST
4 9 = t (4 > —  Z t = 4 9
4
5
4 9 = Z t < t( 5 > = 3
Y O L G O N
—
4
7 = t ( 1 > ^ t -
(4 > = 7
4 9 = Z t
^ t ( 1 > = 7
Bu amallardan keyin tokchalarda kublar quyidagicha joylashadi:
Tokcha ta rtib  raqami
1
2
3
4
5
Boshlang‘ich holatda  kublar  soni
49
12
1
7
3
Davom  etamiz:
Tash-
qi
sikl  i
O ‘tkazish
Ek
Ichki
sikl j
Shart
tekshirish
Shart
qiymati
U HOLDA
o ‘tkazish
Ek
2
12=t(2>—
Zt=12
2
3
12=Zt=1
YOLG‘ON
—
2
4
12=Zt=7
YOLG‘ON
—
2
5
12=Zt=3
YOLG‘ON
—
2
12=t(2>—-
t(2>=12
12=Zt 
—1(2>=12
Hech  narsa  o ‘zgarmadi,  davom  etamiz:
Tash- 
qi sikl
O ‘tkazish
Ek
Ichki 
sikl j
Shart
tekshirish
Shart
qiymati
U HOLDA
o ‘tkazish
Ek
3
1=t(3>— Zt=1
3
4
1 =Zt=7
ROST
7=t(4>—Zt=7
4
5
7=Zt=3 YOLG‘ON
—
4
1=t(3>—1(4>=1
7=Zt —1(3>=7
E ndi  bu  am allardan  keyin  tokchalarda  kublar  quyidagicha 
joylashadi:
163

---

Tokcha ta rtib  raqami
1
2
3
4
5
Boshlang‘ich  holatda  kublar  soni
49
12
7
1
3
Va  nihoyat  oxirgi jarayon:
Tash-
qi
sikl  i
O ‘tkazish
Ek
Ichki
sikl j
Shart
tekshirish
Shart
qiymati
U HOLDA
o ‘tkazish
Ek
4
1=t(4)^ Zt=1
4
5
1=ZtROST
3=t(5)^Zt=3
5
1=t(4)^t(5)=1
3=Zt^t(4)=3
Va  nihoyat  kerakli  ta rtib   o ‘rn a tild i:
Tokcha ta rtib  raqami
1
2
3
4
5
Boshlang‘ich holatda  kublar  soni
49
12
7
3
1
Charchab ketdingiz-a!  Lekin,  Bek ham Siz bilan birga ishlayot- 
ganini unutmang.  C ho‘chimang,  kichkinagina bola o ‘zlashtirayot- 
gan usullar  sizga  ham bo‘ysunadi.
T o ‘liq lik   uchun  yana  b ir  usulni  ko ‘rib  chiqamiz.  U n i  oddiy 
almashtirish yoki «pufakcha» usuli deb atashadi.  Boshqa har qanday 
saralash  usullari  biz  ko ‘rib  chiqayotgan  uchala  usulning  hosilasi 
bo‘lar  ekan.
8.14-masaladagi  kamayish  tartibida  saralash  talab  qilinganda 
oddiy  almashtirish  usuli  quyidagicha:
1- 
takrorlanishda:  1-tokcha  va  2-tokchadagi  kublar  soni  taq- 
qoslanadi,  agar  1-tokchadagi  kublar  soni  kam  bo‘lsa  2-tokchaga 
o‘tkaziladi,  aks  holda  hech  narsa  q ilin m a yd i;  2-tokcha  va  3- 
tokchadagi  kublar  soni  taqqoslanadi,  agar  2-tokchadagi  kublar 
soni  kam  bo ‘lsa  3-tokchaga  o ‘tkaziladi,  aks  holda  hech  narsa 
qilinm aydi va hokazo,  (N -1)-tokcha va  N-tokchadagi kublar  soni 
taqqoslanadi,  agar  (N -1)-tokchadagi  kublar  soni  kam  bo‘lsa  N- 
tokchaga  o ‘tkaziladi,  aks  holda  hech  narsa  qilinm aydi.  N atijada 
ku b la ri  soni  eng  kam  b o ‘lgan  tokcha  N -tokchaga  o‘tkazilgan 
b o ‘ladi.
2- 
takrorlanishda:  1-tokcha  va  2-tokchadagi  kublar  soni  taq­
qoslanadi,  agar  1-tokchadagi  kublar  soni  kam  bo‘lsa  2-tokchaga 
o‘tkaziladi,  aks  holda  hech  narsa  q ilin m a yd i;  2-tokcha  va  3- 
tokchadagi  kublar  soni  taqqoslanadi,  agar  2-tokchadagi  kublar 
soni  kam  bo ‘lsa  3-tokchaga  o ‘tkaziladi,  aks  holda  hech  narsa
164

---

qilinm aydi  va  hokazo,  (N -2)-tokcha  va  (N -l)-to kch a d a g i  kublar 
soni  taqqoslanadi,  agar  (N -2)-tokchadagi  kublar  soni  kam  bo‘lsa 
(N -l)-to k c h a g a   o ‘tka zila d i,  aks  holda  hech  narsa  qilinm a ydi. 
Demak,  oxirgi  N -tokcha  endi  qaralmaydi.  N atijada  N-tokchadan 
oldingi tokchalardan kublari  soni eng  kam bo ‘lgan tokcha  (N -1 )- 
tokchaga  o ‘tkazilgan  bo‘ladi.
3 -ta kro rla n ish d a :  1-to kcha  va  2 -to kch a d a g i  ku b la r  soni 
taqqoslanadi,  agar 1-tokchadagi kublar soni kam bo‘lsa 2-tokchaga 
o ‘tkaziladi,  aks  holda  hech  narsa  qilin m a yd i;  2-tokcha  va  3- 
tokchadagi  kublar  soni  taqqoslanadi,  agar  2-tokchadagi  kublar 
soni  kam  bo‘lsa,  3-tokchaga  o ‘tkaziladi,  aks  holda  hech  narsa 
qilinm aydi  va  hokazo,  (N -3)-tokcha  va  (N -2)-tokchadagi  kublar 
soni  taqqoslanadi,  agar  (N -3)-tokchadagi  kublar  soni  kam  bo‘lsa 
(N -2)-tokchaga  o‘tka zila d i,  aks  holda  hech  narsa  qilinm a ydi. 
Demak,  o xirg i  2  ta  tokcha  endi  qaralm aydi.  N atijada  (N -1 )- 
tokchadan  o ld in g i  tokchalardan  kublari  soni  eng  kam  bo ‘lgan 
tokcha  (N -2)-tokchaga o ‘tkaziladi.
Shu tariqa davom ettirilsa,  (N -1)-takrorlanishda kerakli jadvalni 
hosil qilam iz. Masalada kamayish tartibida saralash so‘ralgani uchun 
har qadamda tokchalardan kam sonlisini o‘ngga surib borayapmiz. 
O ddiy  alm ashtirish usulining  algoritm i  quyidagicha:
TA K R O R LA N S IN  N -1  M AR TA
1  DAN N -i  G ACHA BAJAR
AGAR  to kch a (j)< to kch a (j+ 1 )
U  H O LD A
o ‘tkaz  to kch a (j+ 1 ),  Z t 
o ‘tkaz  tokcha(j),  tokcha(j+ 1) 
o ‘tkaz  Z t,  tokcha(j)
T A M O M
T A M O M
T A M O M
Algoritm dan ko ‘rinadiki, tashqi sikl faqat ko‘riladigan tokchalar 
sonini  kam aytirish  uchun  xizm at  qilm oqda.  H a r  doim gidek, 
«pufakcha»  usulida  ham  faqat  sikllarning  o‘zi  necha  qadam ligini 
jadval  yordam ida  hisoblab  ko ‘ramiz:
8.6-jadval