Saralash algoritmlanini vizuallashtirish
![Xar ikkita juftlik solishtiriladi.
A[N-1] ва A[N],
A[N-2] ва A[N-1]
…
A[2] ва A[1]
Bu solishtirishlarda qaysi massivning elementi kichik bo’lsa o’sha element
bilan joyini almashtiradi. Buning uchun bizga almashtiradigan qiymat kerak.
Masalan ikkita stakandagi ikki xil suyuqlik bor ularning o’rnini almashtirish uchun
bizga albatta bitta bo’sh stakan kerak bo’ladi. Shuning uchun biz yangi bir c degan
o’zgaruvchi tanlab olamiz.
m[i]=c;
m[i]=m[i+1];
c=m[i+1];
Masala: massiv elementlarini o’sish tartibida chiqarish.
Bu masalani hal qilish uchun quyidagi algaritmlardan foydalanamiz.
Dasturini ko’ramiz.
#include <iostream>
using namespace std;
int main()7 7 7 3
4 4 3 7
3 3 4 4
5 5 5 5 3 3
4 4
7 5
5 73 3 3
7 4 4
4 7 7
5 5 5](https://docx.uz/documents/31169c9f-19b5-488c-bf62-71cca551af08/page_10.png?v=1)
![{
int N, i , j, c;
int A[100];
cout<<"Massivning nechta elementi bor? ";
cin>>N;
cout<<"Massivning elementlarini PROBEL bilan kiriting "<<endl;
for (i=1; i<=N; i++)
cin>>A[i];
for (i = 1; i <= N; i ++)
{
for (j = N-1; j >= i ; j --)
if ( A[j] > A[j+1] )
{
c = A[j];
A[j] = A[j+1];
A[j+1] = c;
} }
for (i = 1; i <= N; i++)
cout<<A[i]<<" ";
return 0;
}
Natiyja si :](https://docx.uz/documents/31169c9f-19b5-488c-bf62-71cca551af08/page_11.png?v=1)
![TANLASH USULI
• Eng kichik elementni toping va uni birinchi o ringa qo ying.a[1]‟ ‟
element bilan joyini almashtiring.
• Qolganlaridan eng kichigini toping va uni ikkinchi o ringa qo ying
‟ ‟
a[2] binan o rnini almashtirng,va shunday davom etadi.
‟
Ushbu usil bilan saralashda yozuvlarning tartibga solingan ketma-ketligi
xotiraning dastlabki ketma-ketlik joylashgan uchastkasining o’zida tashkil
etiladi. Birinchi o’tish davomida eng kichik element izlanadi. Bu element
topilganidan so’ng uni dastlabki ketme-ketlikdagi birinchi element bilan joyi
almashtililadi, natiyjada eng kichik element tulayotgan tartiga solingan ketme
ketlikda birinchi element xolatini egalaydi.
6
5
3
4 3
5
6
4 3
4
5
63
4
6
5](https://docx.uz/documents/31169c9f-19b5-488c-bf62-71cca551af08/page_12.png?v=1)
![tartibga solingan bo’lsa bitta xam joy almashtirishlar talab etimaydi. Demak, joy
almashtirish talab etmaydi.
for( i = 1; i <= N ; i ++ )
{
nMin = i ;
for ( j = i+1; j <= N; j ++)
if( A[j] < A[nMin] )
nMin = j;
if( nMin != i )
{
c = A[i];
A[i] = A[nMin];
A[nMin] = c;
}
}
Natiyja si :](https://docx.uz/documents/31169c9f-19b5-488c-bf62-71cca551af08/page_14.png?v=1)
![Sanash orqali saralash
Sanash orqali saralash faqat chekli qiymatli sonlarni saralash mumkin.
Masalan, massivning barcha elementlari qiymatlari 0..10 5
intervalga tegishli
bo’lsa.
Sanash orqali saralash uchun yordamchi massiv ochamiz, bu massiv har
bir sondan qancha borligini saqlab turadi. Har bir songa kelganda uning
sonini oshirish uchun yordamchi massivdan shu indeksning qiymatini 1 ga
oshiramiz.
Keyin har bir 0..10 5
ndekslarni birma-bir ko’rib bu sondan necha marta
uchragan bo’lsa shuncha marta chiqaramiz.
Bunday saralash usuli massiv elementlarining maksimal qiymati massiv
o’lchamiga nisbatan kichik bo’lganda ancha effektiv bo’ladi.
Ishlash vaqti O(n+Max);
Qo’shimcha xotira O(Max)
Max massiv ementlari maksimali.
#include <iostream>
using namespace std;
int maxn = 100001;
int cnt[100001];
int main()
{int n; cin>>n;
int a[n+1];
for (int i = 0; i < maxn; i++) cnt[i] = 0;
for (int i = 1; i <= n; i++) cin>>a[i];
for (int i = 1; i <= n; i++) cnt[a[i]]++;](https://docx.uz/documents/31169c9f-19b5-488c-bf62-71cca551af08/page_15.png?v=1)
![int ind = 0;
for (int i = 0; i < maxn; i++)
{ for (int j = 1; j <= cnt[i]; j++) { a[++ind] = i; }}
for (int i = 1; i <= n; i++) { cout<<a[i]<<endl;}
return 0;
Natiyja: Quyidagicha chiqadi.](https://docx.uz/documents/31169c9f-19b5-488c-bf62-71cca551af08/page_16.png?v=1)
Saralash algoritmlanini vizuallashtirish