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

Qo’yish orqali saralash (Insertion sort)

Algoritm tugagandan so’ng natijalar joylanadigan massiv yaratamiz. Elementlarni navbat bilan natijaviy massivga shunday joylaymizki, oxirida massiv saralangan holatda bo’lishi lozim. Asimptotika o’rta va yomon holda O(n²) ga, yaxshi holda esa O(n) ga teng bo’ladi. Algoritmni boshqacharoq usulda amalga oshirish qulayroq (yangi massiv yaratish va unga haqiqatdan biron elementni joylash nisbatan murakkabroq): kirish massivining prefiksini tartiblashni amalga oshiramiz, qo’yishni o’rniga joriy elementni oldingisi bilan (agar u noto’g’ri joyda turgan bo’lsa) almashtirishni amalga oshiramiz.

void insertionsort(int* l, int* r)

{

for (int *i = l + 1; i < r; i++)

{

int* j = i;

while (j > l && *(j - 1) > *j)

{

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

j--;

}

}

}