|
Tiplarni dinamik tarzda aniqlash. Reja: Tiplarni dinamik tarzda aniqlash
|
| bet | 82/143 | | Sana | 20.07.2024 | | Hajmi | 0,81 Mb. | | #268096 |
Bog'liq Tiplarni dinamik tarzda-fayllar.orgIearxik 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(n2). 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;
}
|
|
| |
