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=107 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.