2. Minimal element massiv boshiga, maksimal element esa massiv oxiriga mos ravishda joylashtiriladi.
3. Algoritm qolgan elementlar qismmassivida ham ushbu amalni takrorlaydi.
void Sort(int col)
{ int trash=0; bool f=true;
for (int i=1; (i<=col) && (f=true) ; i++)
{ f=false; // chapdan o’ngga o’tish
for (int j=i; j<=col-i; j++)
{ if (array [j]>array [j+1])
{ trash=array[j]; array [j]=array [j+1];
array [j+1]=trash; f=true; } }
// o’ngdan chapga o’tish
for (int j=col-i-1; j>i ; j--) {
if (array [j]array [j-1]=trash; f=true; } } } }
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; icin>>array[i];
tezsaralash(size-1,0);
for(i=0; icoutreturn 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.
|
