Mavzu: Algoritmlar va ma’lumotlarning dastur bilan bog’liqligi Reja

#include

using namespace std;

int a[100001];

void qsort(int L, int R) {

int m = (L+R) / 2;

int X = a[m];

int i = L;

int j = R;

while (i <= j) {

while (a[i] < X) i++;

while (a[j] > X) j--;

if (i <= j) {

int t = a[i]; a[i] = a[j]; a[j] = t;

i++;

j--;

}

}

if (L < j) qsort(L, j);

if (i < R) qsort(i, R);

}

Dasturning asosiy qismida esa:

• 
  int main() {
  
• 
  int n;
  
• 
  cin>>n;
  
• 
  for (int i = 0; i < n; i++)
  
• 
  cin>>a[i];
  
• 
  qsort(0, n-1);
  
• 
  for (int i = 0; i < n; i++)
  
• 
  cout<
• 
  return 0;
  
• 
  }
  

C++ dasturlash tilida saralash juda oddiy. Unga Quick Sort algoritmi kiritilgan va unga murojat etish uchun sort() funksiyasiga murojaat etamiz:

• 
  #include
  
• 
  #include
  
• 
  using namespace std;
  
• 
  int main() {
  
• 
  int n;
  
• 
  cin>>n;
  
• 
  int a[n];
  
• 
  for (int i = 0; i < n; i++)
  
• 
  cin>>a[i];
  
• 
  sort(a, a+n);
  
• 
  for (int i = 0; i < n; i++)
  
• 
  cout<
• 
  return 0;
  
• 
  }
  

Quick sort algoritmining qo’llanilishi
Quick sort algoritmining faqatgina saralash uchun emas boshqa bir narsani hisoblash uchun ham qo’llaniladi.
Quick sort(Tezkor saralash) algoritmining ajoyib qo’llanilishi bu massivdagi k-tartibli qiy-matni topish, ya’ni massiv saralangan vaqtda k-o’rinda turadigan elementning qiymatini topish. Agar avval massivni to’liq saralab keyin k-indeksdagi qiymatini chiqarsak u holda ishlash vaqtu n∙log(n) bo’ladi. Lekin quick sort orqali u O(n) vaqtda topiladi. n=10⁷ bo’lgan paytda n∙log(n) ≈ 232,534,966 bo’ladi.

• 
  Asosiy ideasi:
  
• 
  Quick sort algoritmi orqali saralashda bo’luvchi element tanlanadi va undan kichiklari bir tamon [L, j] oraliqda, kattalari ikkinchi tamon[I, R] oraliqda va [j+1, i-1] oraliqda bir xil sonlar joylashishi mumkin.
  
• 
  Dastlab [j+1, i-1] tegishliligini tekshiramiz, Agar unga tegishli bo’lsa demak unga mos o’rindagi qiymatni chiqarib qo’yaveramiz. Agar [L, j] intervalga tegishli bo’lsa k ni o’zgartirmasdan shu qism bo’yicha izlashni davom ettiramiz. Agar [i, R] intervalga tegishli.
  
• 
  Bo’lsa shu qism orqali davom ettiramiz, lekin bu intervalda k-son emas undan kichikroq son kerak bo’ladi, ya’ni tashlab yuborilgan qism uzunligini ayiramiz.