Kirish 2 I bob asosiy qism 5

Tokcha tartib 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

Yechim. Biz saralashning joylashtirish deb ataluvchi usulidan foydalanamiz. Bu usulning ma’nosi quyidagicha: 1-tokchadan N tokchagacha qarab eng ko‘p kubli tokcha aniqlanadi va undan oldingi tokchadan boshlab 1-tokchagacha har bir tokchadagi kublar bitta tokcha o‘ngga suriladi, so‘ng 1-tokchaga eng ko‘p kub o‘tkaziladi; 2-tokchadan N tokchagacha qarab eng ko‘p kubli tokcha aniqlanadi va undan oldingi tokchadan boshlab 2- tokchagacha har bir 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 kubli tokcha aniqlanadi va undan oldingi tokchadan boshlab 1-tokchagacha har bir tokchadagi kublar bitta tokcha o‘ngga suriladi, so‘ng 3-tokchaga yangi eng ko‘p kub o‘tkaziladi va hokazo (N-1)-tokchaga o‘tkazilishi bilan jarayon to‘xtaydi, chunki surilish va o‘tkazishlar natijasida N-tokchada eng kam sondagi kublar turgan bo‘ladi. Algoritmi 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 kubli tokcha aniqlandi}
Ek-1 DAN i GACHA BAJAR
{Saralovchi III teskaricha sanayapti} o‘tkaz tokcha(k), tokcha(k+1)
TAMOM {o‘ngga bitta surilish tugadi}
o‘tkaz Zt, tokcha(i)
{eng ko‘p sonli kublar i-tokchaga o‘tdi}
TAMOM
Keling, joylashtirish usulida faqat sikllarni o‘zi necha qadam- ligini jadval yordamida hisoblab ko‘ramiz:

Tashqi sikl i	1-ichki sikl j	2-ichki sikl k	Takrorlanishlar soni
1 da	2 dan N gacha	N dan 2 gacha	2(N-1)ta
2 da	3 dan N gacha	N dan 2 gacha	2(N-2)ta
3 da	4 dan N gacha	N dan 2 gacha	2(N-3)ta
4 da	5 dan N gacha	N dan 2 gacha	2(N-4)ta

jadvaldagi qadamlar sonini hisoblashda yuqori chegara topildi. Quyidagi jadvaldagi tokchalar uchun sikllarning qadamlari sonini hisoblang va xulosa yozing.

Bek esa quyidagicha ish tutdi: 1-tokchadan N-tokchagacha eng ko‘p kub taxlangan tokchani topdi va 1-tokcha bilan almashtirdi; 2-tokchadan N-tokchagacha eng ko‘p kub taxlangan tokchani topdi va 2-tokcha bilan almashtirdi; 3-tokchadan N- tokchagacha eng ko‘p kub taxlangan tokchani topdi va 3-tokcha bilan almashtirdi va shu kabi almashtirishlarni (N-1)-tokchagacha davom ettirdi, chunki almashtirishlar natijasida N-tokchada eng kam sondagi kublar turgan bo‘ladi.
Bek o‘zi bilmagan holda oddiy tanlov deb ataluvchi usuldan foydalandi. Bunda u ichma-ich joylashgan sikl tashkil etdi. Tashqi va ichki sikl bir-biridan farqlanishi uchun tokcha tartib raqamida i va j harflardan foydalandi. Tokchaning o‘zi bilan o‘zini taqqoslamaslik uchun ichki siklni doimo bitta keyingi tokchadan boshladi, ya’ni tashqi sikldagi i-tokcha uchun ichki sikldagi sanoqni (i+1)-tokchadan boshlash to‘g‘ri bo‘ladi:
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
o‘tkaz tokcha(i), tokcha(Ek) o‘tkaz Zt, tokcha(i)
TAMOM
Joylashtirish usulidagi kabi oddiy tanlov usulida ham faqat sikllarning o‘zi necha qadamligini jadval yordamida hisoblab ko‘ramiz:

