8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja


Birlashtirish orqali saralash (Merge sort)


Download 231.37 Kb.
bet7/16
Sana31.03.2023
Hajmi231.37 Kb.
#1312800
1   2   3   4   5   6   7   8   9   10   ...   16
Bog'liq
8-maruza (2)

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


Download 231.37 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   10   ...   16




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling