Tanlash orqali saralash (Selection sort)
Ushbu iteratsiyada massivdagi joriy elementdan keyingi minimum elementni topamiz, zarur bo’lsa o’rin almashtiramiz. Bu holatda i-iteratsiyadan keyin I ta element o’z o’rnida joylashgan bo’ladi. Asimptotika: O(n2) yaxshi, yomon va o’rta holatda ham. Shuni ham ta’kidlash joizki, bu saralashni ikkita holatda amalga joriy qilish mumkin – minimum element va uning indeksini saqlagan holda yoki joriy elementni ko’rilayotganlar noto’g’ri o’rinda joylashgan bo’lsa ularni qayta tartibga solish orqali. Birinchi usul ancha tezkorroq bo’lganligi sababli uni amalda qo’lladik.
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;
}
swap(*i, *ind);
}
}
Do'stlaringiz bilan baham: |