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



Yüklə 0,53 Mb.
səhifə5/13
tarix02.12.2023
ölçüsü0,53 Mb.
#137210
1   2   3   4   5   6   7   8   9   ...   13
4.2-ma\'ruza

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


    Yüklə 0,53 Mb.

    Dostları ilə paylaş:
  • 1   2   3   4   5   6   7   8   9   ...   13




    Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
    rəhbərliyinə müraciət

    gir | qeydiyyatdan keç
        Ana səhifə


    yükləyin