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](/data/documents/96de3622-5f4d-49c4-adc9-0157908f30ce/page_10.png)
![{
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 :](/data/documents/96de3622-5f4d-49c4-adc9-0157908f30ce/page_11.png)
![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](/data/documents/96de3622-5f4d-49c4-adc9-0157908f30ce/page_12.png)
![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 :](/data/documents/96de3622-5f4d-49c4-adc9-0157908f30ce/page_14.png)
![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]]++;](/data/documents/96de3622-5f4d-49c4-adc9-0157908f30ce/page_15.png)
![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.](/data/documents/96de3622-5f4d-49c4-adc9-0157908f30ce/page_16.png)
Mavzu: Saralash algoritmlanini vizuallashtirish I. Kirish Saralash haqida ma’lumot va ularning qo’llanilishi. II.Asosiy qism Nazariy qism 1. Saralash xossalari va ularning sinflari 2. Saralash algoritmlari bajarilish tezligida xotirani effektiv ishlatilishi bo’yicha baholash. 3. Ichki va tashqi saralash. Amaliy qism 1.Saralash bo’yicha algaritmlar. 2. Saralashga oid misollar. 3.Sanash orqali saralash. 4.Razryadli saralash(Raqamli saralash). III.Xulosa: Saralashning axamiyati. IV. Foydalangan adabiyotlar ro’yxati.
Kirish: Saralashdan biz kundalik hayotmizda ko’p foydalanamiz. Masalan bozordan biror narsa harid qilishimizda, uning ko’piroq narxi bilan qiziqamiz yoki ularni taqqoslaymiz. Bu narsalar bizga oddiy hodisa bo’lib qolgan, lekin biz siz bilan bu jarayon qanaqa miyamizda xosil bo’layotganligini bir o’ylab ko’raylikchi. Demak, oddiygina biz kunda faydalnayotgan xarakatlarimizni dasturini tuzish uchun ko’p narsalarni bilishimiz va aniq bir maqsadga yo’naltirgan tartiblangan qoidalar yig’indisi zarur bo’ladi. Agar ma’lumotlar kompyuter xotirasida muayyan tartibda saqlanadigan bo’lsa, axborotga ishlov berish va uni izlash bilan bog’liq ko’p masalalar oddiyroq, tezroq va samaraliroq xal qilinadi. Bir qator xollarda ma’lumotlarning tartibga solinganligidan foyda aniq bo’lib, maxsus isbotlashlarni talab etmaydi. Agar lug’at yoki telefon ma’lumotnomasida so’zlar va familalar alifbo tartibida joylashtirilmaganda ulardan foydalanish qanchalik qiyin bo’lishini tasavvur etish mumkin. Lekin ma’lumotlarni saralash zaruriyati masalasi har safar muayyan vazifasiga nisbatan hal qilishi zarur. Bunda tashqi xotira qurulmalari imkoniyatlari, opetativ xotira xajmi, ma’lumotlarga murojaat qilish tezligi, ularni yangilab turish tezligi va ishlov berish xarekteri kabilarni taxlil qilish zarur. Turli ilovalarda tartibga solishning turli mezonlaridan foydalaniladi. Ma’lumotlarularga murojat qilish e’htimolining qiymati, qancha tez-tez murojat etib turishiga ko’ra tartibga solishi mumkin. Odatda, tartibga solish yozuv bo’yicha amalga oshiriladi. Axbotot tizimlari bilan ishlov beriladigan ma’lumotlar birligi bir qator axborot maydonidan iborat bo’lgan yozuv hisoblanadi. Yozuv faqat bittagina maydondan iborat bo’lishi mumkin va bu xolda u kalitli hisoblanadi. Tartibga solish natiyjasida yozuvlar kalitlarning qiymati ortib borishi yoki kamayib borish tartibida joylashadi. Bunday tartibga solish jarayoni saralash deb ataladi. Masalan, fakultet talabalari to’g’risidagi ma’lumotlardan iborat bo’lgan yozuvlar
talabalarning reyting daftarchalari nomerlari bo’yicha tartibga solingan bo’lishi mumkin. Yozuvlar dastlabki ketma-ketligi turli darajada tartibga solingan bo’lishi mumkin. Balki yozuv elementlari belgilangan tartibda joylashgan bo’lishi mumkin. Boshqa bir xolatda elementlarga teskari, ya’ni yozuvlarning dastlabki ketma - ketligi teskari tartibda joylashgan bo’lishi mumkin. Yozuvlarning dastlabki ketma- ketligining qanday tartibda joylashganlik darajasiga ko’ra, solishtirishlar va joyini o’zgartirishlarning u yoki bu soni talab etiladi. Saralash usulini boxolashda solishtirishlar va o’rnini o’zgartirishlarning eng ko’p va kam sonlarini topish juda onson. Bu operatsiyalarning o’rtacha sonini aniqlash uchun kombinatorikaning tegishli bo’limlarini jalb etish zarur. Odatda, saralash jarayonida bajariladigan solishtirish operatsiyalarining o’rtacha soni va elementlarining o’rnini almashtirish yoki o’zgartirishning o’rtacha soni turli usullarni baxolash mezonlari xisoblanadi. Saralash samaradorligi solishtirishning o’rtacha soniga bo’linmasi sifatida aniqlanadi. EXM larning operatsiyon tizimlari, xech bo’lmaganda, bitta dastur – saralash utilitasidan iborat bo’ladi. Lekin ma’lumotlarga ishlov berishning muayyan vazifalarini xal qilishda utilita taklif etilayotgan usil yaroqsiz bo’lishi va boshqa usilni ishlab chiqish yoki foydalanishga to’g’ri kelishi mumkin. Shu munasabat bilan saralashning asosiy usillarini bilish va muayyan vazifa uchun yaroqli bo’lgan u yoki bu usilni baxolay olish muximdir.
II.Asosiy qism Saralash – bu massiv elementlarini biror qonuniyat (o’sish, kamayish, oxirgi raqami, bo’luvchilar, juftlari toqlari …)ga asoslangan holda tartiblashga aytiladi. Umuman olganda saralashning maqsadi berilgan ob’ektlar to’plamini aniq bir tartibda guruxlab chiqish jarayoni tushuniladi. Saralashning maqsadi keyinchalik, saralashgan to’plamni qidirilayotgan elementini topishdani borat. Bu qariyib universal, fundamental jarayon. Biz bu jarayon bilan har kuni uchrashamiz – telefon daftaridagi saralash, kitoblar sarlavhasida, kutubxonalarda, lug’atlarda, pochtada savdoda va x.k. Xar qanday saralash bu dastur demakdir va saralash presedurasining tavsivlarining baxosi dastur qanchalik yaxshi tuzilganiga bog’liq bo’ladi.Ikkita turli usillarning ish unimidagi farq “ yaxshi ” va “ yoman ” dasturlashtirilgan aynan bitta usil o’rtasidagilarga nisbatan bir necha kam bo’lishi mumkin. Saralash presedurasi uchun sarflanadigan xaqiqiy mashina vaqti massivlardan ko’rib chiqish, qiyoslash va sikllarni tashkil etish, ma’lumotlarni boshqa joyga ko’chirish kichik dasturlari, kichik dasturlarning aloqasi uchun bog’liq bo’ladi. Bugun biz siz bilan massiv elementlarini saralashni ko’rib chiqamiz. Saralashning juda ko’pusullari mavjud. Ular turli to’plamlar uchun turlicha bo’lishi mumkin. Massivni saralash uchun ishlatiladigan usul unga berilgan xotirani ixcham holda ishlatish lozim. Boshqacha qilib aytganda, saralanayotgan massiv xuddi shu massivni o’zida amalga oshirilishi lozim. Saralash usullari kam mashina vaqtini talab qilishi lozim. Eng yaxshi tez algoritmlar tartibidagi saralashlarni talab etadi.
n*log n Bu yerda ikkita saralashni farqlash lozim. Ichki va tashqi saralash. Ichki saralash deganda, massivlarni saralashni, Tashqi saralash deganda esa, fayl elementlarini saralashni tushunamiz. Algoritmning asosiy xossalaridan biri unga qo’llanish sferasi(sohasi) bilan bog'liq. Asosan ikkita tur saralashi mavjud: •Ichki saralash. Boshqacha qilib aytganda, bunday saralash massivlarda saralashni amalga oshiradi. Bunda keltirilgan n ketma – ketlik operativ xotirada joylashga va bunda ixtiyoriy yacheykaga raxsatli kirish mavjud. Asosan bu yerda o‘z joyida saralash amalga oshiriladi. • Tashqi saralash. Bu yerda fayllar ustida saralash a malga oshiriladi. Albatta, bunday saralashda vaqt ko‘p ketadi, lekin, o’lcham jixattan katta ketma-ketliklarni saralash mumkin. Faraz qilaylik, bizgaα 1 , α 2 , . . . , α n elementlar berilgan bo’lsin, u holda massivni saralash deganda, uni elementlarini o’rinlariga almashtirish tushuniladi. α k 1 , α k 2 , . . . , α k n