10-mazvzu: tashqi saralash. Saralash usullarini tanlashda hisobga olinadigan omillar. Yozuvni(struktura) joylashtirish usullari

10-MAZVZU: TASHQI SARALASH. SARALASH USULLARINI TANLASHDA HISOBGA OLINADIGAN OMILLAR. YOZUVNI(STRUKTURA) JOYLASHTIRISH USULLARI
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:
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
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; 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:
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
O‘rin almashtirish usuli C++ tilida quyidagi ko‘rinishda bo‘ladi.