Tashqi sikl i	Ichki sikl j	Takrorlanishlar Soni
1 da	2 dan N gacha	1(N-1>—N-1 ta
2 da	3 dan N gacha	1(N-2>—N-2ta
3 da	4 dan N gacha	1(N-3>—N-3 ta
4 da	5 dan N gacha	1(N-4>—N-4ta
N-2 da	N-1 dan N gacha	1(N-(N-2>> -1-2—2ta
N-1 da	N dan N gacha	1(N-(N-1>> -1-1—1 ta
Hammasi sikllardagi bo‘lib qadamlar soni		1+2+3+...+(N-3>+(N-2>+(N-1>-N(N- -1>:2ta

Ko‘rib turibsiz, oddiy tanlov usulida joylashtirish usuliga qaraganda qadamlar soni ikki marta kam ekan.

Charchab ketdingiz-a! Lekin, Bek ham Siz bilan birga ishlayot- ganini unutmang. Cho‘chimang, kichkinagina bola o‘zlashtirayot- gan usullar sizga ham bo‘ysunadi.
To‘liqlik uchun yana bir usulni ko‘rib chiqamiz. Uni 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 qilinmaydi; 2-tokcha va 3- tokchadagi kublar soni taqqoslanadi, agar 2-tokchadagi kublar soni kam bo‘lsa 3-tokchaga o‘tkaziladi, aks holda hech narsa qilinmaydi 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 qilinmaydi. Natijada kublari soni eng kam bo‘lgan tokcha N-tokchaga o‘tkazilgan bo‘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 qilinmaydi; 2-tokcha va 3- tokchadagi kublar soni taqqoslanadi, agar 2-tokchadagi kublar soni kam bo‘lsa 3-tokchaga o‘tkaziladi, aks holda hech narsa qilinmaydi va hokazo, (N-2)-tokcha va (N-1)-tokchadagi kublar soni taqqoslanadi, agar (N-2)-tokchadagi kublar soni kam bo‘lsa (N-1)-tokchaga o‘tkaziladi, aks holda hech narsa qilinmaydi. Demak, oxirgi N-tokcha endi qaralmaydi. Natijada N-tokchadan oldingi tokchalardan kublari soni eng kam bo‘lgan tokcha (N-1)- tokchaga o‘tkazilgan bo‘ladi.
3-takrorlanishda: 1-tokcha va 2-tokchadagi kublar soni taqqoslanadi, agar 1-tokchadagi kublar soni kam bo‘lsa 2-tokchaga o‘tkaziladi, aks holda hech narsa qilinmaydi; 2-tokcha va 3- tokchadagi kublar soni taqqoslanadi, agar 2-tokchadagi kublar soni kam bo‘lsa, 3-tokchaga o‘tkaziladi, aks holda hech narsa qilinmaydi 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‘tkaziladi, aks holda hech narsa qilinmaydi. Demak, oxirgi 2 ta tokcha endi qaralmaydi. Natijada (N-1)- tokchadan oldingi tokchalardan kublari soni eng kam bo‘lgan tokcha (N-2)-tokchaga o‘tkaziladi.
Shu tariqa davom ettirilsa, (N-1)-takrorlanishda kerakli jadvalni hosil qilamiz. Masalada kamayish tartibida saralash so‘ralgani uchun har qadamda tokchalardan kam sonlisini o‘ngga surib borayapmiz. Oddiy almashtirish usulining algoritmi quyidagicha: TAKRORLANSIN N-1 MARTA
1DAN N-1 GACHA BAJAR
AGAR tokcha(j)U HOLDA
o‘tkaz tokcha(j+1), Zt o‘tkaz tokcha(j), tokcha(j+1) o‘tkaz Zt, tokcha(j)
TAMOM
TAMOM
Algoritmdan ko‘rinadiki, tashqi sikl faqat ko‘riladigan tokchalar sonini kamaytirish uchun xizmat qilmoqda. Har doimgidek, «pufakcha» usulida ham faqat sikllarning o‘zi necha qadamligini jadval yordamida hisoblab ko‘ramiz.
Tokchalardagi kublar saralanganidan keyin eng ko‘p kubli yoki eng kam kubli tokchani topish masalasi juda ham oson ishga aylanganini ko‘rish mumkin. Haqiqatan, bu masalalarning yechimlari saralangan tokchalardagi kubli tokchalardan yoki o‘ng tomondagi oxirgi tokchasi yoki chap tomondagi oxirgi tokchasi bo‘ladi.
Uchala usulning sikldagi qadamlar sonini taqqoslab, «pufakcha» usulining boshqa usullarga nisbatan samaradorligi kam emasligini, murakkabligi esa eng kam ekanligini ko‘rish mumkin.
Ko‘rilgan uchala usulning samaradorligini aniqlash uchun bajariladigan amallar sonini yuqori chegarasini hisoblaymiz (* - ko‘paytirish amali):
1)Joylashtirish usulida:
Amallar soni =(N-1)+2*((N-1)+(N-2)+...+1)+((N-1)+(N- 2)+...+1)+(N-1)=
=2*(N-1)+3*((N-1)+(N-2)+...+1)=2*(N-1)+3*N*(N-1):2=
=(4*(N-1)+3*N*(N-1)):2=(4+3*N)*(N-1):2 ta
2)Oddiy tanlov usulida:
Amallar soni =(N-1)+2*((N-1)+(N-2)+...+1)+2*(N-1) =
= 3*(N-1)+2*N*(N-1):2=(6*(N-1)+N*(N-1)):2 = (6+N)*(N- 1):2 ta
3)Oddiy almashtirish usulida:
Amallar soni =4*((N-1) + (N-2) + ... + 1)=4*N*(N-1):2 = 2*N*(N-1)