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