«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan kurs ishi

x elementi oldida uning kalitidan kichik kalitli a(j) elementi chiqqanda.

x elementi oldida element qolmaganda.

Dastur kodi:

for (int i=1;i

{

int j=i;

while(a[j]

{

int t=a[j-1];

a[j-1]=a[j];

a[j]=t;

j=j-1;

}

}

Algoritm samaradorligi

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, unga teng bo'ladi. O'rinlashtirishlar soni esa ga teng bo'ladi. Agar berilgan massiv o'sish tartibida saralangan bo'lsa, u holda taqqoslashlar va o'rinlashtirishlar soni eng kichik bo'ladi.

Tanlash orqali saralash algoritmi

Mazkur usul quyidagi tamoyillarga asoslangan:

1. Eng kichik kalitga ega element tanlanadi.

2. Ushbu element birinchi element bilan o'rin almashinadi.

3. Keyin mazkur jarayon qolgan n-1, n-2 elementlar bilan takrorlanib, to bitta eng “katta” element qolguncha davom ettiriladi.

Dastur kodi:

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;

}

Algoritm samaradorligi:

• 
  Taqqoslashlar soni
  
• 
  Massiv tartiblanganda o'rinlashtirishlar soni
  
• 
  Massiv teskari tartiblanganda o'rinlashtirishlar soni
  

Ushbu usul bo'yicha saralash bajarilsa, eng yomon holda taqqoslashlar va o'rinlashtirishlar soni tartibi n2 bo'ladi.