Insertion Sort(Joylab saralash)

E'tibor bering , elementni to'g'ri joyiga qo'ygandan so'ng, biz undan kattaroq barcha elementlarni bir qadam o'ngga siljitamiz.
Agar currentElement < Array[j] to'g'ri bo'lmasa, biz boshqa chapga o'tmasligimizni bildiradi, biz j bu joriy element joylashtiriladigan joy ekanligini bilamiz. Shunday qilib, biz array [j] = currentElement ni qilamiz .
Endi, agar biz elementlarni almashtirmasdan buni bajargan bo'lsak, j ga joylashtirilgan dastlabki element yo'qoladi. Shunday qilib, biz birinchi navbatda barcha j ni j+1 holatiga o'tkazamiz va keyin joriy elementni j ga joylashtiramiz .
JOYLAB SARALASH ALGORITMI
TUSHUNTIRISH:
2-qator : Biz birinchi elementni qayta ishlamaymiz, chunki uni solishtirish uchun hech narsa yo'q.
3-qator : Har bir elementni qayta ishlash uchun i=1 dan oxirigacha aylantiring.
4 -qator: i, ya'ni massiv[i] holatidagi elementni chiqarib oling . U E deb nomlansin.
5-qator : E ni chap elementlari bilan solishtirish uchun i-1 dan 0 gacha j sikli 6 , 7 qator: E ni chap element bilan solishtiring, agar E kichik bo‘lsa, [j] massivni o‘ngga suring. 1 tomonidan .
8-qator : E ning o'rnini topganimizdan so'ng , uni o'sha joyga qo'ying.
JOYLAB SARALASH ALGORITMINI AMALGA OSHIRISH
Insertion Sort(Joylab saralash uchun C# dasturi )
CHIQISH:
Joylab saralash vaqtining murakkabligi
Joylab saralash ikkita operatsiyani bajaradi : U ro'yxatni skanerlaydi, har bir juft elementni taqqoslaydi va agar ular tartibsiz bo'lsa, elementlarni siljitadi. Har bir operatsiya algoritmning ishlash vaqtiga hissa qo'shadi.
Eng yaxshi holat: O(N) . Insertion Sort uchun eng yaxshi holat massiv allaqachon tartiblangan bo'lsa sodir bo'ladi. U holda biz 1 → N dan i siklini bajaramiz. Ammo elementlarni o'zgartiradigan ichki halqa hech qachon ishlamaydi. Buning sababi shundaki, agar massiv o'sish tartibida tartiblangan bo'lsa, currentElement ning chap tomonida currentElement dan kattaroq bo'lgan arr[j] elementi bo'lmaydi. Demak , arr[j] > currentElement hech qachon to'g'ri bo'lmaydi va ichki sikl hech qachon bajarilmaydi. Shunday qilib, faqat N iteratsiya bo'ladi va vaqt murakkabligi Lineer, ya'ni O(N) bo'ladi.
Eng yomon holat massiv tartiblangan, lekin teskari tartibda bo'lsa.
Masalan, agar biz massivni o'sish tartibida tartibga solmoqchi bo'lsak, lekin berilgan kiritishda ular kamayish tartibida bo'lsa, unda bu stsenariyda eng yomon murakkablik Insertion Sortda sodir bo'ladi. Tashqi i tsikli 1 → N uchun ishlaydi va i-1 → 0 dan har bir j uchun biz bu taqqoslashlarning barchasini qilishimiz kerak, chunki har bir element teskari. Demak, har bir N - element uchun (N-1) taqqoslash amalga oshiriladi. Shunday qilib, taqqoslashlarning umumiy soni = N * (N-1) = O (N ^ 2)
KIRITISH TARTIBI ILOVALARI
1. Vaqt murakkabligi Insertion sort borish mumkin, u massivda tartiblash uchun kamroq elementlarga ega bo'lganda foydali bo'ladi.
2. Qo'shish tartibi o'z joyida algoritm bo'lib, u qo'shimcha joy talab qilmaydi.
3. Ikki teng qiymat (barqaror) bo'lsa, kiritilgan ma'lumotlarning nisbiy tartibini saqlaydi.
XULOSA
Insertion Sort oz sonli elementlar bilan yaxshi ishlaydi. Insertion Sortning eng yomon ish vaqti murakkabligi. Bubble Sort-ga o'xshaydi. Biroq, Insertion Sort pufakcha tartiblashdan yaxshiroq deb hisoblanadi.