8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja


Piramida kabi saralash (Heapsort)


Download 231.37 Kb.
bet5/16
Sana31.03.2023
Hajmi231.37 Kb.
#1312800
1   2   3   4   5   6   7   8   9   ...   16
Bog'liq
8-maruza (2)

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


Download 231.37 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   ...   16




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling