Ma’lumotlar tuzilmasi va algoritmlar fanining maqsad va vazifasini izohlab bering

36. Tez saralash usuli, uning yaratilgan davri, algoritmining yozilishi va samaradorligini tushuntirib bering.

• 
  Bu algoritm – bo’laklash usuli deb yuritiladi. 1962-yilda Charlz Xoar tomonidan taklif etilgan.
  
• 
  Bu usul “bo’laklarga bo’l va hukmronlik qil” g’oyasiga asoslangan.
  
• 
  Bu algoritmning asosiy g’oyasi almashtirish (pufak) usulidagi saralash algoritmiga mos keladi, ya’ni tanlab olingan kalitli elementga nisbatan kichik yoki teng elementlar ikki tomonga ajratib olinadi.
  

Algoritmning umumiy sxemasi

• 
  Tuzilmadan aniq qiymatga ega biror p element tanlab olish;
  
• 
  Ushbu elementga nisbatan chap tomonga “kichik yoki teng”, o’ng tomonga esa “katta yoki teng” elementlarni ajratib olish;
  
• 
  Natijada ikkita “kichiklar” va “kattalar” qismto’plami hosil bo’ladi;
  
• 
  Agar hosil qilingan qismto’plamlar 2 tadan ortiq elementlarga ega bo’lsa, u holda ushbu jarayon har bir qismto’plam uchun takrorlanadi.
  

#include

#include

int array[100000];

void tezsaralash (long h,long l)

{ long i,j; int p, temp;

i=l; j=h;

p=array[(l+h)/2];

do

{

while (array[i]

while (array[j]>p) j--;

if (i<=j)

{ temp=array[i];

array[i]=array[j];

array[j]=temp;

i++; j--;

} }

while (i<=j);

if(j>l) tezsaralash(j,l);

if(h>i) tezsaralash(h,i);

}

main()

{

int size; int i;

cin>>size;

for (i=0; i

cin>>array[i];

tezsaralash(size-1,0);

for(i=0; i

cout<

getch();

return 0;

}

37. Aralashtirib saralash usuli algoritmining ishlash printsipi, va uning dasturlash tilidagi funktsiyasi?

Bu saralash usulining asosiy g’oyasi, ikkita alohida saralangan massiv yordamida, ularni aralashtirib yuborish orqali yangi saralangan massiv hosil qilishdan iborat.

Bu algoritm quyidagi prinsip asosida ishlaydi:

1. Berilgan massiv ikkita massivga ajratib olinadi.

2. Qismmassivlarning har biri alohida saralanadi.

3. Saralangan massivlar qayta qo’shiladi.

• 
  A(6,5,1,9,3,4,8,7,2) massiv berilgan.
  

Ushbu massiv elementlarini o’rtacha qiymatining butun qismiga nisbatan ikkiga ajratamiz:

• 
  А1(5,1,3,4,2) – birinchi qismmassiv.
  
• 
  А2(6,9,8,7) – ikkinchi qismmassiv.
  

Har birini alohida saralaymiz:

• 
  А1(1,2,3,4,5) –birinchi qismmassiv.
  
• 
  А2(6,7,8,9) – ikkinchi qismmassiv.
  

A=A1+A2 yangi saralangan massiv hosil qilinadi

viod Sliv(int p,q)

{

int r,i,j,k

r=(p+q) div 2;

i=p; j=r+1;

for (k=p; k<= q; k++)

if (i<=r) and ((j>q) or (a[i]

{

b[k]=a[i]; i=i+1;

} else

{

b[k]=a[j]; j=j+1;

}

for (k=p; k<= q; k++)

a[k]=b[k];

}

void Sort(int p,q)

{

if p

{

Sort(p,(p+q) div 2);

Sort((p+q) div 2 + 1,q);

Sliv(p,q);

}

}