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;
}
