Javoblar 86. Хасис алгоритм қачон қўлланилади?

92.Quicksort алгоритмини тушунтиринг.

Quiksort – тез саралаш алгоритмлари.

QuickSort яъни тез саралаш – Чарлз Хоар томонидан яратилган машхур сарааш алгоритмидир. Ушбу алгоритм n та элементдан иборат массивни энг узоги билан O(n²) вактда саралайди. Лекин бажарилиш тезлигининг математик кутилмаси O(n log n) га тенг ва у бошка шундай тезликда бадарилувчи алгоритмлардан тезрок ишлайди.

Ишлаш присипи:

• 
  Массивда ихтийорий таянч элемент талаймиз
  
• 
  Кейин ундан кичик йоки тенг элементларни унинг чап томонига, катталарини унг томонига утказамиз.
  
• 
  1-2 кадамларни таянч элементнинг унг ва чап томонларидаги элементлар учун куллаймиз
  

Айни шу 2-кадамда элементларни жойлаштириш алгоритми туфайли у саралаш алгоритмлари ичида енг тез ишлайдиганларидан биридир.

#include

#include

using namespace std;

int partition(int *a,int start,int end)

{

int pivot=a[end];

int P_index=start; //P-index sikldagi qiymat indexsi uchun

int i,t; //t vaqtinchalik o'zgaruvchi

for(i=start;i

{

if(a[i]<=pivot)

{

t=a[i];

a[i]=a[P_index];

a[P_index]=t;

P_index++;

}

}

//o'rin almasshtirish uchun

t=a[end];

a[end]=a[P_index];

a[P_index]=t;

return P_index;

}

void Quicksort(int *a,int start,int end)

{

if(start

{

int P_index=partition(a,start,end);

Quicksort(a,start,P_index-1);

Quicksort(a,P_index+1,end);

}

}

int main()

{

cout<<"\n\t\tAkramov Umarbek CAL006 guruh"<

int n;

cout<<"Neshta element kiritmoqchisiz: ";

cin>>n;

int a[n];

cout<<"\nAralash tartibda raqamlarni kiriting:\n";

for(int i=0;i

{

cin>>a[i];

}

Quicksort(a,0,n-1);

cout<<"\nQuickSort saralab bergan holati:\n";

for(int i=0;i

{

cout<

}

return 0;

}



1-расм. QuickSort дастур натижаси.