8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja

Tezkor saralash (quicksort). Baʻzi mos yozuvlar elementini tanlaylik. Shundan so‘ng chapdan kichik bo‘lgan barcha elementlarni, katta bo‘lganlarini esa o‘ng tomonga harakatlantiramiz. Takrorlanuvchi qismlarning har biridan rekursiv chaqirish mumkin. Natijada tartiblangan massivga ega bo‘lamiz, chunki har bir katta elementdan oldin massivdan kichik bo‘lgan har bir element joylashtirilgan. Murakkabligi: O(nlogn) o‘rtacha va eng yaxshi holda, O (n²) eng yomon holda. Malumot elementi noto‘g‘ri tanlanganda eng yomon reytingga erishiladi. Bu algoritmni amalga oshirish butunlay standart hisoblanadi, bir vaqtning o‘zida chapga va o‘ngga borib, elementlarni juft topish, bunda chap element mos yozuvlari tanlangandan katta ekanligini va o‘ng kichik, ular almashtiriladi. Sof tezkor tartiblashdan tashqari, elementlar soni kam bo‘lganda tartiblashni joylashtirishga, taqqoslashda ham saralash ishtirok etdi. Qo‘shish orqali saralash vazifa uchun mos bo‘lgan eng yaxshi saralashdir va doimiy sinov orqali tanlanadi.
8.10-dastur. Saralashni amalga oshirish.
Birinchi variant
void quicksort(int* l, int* r) { if (r - l <= 1) return; int z = *(l + (r - l) / 2); int* ll = l, *rr = r - 1; while (ll <= rr) {
while (*ll < z) ll++; while (*rr > z) rr--; if (ll <= rr) {
swap(*ll, *rr); ll++;
rr--;
}
}
if (l < rr) quicksort(l, rr + 1); if (ll < r) quicksort(ll, r);
}
Ikkinchi variant
void quickinssort(int* l, int* r) { if (r - l <= 32) {
insertionsort(l, r); return;
}
int z = *(l + (r - l) / 2); int* ll = l, *rr = r - 1; while (ll <= rr) {
while (*ll < z) ll++; while (*rr > z) rr--; if (ll <= rr) {
swap(*ll, *rr); ll++;
rr--;
}
}
if (l < rr) quickinssort(l, rr + 1); if (ll < r) quickinssort(ll, r);
}
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;
}