Javoblar 86. Хасис алгоритм қачон қўлланилади?

Sheyker saralash (Shaker sort)

Sheyker sort aralash yoki kokteyl saralash deb ham yuritiladi. Ma’lumki, pufakchali saralash eng kichik element massiv oxirida joylashgan holatda testlanganda sekin ishlaydi(ularni “toshbaqalar” deb yuritadilar). Bunda element har bir qadamda atigi bitta pozitsiyaga chapga suriladi. Shu sababdan faqat chapdan o’ngga emas balki o’ngdan chapga ham yurish amalga oshiramiz. Ikkita begin va end ko’rsatkichlarini olamiz, bu bizga massivning qaysi bo’lagi saralanmaganini anglatadi. Keying iteratsiyada end ga yetib borganda undan birni ayiramiz va o’ngdan chapga qarab yuramiz, analog holda begin ga yetib borganda bitta oshiramiz va yana chapdan o’ngga yurishda davom etamiz. Algoritmning asimptotikasi ham huddi pufakcha saralashi kabidir, lekin ishlash vaqti anchayin yaxshiroq.

void shakersort(int* l, int* r)

{

int sz = r - l;

if (sz <= 1) return;

bool b = true;

int* beg = l - 1;

int* end = r - 1;

while (b)

{

b = false;

beg++;

for (int* i = beg; i < end; i++)

{

if (*i > *(i + 1))

{

swap(*i, *(i + 1));

b = true;

}

}

if (!b) break;

end--;

for (int* i = end; i > beg; i--)

{

if (*i < *(i - 1))

{

swap(*i, *(i - 1));

b = true;

}

}

}

}