|
Algoritmning umumiy sxemasi
|
| bet | 18/71 | | Sana | 18.12.2023 | | Hajmi | 5,63 Mb. | | #122750 |
Bog'liq Test gift and xml-fayllar.orgAlgoritmning 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);
}
}
|
| |
