Algoritmlash p65. p65

Tokcha ta rtib  raqami
1
2
3
4
5
6
7
8
9
Boshlang‘ich  holatda  kublar  soni
7
12
1 49
3
1 0
15
12
Kamayish tartibida  saralangandan  keyin
49
15
12
12
7
3
1
1
0
157

---

Yechim. 
Biz  saralashning 
joylashtirish 
deb  ataluvchi  usulidan 
foydalanamiz.  Bu  usulning  ma’nosi  quyidagicha:  1-tokchadan  N  
tokchagacha  qarab  eng  ko ‘p  ku b li  tokcha  aniqlanadi  va  undan 
oldingi tokchadan boshlab  1-tokchagacha har b ir tokchadagi kublar 
b itta   tokcha  o‘ngga  suriladi,  so‘ng  1-tokchaga  eng  k o ‘p  kub 
o‘tkaziladi;  2-tokchadan  N   tokchagacha  qarab  eng  ko ‘p  ku b li 
tokcha  a n iq la n a d i  va  undan  o ld in g i  tokchadan  boshlab  2- 
tokchagacha har b ir tokchadagi kublar bitta  tokcha o‘ngga suriladi, 
so‘ng  2-tokchaga yangi  eng  ko ‘p  kub  o ‘tkaziladi;  3-tokchadan  N  
tokchagacha  qarab  eng  ko ‘p  ku b li  tokcha  aniqlanadi  va  undan 
oldingi tokchadan boshlab  1-tokchagacha har b ir tokchadagi kublar 
b itta  tokcha o ‘ngga suriladi,  so‘ng  3-tokchaga yangi eng  ko ‘p  kub 
o‘tkaziladi  va  hokazo  (N -1)-tokchaga  o ‘tka zilish i  bilan  jarayon 
to ‘xtaydi,  chunki  surilish  va  o ‘tkazishlar  natijasida  N -tokchada 
eng  kam  sondagi  kublar turgan bo‘ladi.  A lg o ritm i  quyidagicha:
1  DAN N-1  GACHA BAJAR 
o‘tkaz  tokcha(i),  Zt 
i+1  DAN N  GACHA BAJAR 
AGAR ZtU HOLDA
o‘tkaz  tokcha(i),  Zt 
TAMOM
TAMOM 
{eng  ko ‘p  ku b li tokcha  aniqlandi}
Ek-1  DAN  i  GACHA  BAJAR
{Saralovchi I I I  teskaricha sanayapti} 
o ‘tkaz  tokcha(k),  tokcha(k+1)
TAMOM 
{o ‘ngga b itta   surilish  tugadi}
o‘tkaz  Zt,  tokcha(i)
{eng ko‘p sonli kublar i-tokchaga o‘tdi}
TAMOM
Keling, 
joylashtirish 
usulida faqat  siklla rn i  o ‘zi necha  qadam- 
lig in i jadval  yordam ida  hisoblab  ko ‘ramiz:
8.2-jadval