1]){
int t=a[j-1]; a[j-1]=a[j]; a[j]=t;
j=j-1;
}
}
Faraz qilaylik, taqqoslashlar soni C, o„rinlashtirishlar soni M bo„lsin. Agar massiv elementlari kamayish tartibida bo„lsa, u holda taqqoslashlar soni eng katta
bo„lib, u
Cmax
= n(n −1) 2
ga teng bo„ladi, ya‟ni
O(
n2 ). O„rinlashtirishlar
soni esa
Mmax = Cmax + 3(n −1)
ga teng bo„ladi, ya‟ni
O(n2 ). Agar berilgan massiv o„sish
tartibida saralangan bo„lsa, u holda taqqoslashlar va o„rinlashtirishlar soni eng
kichik bo„ladi, ya‟ni
Cmin = n −1,
Mmin = 3(n −1) .
Do'stlaringiz bilan baham: