Tanlab saralash (selection sort)
Tanlash saralash
Tanlovni saralash algoritmi massivdagi eng past qiymatni topadi va uni massivning old qismiga o‘tkazadi.
{{ msgDone }}
Algoritm massivni qayta-qayta ko‘rib chiqadi va massiv tartiblashtirilguncha keyingi eng past qiymatlarni old tomonga o‘tkazadi.
Qanday ishlaydi:
- Eng past qiymatni topish uchun massivdan o‘ting.
- Eng past qiymatni massivning tartiblanmagan qismining old tomoniga o‘tkazing.
- Massivda qancha qiymatlar mavjud bo‘lsa, shuncha marta massivdan o‘ting.
Qo‘lda yugurish
Python dasturida Tanlovni saralash algoritmini qo‘llashdan oldin, keling, qisqa massivni faqat bir marta qo‘lda bajaramiz, shunchaki fikrni tushunish uchun.
1-qadam: Biz tartiblanmagan massivdan boshlaymiz.
[ 7, 12, 9, 11, 3]
2-qadam: Massivni bir vaqtning o‘zida bitta qiymatdan o‘tkazing. Qaysi qiymat eng past? 3, to‘g‘rimi?
[ 7, 12, 9, 11, 3]
3-qadam: Eng past qiymat 3 ni massivning old tomoniga o‘tkazing.
[ 3, 7, 12, 9, 11]
4-qadam: 7 dan boshlab qolgan qiymatlarni ko‘rib chiqing. 7 eng past qiymat va massivning old tomonida joylashgan, shuning uchun uni ko‘chirishimiz shart emas.
[ 3, 7, 12, 9, 11]
5-qadam: Massivning qolgan qismini ko‘rib chiqing: 12, 9 va 11. 9 - eng past qiymat.
[ 3, 7, 12, 9, 11]
6-qadam: 9-ni old tomonga o‘tkazing.
[ 3, 7, 9, 12, 11]
7-qadam: 12 va 11 ga qaraganda, 11 eng past.
[ 3, 7, 9, 12, 11]
8-qadam: Uni old tomonga o‘tkazing.
[ 3, 7, 9, 11, 12]
Nihoyat, massiv tartiblangan.
Yuqoridagi animatsiyali qadamlarni ko‘rish uchun quyidagi simulyatsiyani bajaring:
Python-da tanlashni saralash
Python-da tanlashni saralash algoritmini amalga oshirish uchun bizga kerak:
- Saralash uchun qiymatlari bo‘lgan massiv.
- Massiv bo‘ylab o‘tadigan, eng past qiymatni topadigan va uni massivning old qismiga o‘tkazadigan ichki sikl. Bu sikl har safar ishlaganda bir kam qiymatdan o‘tishi kerak.
- Ichki pastadir necha marta ishlashi kerakligini boshqaradigan tashqi sikl. \(n\) qiymatli massiv uchun bu tashqi sikl \(n-1\) marta ishlashi kerak.
Olingan kod quyidagicha ko‘rinadi:
Misol
Python ro‘yxatida Tanlash tartibidan foydalanish:
mylist = [64, 34, 25, 5, 22, 11, 90, 12]
n = len(mylist)
for i in range(n-1):
min_index = i
for j in range(i+1, n):
if mylist[j] < mylist[min_index]:
min_index = j
min_value = mylist.pop(min_index)
mylist.insert(i, min_value)
print(mylist)
Misolni ishga tushirish »
Tanlovni saralash bilan bog‘liq muammo
Tanlovni saralash algoritmi biroz yaxshilanishi mumkin.
Yuqoridagi kodda eng past qiymat elementi olib tashlanadi va keyin massivning oldiga kiritiladi.
Har safar eng past qiymatli massivning keyingi elementi olib tashlanganida, olib tashlashning o‘rnini bosish uchun barcha keyingi elementlarni bir joyga pastga siljitish kerak.
Bu almashtirish operatsiyalari ko‘p vaqtni oladi va biz hali tugatmadik! Eng past qiymat (5) topilgandan va olib tashlangandan so‘ng, u massivning boshiga kiritiladi, bu quyidagi rasmda ko‘rsatilganidek, yangi qiymat uchun joy ochish uchun barcha keyingi qiymatlarni bir pozitsiya yuqoriga siljitadi.
Eslatma: Agar siz Python yoki Java 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.
Yechim: qiymatlarni almashtiring!
Barcha siljishlar o‘rniga eng past qiymatni (5) birinchi qiymatga (64) quyida bo‘lgani kabi almashtiring.
Yuqoridagi rasmdagi kabi qiymatlarni almashtirishimiz mumkin, chunki eng past qiymat to‘g‘ri holatda tugaydi va biz almashtirayotgan boshqa qiymatni qaerga qo‘yishimiz muhim emas, chunki u hali tartiblanmagan.
Mana, almashtirish bilan yaxshilangan Tanlash tartibi qanday ishlashini ko‘rsatadigan simulyatsiya:
{{ msgDone }}
Tanlovni saralash algoritmiga yaxshilanishni kiritamiz:
Misol
Yaxshilangan Tanlovni Saralash algoritmi, shu jumladan qiymatlarni almashtirish:
mylist = [64, 34, 25, 12, 22, 11, 90, 5]
n = len(mylist)
for i in range(n):
min_index = i
for j in range(i+1, n):
if mylist[j] < mylist[min_index]:
min_index = j
mylist[i], mylist[min_index] = mylist[min_index], mylist[i]
print(mylist)
Misolni ishga tushirish »
Tanlov saralash vaqtining murakkabligi
Tanlash Saralash \(n\) qiymatlar massivini tartiblaydi.
Har bir sikldagi eng past qiymatni topish uchun o‘rtacha taxminan \(\frac{n}{2}\) elementlar taqqoslanadi.
Tanlovni saralash eng past qiymatni taxminan \(n\) marta topish uchun siklni ishga tushirishi kerak.
Vaqt murakkabligi quyidagicha bo‘ladi: \( O( \frac{n}{2} \cdot n) = {O(n^2)} \)
Tanlovni saralash algoritmi uchun vaqt murakkabligi quyidagi kabi grafikda ko‘rsatilishi mumkin:
Ko‘rib turganingizdek, ishga tushirish vaqti Bubble Sort bilan bir xil: Massiv hajmi kattalashganda ish vaqti juda tez ortadi.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!