Insertion Sort(Joylab saralash)

Insertion sort (Joylab saralash) algoritmi
Insertion Sort - eng oddiy saralash usullaridan biri bo'lib, siz kundalik hayotingizda kartalar to'plamini joylashtirishda foydalangan bo'lishingiz mumkin.
Shunday qilib, ushbu algoritm qanday ishlashini ko'rib chiqmasdan, keling, kartalar to'plamini qanday tartibga solish haqida o'ylab ko'raylik? Aytaylik, sizga 10 ta karta, 1 dan 10 gacha berilgan, hammasi aralashtiriladi va siz bu kartalarni saralashni xohlaysiz.
Siz har qanday tasodifiy kartani (masalan, 7) tanlaysiz va chap qo'lingiz saralangan kartalarni olib yurish uchun mo'ljallangan deb o'ylab, uni chap qo'lingizga joylashtirasiz. Keyin siz boshqa tasodifiy kartani tanlaysiz, aytaylik 2, 2 ni chap qo'lingizning to'g'ri joyiga, ya'ni 7 dan oldin qo'ying.
Agar siz endi 5 ni tanlasangiz, uni chap qo'lingizga 2 dan keyin, 7 dan oldin qo'ygan bo'lasiz va shu tariqa biz kartalar to'plamini saralashimiz mumkinligini bilamiz. Biz bir vaqtning o'zida bitta elementni to'g'ri joyga joylashtirganimiz uchun uning nomi " Joylab saralash " deb ataladi.
Xuddi shu fikrni ko’rib chiqsak, keling, uni kompyuterlarimizga etkazib berish usulini shakllantirishga harakat qilaylik. Biz bir vaqtning o'zida bitta elementni tanlaymiz, uni bir tomonidagi (masalan, chap) barcha elementlar bilan taqqoslaymiz va uni to'g'ri joyga joylashtiramiz.
Masalan: Agar elementlar quyidagi tartibda bo'lsa: 5, 9, 1
Siz 5 ni tanlash bilan boshlashingiz mumkin va 5 ning chap tomonida hech qanday element yo'qligi sababli, biz uni to'g'ri joyda deb taxmin qilishimiz mumkin.
Massiv: 5, 9, 1
Siz 5 ni tanlashingiz mumkin, siz 5 ni 9 bilan solishtirasiz va 5, M [5, 9 ] massivida to'g'ri tartibda ekanligini topasiz . Massiv: 5, 9, 1.
Keyin siz 1 ni tanlaysiz, [5,9] ning chap tomonidagi massivda shu 1 ni joylashtirish uchun joyni topasiz . 1 5 dan oldin kelishi kerakligi sababli 5 dan oldin 1 ni kiritamiz .
Massiv: 1, 5, 9 → Bu tartiblangan massiv.