139
Bir o„lchovli massiv elementlarini tartiblash
Massiv elementlarini tartiblash jarayoni ikki xil bo‗ladi, ya‘ni massiv
elementlarini o‗sish yoki kamayish bo‗yicha tartiblash mumkin. C++ dasturlash
tilida massiv elementlarini o‗sish va kamayish bo‗yicha tartiblashda bir biridan
katta farq qilmaydi, ularning algoritmi bir xil bo‗ladi faqat o‗sish va kamayish
bo‗yicha tartiblashda bitta > yoki < shartlar bilan farq qiladi. Shuning uchun
tartiblash masalalarini bittasini o‗sish yoki kamayishni tushuntirib o‗tamiz siz
uning tarkibidagi shartni teskarisiga almashtirsangiz o‗sish bo‗lsa
kamayish,
kamayish bo‗lsa o‗sishga almashadi. Ketma-ketliklar va ular ustida amallar orqali
hal etiladigan masalalar tarkibida ketma-ketliklarning o‗sish yoki kamayish
tartibda saralash muommolari yotadi.
Dastlab saralash algoritmlarinig eng oddiy turini ko‗rib o‗tamiz. Bunda berilgan
ketmaketlikning har bir elementi o‗zidan keying elementlar bilan solishtiriladi agar
kichik bo‗lsa almashtiriladi aks holda keyingisi bilan solishtiriladi, shu tariqa
massivning kichik elementlari ro‗yxat boshiga kattalari esa ro‗yxat
oxiriga borib
joylashadi.
Algoritmdagi jarayonni aniqlash uchun quyidagi masalaga e‘tibor bering.
A=[3; 5; 1; 0; 6] ketma ketlikni oddiy usul bilan saralash algoritmi bo‗yicha
quyidagi almashtirishlar hosil bo‗ladi.
[3; 5; 1; 0; 6], [1; 5; 3; 0; 6] , [0; 5; 3; 1; 6] , [0; 3; 5; 1; 6], [0; 1; 5; 3; 6], [0; 1;
3; 5; 6].
Demak yuqoridagi misolga e‘tibor bersak eng kichik elementlar ro‗yxat
boshiga birin keyin harakatlanib o‗tmoqda natijada berilgan ketma ketlik o‗sish
tartibida saralanib qoladi. Bu usulni C++ dasturlash tilida quyidagicha
tasvirlashimiz mumkin.
#include
using namespace std;
int main()
{ int a[90];
int n,t; cout<<‖n=‖;
cin>>n;
for(int i=0;icin>>a[i];
for(int i=0;ifor(int j=i+1;jif(a[i]>a[j]) { t=a[i];
140
a[i]=a[j];
a[j]=t;
}
for(int j=0;j
cout<
cout<<‖\n‖;
return 0;
}
Kiritish uchun ma‘lumot
n=5
3 5 1 0 6
Dastur
natijasi
0 1 3 5 6
Yuqorida keltirib o‗tilgan algoritm bilan massiv kamayish tartibida ham
saralash mumkin, faqatgina sikl ichidagi shartni almashtirish kerak. Kamayish
bo‗yicha tartiblash uchun C++ dasturlash tilida quyidagi dasturga e‘tibor bering.
#include
using namespace std;
int main()
{ int a[90];
int n,t; cout<<‖n=‖;
cin>>n;
for(int i=0;icin>>a[i];
for(int i=0;ifor(int j=i+1;jif(a[i]a[i]=a[j];
a[j]=t;
}
for(int j=0;jcout<return 0;
}
Kiritish uchun ma‘lumot
n=5
3 5 1 0 6
Dastur natijasi
6 5 3 1 0
141
Saralash uchun bir nechta usullar mavjud, lekin ko‗p hollarda biz ketma-
ketliklarni saralashda vaqt chegarasidan yutqazib qo‗yamiz.
Bunday holatlarni oldini olish uchun ba‘zi mavjud usullarni keltiramiz.
O‗rniga qo‗yish usuli bilan saralash algoritmi: Bunda ikkinchi elementdan
boshlab har bir element tanlab olinib o‘zidan oldingi elementlar bo‗yicha
solishtiriladi. Natijada tanlangan element o‘zidan oldingi elementlar ichida
solishtirish natijasida o‘z joyiga borib tushadi. Bu holat
toki oxirgi elementgacha
bajarilib boradi.
Algoritmdagi jarayonni aniqlash uchun quyidagi masalaga e‘tibor bering.
A=[3; 5; 1; 0; 6] ketma ketlikni o‗rniga qo‗yish usuli bilan saralash algoritmi
bo‗yicha quyidagi almashtirishlar hosil bo‗ladi.
[3; 5; 5; 0; 6], [3; 3; 5; 0; 6] , [1; 3; 5; 0; 6] , [1; 3; 5; 5; 6], [1; 3; 3; 5; 6], [1; 1;
3; 5; 6], [0; 1; 3; 5; 6]
Ushbu jarayonni amalga oshiruvchi algoritm quyidagicha:
Algoritm bo‗yicha C++ tilida quyidagi dastur asosida ko‗p elementdan iborat
massivlarni ham saralash mumkin.
#include
#include
#pragma hdrstop
using namespace std;
#pragma argsused
int main(int argc, char* argv[])
{ int l,i,x,n; int a [100]; cout<<"n="; cin>>n;
Bosh
N,A[i]
(l>=1)
(a[l]>x)
1
0
i=2;i<=N;i++
x=a[i]; l=i-1;
A[l+1]=A[l];
l=l-1;
A[l+1]=x;
A
Tamom
142
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=n;i++)
{ x=a[i]; l=i-1; while((l>=1)&(a[l]>x)) { a[l+1]=a[l]; l=l-1; }
a[l+1]=x;
}
for(int j=1;j<=n;j++) cout<
system("pause");
return 0; }
O‗rin almashtirish usuli bilan saralash algoritmi: Usulning
asosiy prinsipi
katta elementlarning ro‗yxat uchiga otilib chiqadi va bu vaqtda kichik
qiymatlar pastga tushadi. Usulda ichma ich sikldan foydalaniladi birinchi n-1
marta, ikkinchi n-2 marta va oxiri bir marta har bir element o‘zidan keyingi
element bilan solishtiriladi.
Bunda kichik elementlar ro‗yxat oxiriga katta elementlar ro‗yxat boshiga
tushadi. Kuzatish mumkinki, har bir o‗tishda bir qancha
elementlar siljiydi va
bitta elementgina o‗zining o‗rnini qat‘iy egallaydi.
Algoritmdagi jarayonni aniqlash uchun quyidagi masalaga e‘tibor bering.
A=[3; 5; 1; 0; 6] ketma ketlikni o‗rin almashtirish usuli bilan saralash algoritmi
bo‗yicha quyidagi almashtirishlar hosil bo‗ladi.
[3; 1; 5; 0; 6], [3; 1; 0; 5; 6] , [1; 3; 0; 5; 6] , [1; 0; 3; 5; 6], [0; 1; 3; 5; 6]
O‗rin almashtirish usuli bilan saralash algoritmining ko‗rinishi quyidagicha:
O‗rin almashtirish usuli C++ tilida quyidagi ko‗rinishda bo‗ladi.
Bosh
N,A[i],N1=N,x=1
X=1
1
0
N1--; x=0;
i=1;i<=N1;i++
A[i]>A[i+1]
t=A[i]; A[i]=A[i+1]; A[i+1]=t; x=1;
1
0
A
Tamom
