Qo‘yib saralash (insertion sort)
Kiritish tartibi
Insertion Sort algoritmi tartiblangan qiymatlarni saqlash uchun massivning bir qismidan, hali tartiblanmagan qiymatlarni saqlash uchun massivning boshqa qismidan foydalanadi.
{{ msgDone }}
Algoritm massivning saralanmagan qismidan bir vaqtning o‘zida bitta qiymatni oladi va massiv tartiblashtirilguncha uni massivning tartiblangan qismidagi kerakli joyga qo‘yadi.
Qanday ishlaydi:
- Massivning tartiblanmagan qismidan birinchi qiymatni oling.
- Qiymatni massivning tartiblangan qismidagi to‘g‘ri joyga ko‘chiring.
- Massivning saralanmagan qismidan qancha qiymatlar bo‘lsa, shuncha marta o‘ting.
Qo‘lda yugurish
Python dasturida Insertion Sort algoritmini qo‘llashdan oldin, keling, qisqa massivni qo‘lda bajaramiz, shunchaki fikrni tushunish uchun.
1-qadam: Biz tartiblanmagan massivdan boshlaymiz.
[ 7, 12, 9, 11, 3]
2-qadam: Biz birinchi qiymatni massivning dastlabki tartiblangan qismi deb hisoblashimiz mumkin. Agar u faqat bitta qiymat bo‘lsa, uni tartiblash kerak, to‘g‘rimi?
[ 7, 12, 9, 11, 3]
3-qadam: Keyingi qiymat 12 endi massivning tartiblangan qismidagi to‘g‘ri joyga ko‘chirilishi kerak. Ammo 12 7 dan yuqori, shuning uchun u allaqachon to‘g‘ri holatda.
[ 7, 12, 9, 11, 3]
4-qadam: Keyingi qiymatni ko‘rib chiqing 9.
[ 7, 12, 9, 11, 3]
5-qadam: Endi 9 qiymati massivning tartiblangan qismi ichida to‘g‘ri joyga ko‘chirilishi kerak, shuning uchun biz 9 ni 7 va 12 oralig‘ida siljitamiz.
[ 7, 9, 12, 11, 3]
6-qadam: Keyingi qiymat 11.
[ 7, 9, 12, > 11, 3]
7-qadam: Biz uni massivning tartiblangan qismida 9 dan 12 gacha o‘tkazamiz.
[ 7, 9, 11, 12, 3]
8-qadam: To‘g‘ri joyga kiritish uchun oxirgi qiymat 3.
[ 7, 9, 11, 12, 3]
9-qadam: Biz boshqa barcha qiymatlar oldiga 3 ni kiritamiz, chunki u eng past qiymatdir.
[ 3,7, 9, 11, 12]
Nihoyat, massiv tartiblangan.
Yuqoridagi animatsiyali qadamlarni ko‘rish uchun quyidagi simulyatsiyani bajaring:
Python-da qo‘shish tartibini amalga oshirish
Python dasturida Insertion Sort algoritmini amalga oshirish uchun bizga kerak:
- Saralash uchun qiymatlari bo‘lgan massiv.
- Saralash uchun qiymatni tanlaydigan tashqi sikl. \(n\) qiymatlari bo‘lgan massiv uchun bu tashqi sikl birinchi qiymatni o‘tkazib yuboradi va \(n-1\) marta ishlashi kerak.
- Qiymatni qaerga kiritish kerakligini topish uchun massivning tartiblangan qismidan o‘tuvchi ichki sikl. Agar saralanadigan qiymat \(i\) indeksida bo‘lsa, massivning tartiblangan qismi \(0\) indeksidan boshlanib, \(i-1\) indeksida tugaydi.
Olingan kod quyidagicha ko‘rinadi:
Misol
Python ro‘yxatida Insertion Sortdan foydalanish:
mylist = [64, 34, 25, 12, 22, 11, 90, 5]
n = len(mylist)
for i in range(1,n):
insert_index = i
current_value = mylist.pop(i)
for j in range(i-1, -1, -1):
if mylist[j] > current_value:
insert_index = j
mylist.insert(insert_index, current_value)
print(mylist)
Misolni ishga tushirish »
Qo‘shish tartibini yaxshilash
Qo‘shish tartibini biroz yaxshilash mumkin.
Yuqoridagi kod avval qiymatni olib tashlab, keyin uni boshqa joyga kiritish usuli intuitivdir. Masalan, qo‘lda kartalar yordamida Insertion Sort-ni shunday qilishingiz mumkin. Agar past qiymatli kartalar chap tomonga saralangan bo‘lsa, siz yangi saralanmagan kartani olasiz va uni boshqa tartiblangan kartalar orasiga to‘g‘ri joylashtirasiz.
Dasturlashning bu usuli bilan bog‘liq muammo shundaki, qiymatni massivdan olib tashlashda yuqoridagi barcha elementlarni bir indeks o‘ringa pastga siljitish kerak:
O‘chirilgan qiymatni massivga qayta kiritishda ham bajarilishi kerak bo‘lgan ko‘plab siljish operatsiyalari mavjud: kiritilgan qiymat uchun joy ochish uchun quyidagi barcha elementlar bir pozitsiyani yuqoriga siljitishi kerak:
Ushbu siljish operatsiyalari ko‘p vaqt talab qilishi mumkin, ayniqsa ko‘p elementlarga ega massiv uchun.
Yashirin xotira siljishlari: Agar siz Python yoki JavaScript kabi yuqori darajadagi dasturlash tilidan foydalanayotgan bo‘lsangiz, kodda bu o‘zgartirish operatsiyalarini ko‘rmaysiz, lekin o‘zgartirish operatsiyalari hali ham fonda amalga oshirilmoqda. Bunday o‘zgartirish operatsiyalari kompyuter uchun qo‘shimcha vaqt talab qiladi, bu muammo bo‘lishi mumkin.
Massivlar xotirada qanday saqlanishi haqida ko‘proq ma’lumotni bu yerda o‘qishingiz mumkin.
Yaxshilangan yechim
Biz faqat kerakli qiymatlarni o‘zgartirish orqali ushbu siljish operatsiyalarining aksariyatidan qochishimiz mumkin:
Yuqoridagi rasmda birinchi qiymat 7 ko‘chiriladi, so‘ngra 11 va 12 qiymatlari massivda bir o‘ringa yuqoriga siljiydi va oxirgi qiymatda 7 qiymati 11 oldingi qiymatga qo‘yiladi.
Bu holda o‘zgartirish operatsiyalari soni 12 dan 2 gacha kamayadi.
Ushbu takomillashtirish quyidagi misolda amalga oshiriladi:
Misol
Saralash algoritmiga yaxshilanishlarni kiriting:
mylist = [64, 34, 25, 12, 22, 11, 90, 5]
n = len(mylist)
for i in range(1,n):
insert_index = i
current_value = mylist[i]
for j in range(i-1, -1, -1):
if mylist[j] > current_value:
mylist[j+1] = mylist[j]
insert_index = j
else:
break
mylist[insert_index] = current_value
print(mylist)
Misolni ishga tushirish »
Yuqoridagi kodda ham bajarilgan narsa ichki pastadirdan chiqishdir. Buning sababi, agar biz joriy qiymat uchun to‘g‘ri joyni topib olgan bo‘lsak, qiymatlarni taqqoslashni davom ettirishning hojati yo‘q.
Qo‘shishni saralash vaqtining murakkabligi
Insertion Sort \(n\) qiymatlar massivini tartiblaydi.
O‘rtacha har bir qiymatni kiritish uchun to‘g‘ri joyni topish uchun taxminan \(\frac{n}{2}\) boshqa qiymatlar bilan solishtirish kerak.
Qiymatni to‘g‘ri joyga kiritish uchun “Qo‘shish saralash” siklini taxminan \(n\) marta bajarishi kerak.
Insertion Sort uchun vaqt murakkabligini olamiz: \( O( \frac{n}{2} \cdot n) = {O(n^2)} \)
Insertion Sort uchun vaqt murakkabligi quyidagicha ko‘rsatilishi mumkin:
Insertion Sort uchun eng yaxshi, o‘rtacha va eng yomon stsenariylar o‘rtasida katta farq bor.
Keyingi - Quicksort. Nihoyat, biz tezroq saralash algoritmini ko‘ramiz!
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!