|
Iearxik saralash (Tree sort)
|
| bet | 71/131 | | Sana | 13.05.2024 | | Hajmi | 1,83 Mb. | | #228405 |
Bog'liq Tiplarni dinamik tarzdaIearxik 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;
}
|
|
| |
