8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja

Birlashtirish orqali saralash (Merge sort). Bo‘lish-boshqarish paradigmasi asosida tartiblash. Massivni ikkiga bo‘lamiz, qismlarni rekursiv ravishda tartiblang va keyin birlashtirish protsedurasini bajaring. Birinchi qismning joriy elementiga, ikkinchisi ikkinchi qismning joriy elementiga ikkita ko‘rsatkichni qo‘llang. Bu ikki elementdan minimumni tanlab, javobga joylashtiring va minimumga mos keladigan ko‘rsatgichni siljiting. Birlashtirish O(n), barcha logn darajalari uchun ishlaydi, shuning uchun murakkabligi O(nlogn). Bu oldindan vaqtinchalik masiv yaratish va vazifaga argument sifatida o‘tishi samarali bo‘ladi. Bu saralash rekursiv, hamda tez va shuning uchun elementlar soni kam bo‘lgan kvadratik o‘tish mumkin.
8.11-dastur. Saralashni amalga oshirish.

Asosiy funksiya

void merge(int* l, int* m, int* r, int* temp) { int *cl = l, *cr = m, cur = 0; while (cl < m && cr < r) { if (*cl < *cr) temp[cur++] = *cl, cl++; else temp[cur++] = *cr, cr++;

} while (cl < m) temp[cur++] = *cl, cl++; while (cr < r) temp[cur++] = *cr, cr++; cur = 0; for (int* i = l; i < r; i++) *i = temp[cur++]; }

Birinchi varinat

void _mergesort(int* l, int* r, int* temp) { if (r - l <= 1) return; int *m = l + (r - l) / 2; _mergesort(l, m, temp); _mergesort(m, r, temp); merge(l, m, r, temp); } void mergesort(int* l, int* r) { int* temp = new int[r - l]; _mergesort(l, r, temp); delete temp; }

Ikkinchi varinat void _mergeinssort(int* l, int* r, int* temp) { if (r - l <= 32) { insertionsort(l, r); return; } int *m = l + (r - l) / 2; _mergeinssort(l, m, temp); _mergeinssort(m, r, temp); merge(l, m, r, temp); } void mergeinssort(int* l, int* r) { int* temp = new int[r - l]; _mergeinssort(l, r, temp); delete temp; }