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

Tezkor qidiruv (Quicksort)

Qandaydir tayanch element tanlab olinadi. Shundan so’ng undan kichik elementlarni chapga joylaymiz, kattalarini esa o’ngga. Rekursiv ravishda har bir qismga murojaat qilamiz. Tayanch elementdan har bir kichik element oldin tayanch elementdan kattalaridan oldin turardi. Asimptorika: O(nlogn) o’rta va O(n²) yaxshi holatda. Yomon holat massivning tayanch elementi omadsiz holatda tanlanadi. Bu algoritmning quyida standart holini ko’rib chiqamiz, bir vaqtning o’zida chapdan va o’ngdan ikkita element topamiz. Chapdagi element tayanch elementdan katta, o’ngdagisi kichik bo’lishi lozim va ularni o’rinlarini almashtiramiz. Bundan tashqari, aniq tezkor saralashda qo’yish orqali saralashning kam sondagi elementlari ustida taqqoslash va saralash amallari qatnashgan. Konstanta testlash orqali tanlab olingan, qo’yish orqali saralash esa ushbu masalani yechish uchun mos keluvchi eng munosib saralashdir (bu holdan uni kvadratik saralashlardan afzal deb hisoblash kerak emas).

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

}

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

}