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();
}
}
|
Tezkor saralash (quicksort). Baʻzi mos yozuvlar elementini tanlaylik. Shundan so‘ng chapdan kichik bo‘lgan barcha elementlarni, katta bo‘lganlarini esa o‘ng tomonga harakatlantiramiz. Takrorlanuvchi qismlarning har biridan rekursiv chaqirish mumkin. Natijada tartiblangan massivga ega bo‘lamiz, chunki har bir katta elementdan oldin massivdan kichik bo‘lgan har bir element joylashtirilgan. Murakkabligi: O(nlogn) o‘rtacha va eng yaxshi holda, O (n2) eng yomon holda. Malumot elementi noto‘g‘ri tanlanganda eng yomon reytingga erishiladi. Bu algoritmni amalga oshirish butunlay standart hisoblanadi, bir vaqtning o‘zida chapga va o‘ngga borib, elementlarni juft topish, bunda chap element mos yozuvlari tanlangandan katta ekanligini va o‘ng kichik, ular almashtiriladi. Sof tezkor tartiblashdan tashqari, elementlar soni kam bo‘lganda tartiblashni joylashtirishga, taqqoslashda ham saralash ishtirok etdi. Qo‘shish orqali saralash vazifa uchun mos bo‘lgan eng yaxshi saralashdir va doimiy sinov orqali tanlanadi.
8.10-dastur. Saralashni amalga oshirish.
Birinchi variant
|
void quicksort(int* l, int* r) { if (r - l <= 1) return; int z = *(l + (r - l) / 2); int* ll = l, *rr = r - 1; while (ll <= rr) {
while (*ll < z) ll++; while (*rr > z) rr--; if (ll <= rr) {
swap(*ll, *rr); ll++;
rr--;
}
}
if (l < rr) quicksort(l, rr + 1); if (ll < r) quicksort(ll, r);
}
|
Ikkinchi variant
|
void quickinssort(int* l, int* r) { if (r - l <= 32) {
insertionsort(l, r); return;
}
int z = *(l + (r - l) / 2); int* ll = l, *rr = r - 1; while (ll <= rr) {
while (*ll < z) ll++; while (*rr > z) rr--; if (ll <= rr) {
swap(*ll, *rr); ll++;
rr--;
}
}
if (l < rr) quickinssort(l, rr + 1); if (ll < r) quickinssort(ll, r);
}
|
Do'stlaringiz bilan baham: |
