|
Birlashtirish orqali saralash (Merge sort)
|
| bet | 84/143 | | Sana | 20.07.2024 | | Hajmi | 0,81 Mb. | | #268096 |
Bog'liq Tiplarni dinamik tarzda-fayllar.orgBirlashtirish 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;
}
|
|
| |
