Laboratoriya ishi Элементлар жамланмасини бирор белги бўйича тартиблаштириш алгоритми

To„g„ridan-to„g„riqo„shishusulibilansaralashalgoritmi
Bundayusulkartao„yinidakengqo„llaniladi. Elementlar (kartalar) hayolan “tayyor” a(1),...,a(i-1) vaboshlang„ichketma-ketliklargabo„linadi. Harbirqadamda (i=2danboshlanib, harbirqadamdabirbirlikkaoshiribboriladi) boshlang„ichketma-ketlikdani-chi element ajratibolinibtayyorketma-ketlikningkeraklijoyigaqo„yiladi.
To„g„ridan-to„g„riqo„shishorqalisaralashalgoritmiquyidagichabo„ladi:
for (int i=1;i
x=a[i];
xni a[0]...a[i] oraliqningmosjoyigaqo‘shish
}
Keraklijoyniqidirishjarayoniniquyidagitartibdaolibborishqulaybo„ladi. 2-elementdan boshlabharbirelementniqarabchiqamiz, ya‟niharbir element o„zidanoldinturgan element bilansolishtiriladi. Agar qaralayotgan element kichikbo„lsa, oldindaturgan element bilano„rinalmashadivayanao„zidanoldindaturgan element bilansolishtiriladi, jarayonshukabidavometadi. Bu jarayonquyidagishartlarningbirortasibajarilgandato„xtatiladi:
1. x elementioldidauningkalitidankichikkalitlia(j) elementichiqqanda.
2. x elementioldida element qolmaganda.
for (int i=1;i
while(a[j]
int t=a[j-1];
a[j-1]=a[j];
a[j]=t;
j=j-1;
}
}
Algoritmsamaradorligi
Farazqilaylik, taqqoslashlarsoniC, o„rinlashtirishlarsoniM bo„lsin. Agar massivelementlarikamayishtartibidabo„lsa, u holdataqqoslashlarsoniengkattabo„lib, u gatengbo„ladi, ya‟ni .O„rinlashtirishlarsoniesagatengbo„ladi, ya‟ni . Agar berilganmassivo„sishtartibidasaralanganbo„lsa, u holdataqqoslashlarvao„rinlashtirishlarsoniengkichikbo„ladi, ya‟ni , .
Tanlashorqalisaralashalgoritmi
Mazkurusulquyidagitamoyillargaasoslangan:
1. Eng kichik kalitga ega element tanlanadi.
2. Ushbu element birinchi element bilano„rinalmashinadi.
3. Keyinmazkurjarayonqolgann-1, n-2 elementlarbilantakrorlanib, to bittaeng “katta” element qolgunchadavomettiriladi.
for(int i=0;i
for(int j=i+1;j
if (a[i] > a[j]){
int k = a[j];
a[j]= a[i];
a[i]= k;
}
Algoritmsamaradorligi:
Taqqoslashlarsoni
S= N(N-1)/2=(N²-N)/2
Massivtartiblangandao„rinlashtirishlarsoni
M_min=3(N-1)
Massivteskaritartiblangandao„rinlashtirishlarsoni
M_min=M_minN/2=3N(N-1)/2
Ushbuusulbo„yichasaralashbajarilsa, engyomonholdataqqoslashlarvao„rinlashtirishlarsonitartibi n2 bo„ladi.