8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja

Iearxik saralash (Tree sort). Binar qidiruv iearxiyasiga elementlarni kiritamiz. Barcha elementlar kiritilgandan so‘ng, iearxiyadan tartiblangan massiv olish kifoya. Agar siz qizil-qora kabi muvozanatli iearxiyadan foydalansangiz, murakkabligi eng yomon, o‘rtacha va eng yaxshi holatlarda O(nlogn). Amalga oshirishda multiset konteyner foydalanadi.
8.6-dastur. Saralashni amalga oshirish.
void treesort(int* l, int* r) { multiset m;
for (int *i = l; i < r; i++) m.insert(*i);
for (int q : m)
*l = q, l++;
}
Nav saralash (Gnome sort). Algoritm qo‘shish orqali saralashga o‘xshash. Ko‘rsatgichni joriy elementga ko‘rsatamiz, agar u avvalgisidan katta bo‘lsa yoki u birinchi bo‘lsa ko‘rsatgichni to‘g‘ri holatga ko‘chiramiz, aks holda joriy va oldingi elementlarni o‘zgartiramiz va chap tomonga harakatlantiramiz.
8.7-dastur. Saralashni amalga oshirish.
void gnomesort(int* l, int* r) { int *i = l;
while (i < r) {
if (i == l || *(i - 1) <= *i) i++; else swap(*(i - 1), *i), i--;
}
}
Tanlash orqali saralash (Selection sort). Navbatdagi iterasiya bo‘yicha massivdagi minimumni joriy elementdan keyin topamiz va kerak bo‘lsa u bilan o‘zgartiramiz. Shunday qilib, i-iterasiyadan keyin birinchi i elementlar o‘z joylarida qoladi. murakkabligi eng yaxshi, o‘rtacha va eng yomon holatlarda O(n²). Bu saralashni ikki yo‘l bilan amalga oshirilishi mumkinligini unutmang - minimal va uning indeks tutib, yoki shunchaki ular noto‘g‘ri tartibda bo‘lsa, ko‘rib chiqilayotgan va joriy element o‘rin almashtirish kerak. Birinchi usul bir oz tezroq.
8.8-dastur. Saralashni amalga oshirish.
void selectionsort(int* l, int* r) { for (int *i = l; i < r; i++) {
int minz = *i, *ind = i;
for (int *j = i + 1; j < r; j++) {
if (*j < minz) minz = *j, ind = j;
}
Piramida kabi saralash (Heapsort). Tanlash orqali saralash g‘oyasini rivojlantirilgan varianti. Piramida shaklidagi maʻlumot strukturasidan foydalanaylik. Elementlarni qo‘shish va minimumini chiqarish orqali O(logn), O(1) minimumini olish imkonini beradi. Shunday qilib, O(nlogn) murakkabligi eng yomon, o‘rtacha va eng yaxshi holatlarda. C++ da priority_queue konteyneri mavjud bo‘lsa-da, bu konteyner juda sekin bo‘lgani uchun Piramidaga yo‘natirilgan yangi to‘plam sinfni amalga oshirdim.
8.9-dastur. Saralashni amalga oshirish.
Heap sinfi
template class heap { private :
vector h;
void SiftUp(int a) {
while (a) {
int p = (a - 1) / 2;
if (h[p] > h[a]) swap(h[p], h[a]); else break;
a--; a /= 2;
}
}
void SiftDown(int a) {
while (2 * a + 1 < n) {
int l = 2 * a + 1, r = 2 * a + 2; if (r == n) {
if (h[l] < h[a]) swap(h[l], h[a]); break;
}
else if (h[l] <= h[r]) {
if (h[l] < h[a]) {
swap(h[l], h[a]); a = l;
}
else break;
}
else if (h[r] < h[a]) {
swap(h[r], h[a]); a = r;
}
else break;
}
}
public:
heap():n(0){} int n;
int size() {
return n;
}
int top() {
return h[0];
}
bool empty() {
return n == 0;
}
void push(T a) {
h.push_back(a); SiftUp(n);
n++;
}
void pop() {
n--;
swap(h[n], h[0]); h.pop_back(); SiftDown(0);
}
void clear() {
h.clear(); n = 0;
}
T operator [] (int a) { return h[a];
}
};
Heap cinfi aosida saralash
void heapsort(int* l, int* r) { heap h;
for (int *i = l; i < r; i++) h.push(*i);
for (int *i = l; i < r; i++) {
*i = h.top();
h.pop();
}
}