6-dars: Saralash — ishlatish

1-darajaBronza — algoritmik fikrlash1–8 darslar

HayotdaKutubxona

Kutubxonachidan «shu kitob bormi?» deb so’rasangiz, u javonga qaraydi va bir necha soniyada javob beradi. Kitoblar tartibsiz tursa, u butun xonani aylanib chiqishiga to’g’ri kelardi. Tartib kitob qidirmaydi — u qidirishni osonlashtiradi.

Bu darsdan keyin siz

• sort() va sorted() farqini bilasiz va kerakligini tanlaysiz
• «saralangandan keyin nima oson bo’ladi?» savolini har masalada berasiz
• kalit bo’yicha saralashni yozasiz

Avval qo’lda

Avval qo‘lda

~5 daqiqa·juftlikda·10 ta kartochka

O’nta kartochkaga tasodifiy sonlar yozing, ikkitasi bir xil bo’lsin. Kartochkalarni aralashtiring va sinfdoshingizdan takrorlangan juftlikni topishni so’rang. Nechta taqqoslash qilganini sanang.

Endi kartochkalarni o’sish tartibida tering va yana o’sha savolni bering. Necha taqqoslash kerak bo’ldi?

Nimani sezishingiz kerak

Ikkinchi safar faqat qo’shni kartochkalarni solishtirish yetdi. Saralash javobni bermadi — u masalani boshqa, ancha oson masalaga aylantirdi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

O’z saralashingizni yozmaysiz

Pufakcha, tanlash, birlashtirish orqali saralash — bularning hammasi qiziq, lekin ular bu darsning mavzusi emas. Python’ning sort() funksiyasi C tilida yozilgan, n log n ishlaydi va siznikidan tezroq.

◆Asosiy g'oya

Olimpiadada saralash algoritmi so’ralmaydi, saralashdan keyin nima qilish so’raladi. Shuning uchun savol bitta: bu ro’yxat tartiblangach, qaysi savolga javob berish osonlashadi?

sort() ro’yxatning o’zini o’zgartiradi va None qaytaradi. sorted() esa yangi ro’yxat qaytaradi va originalga tegmaydi. Asl tartib keyin kerak bo’lsa — ikkinchisini oling.

Sekin yechim

Masala: bir ko’chada n ta uy bor, qaysi ikkitasi bir-biriga eng yaqin? To’liq izlash har juftlikni o’lchaydi.

sekin.pyNusxalash

1uylar = [17, 3, 25, 9, 12, 6]2eng = None3for i in range(len(uylar)):4  for j in range(i + 1, len(uylar)):5      farq = abs(uylar[i] - uylar[j])6      if eng is None or farq < eng:7          eng = farq8print(eng)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1uylar = [17, 3, 25, 9, 12, 6]2eng = None3for i in range(len(uylar)):4  for j in range(i + 1, len(uylar)):5      farq = abs(uylar[i] - uylar[j])6      if eng is None or farq < eng:7          eng = farq8print(eng)

Sizning bashoratingizTekshirish

Javobni ko'rish

3

Eng yaqin juftlik — 6 va 9. Olti uy uchun 15 ta o'lchash bo'ldi; yuz ming uy uchun bu besh milliardga chiqadi.

Nega sekin

Har juftlik o’lchanadi, ya’ni n²/2 amal. Ammo bu ishning katta qismi ma’nosiz: ko’chaning ikki chekkasidagi uylarni solishtirishdan hech qanday foyda yo’q.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 5 000	n = 200 000
Har juftni o‘lchashn^2	10⁶sig‘adi	10⁷sig‘adi	10¹⁰sig‘maydi
Saralab, qo‘shnilarni ko‘rishn log n	9 966sig‘adi	61 439sig‘adi	10⁶sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

Saralangandan keyin bitta xossa paydo bo’ladi: eng yaqin ikki uy albatta qo’shni bo’ladi. Demak n² juftlik o’rniga n − 1 juftlikni ko’rish yetadi.

tez.pyNusxalash

1uylar = [17, 3, 25, 9, 12, 6]2uylar.sort()3eng = uylar[1] - uylar[0]4for i in range(1, len(uylar) - 1):5  farq = uylar[i + 1] - uylar[i]6  if farq < eng:7      eng = farq8print(uylar)9print(eng)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1uylar = [17, 3, 25, 9, 12, 6]2uylar.sort()3eng = uylar[1] - uylar[0]4for i in range(1, len(uylar) - 1):5  farq = uylar[i + 1] - uylar[i]6  if farq < eng:7      eng = farq8print(uylar)9print(eng)

Sizning bashoratingizTekshirish

Javobni ko'rish

[3, 6, 9, 12, 17, 25]
3

Saralangan ro'yxatda qo'shnilar orasidagi farqlar: 3, 3, 3, 5, 8. Eng kichigi — 3. abs() endi kerak emas, chunki keyingi son har doim kattaroq.

Nega qo’shnilar yetarli: agar a < b < c bo’lsa, a va c orasidagi masofa a va b orasidagidan kichik bo’la olmaydi. Demak qo’shni bo’lmagan juftlikni tekshirishning hojati yo’q.

Kalit bo’yicha saralash

Ko’pincha sonlar emas, murakkabroq narsalar saralanadi. key argumenti har element uchun nima bo’yicha solishtirishni aytadi.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1oquvchilar = [("Aziza", 87), ("Bek", 92), ("Dilnoza", 87)]2oquvchilar.sort(key=lambda x: -x[1])3print(oquvchilar)

Sizning bashoratingizTekshirish

Javobni ko'rish

[('Bek', 92), ('Aziza', 87), ('Dilnoza', 87)]

Minus belgisi tartibni teskari qiladi. Aziza va Dilnoza teng ball to'plagan va ular asl tartibda qolgan — Python saralashi bunday holatda tartibni buzmaydi.

Sinab ko’r

Vizualda bir masala ikki marta yechiladi: avval tartibsiz ro’yxatda, keyin saralanganida. Taqqoslash hisoblagichini solishtiring.

Saralashdan keyin nima oson bo'ladi

Avval tartibsiz ro'yxatda, keyin saralanganida — taqqoslash sonini solishtiring.

Tartibsiz ro'yxatda eng yaqin juftni topish uchun 15 ta taqqoslash kerak. Saralangandan keyin 5 ta yetadi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Masala: qaysi ikki son bir-biriga eng yaqin? Avval saralanmagan ro'yxatda ishlaymiz.
2. 17 va 3: farq 14. Har juftni ko'rish shart — tartib yo'q.
3. 17 va 25: farq 8. Har juftni ko'rish shart — tartib yo'q.
4. 17 va 9: farq 8. Har juftni ko'rish shart — tartib yo'q.
5. 17 va 12: farq 5. Har juftni ko'rish shart — tartib yo'q.
6. 17 va 6: farq 11. Har juftni ko'rish shart — tartib yo'q.
7. 3 va 25: farq 22. Har juftni ko'rish shart — tartib yo'q.
8. 3 va 9: farq 6. Har juftni ko'rish shart — tartib yo'q.
9. 3 va 12: farq 9. Har juftni ko'rish shart — tartib yo'q.
10. 3 va 6: farq 3. Har juftni ko'rish shart — tartib yo'q.
11. 25 va 9: farq 16. Har juftni ko'rish shart — tartib yo'q.
12. 25 va 12: farq 13. Har juftni ko'rish shart — tartib yo'q.
13. 25 va 6: farq 19. Har juftni ko'rish shart — tartib yo'q.
14. 9 va 12: farq 3. Har juftni ko'rish shart — tartib yo'q.
15. 9 va 6: farq 3. Har juftni ko'rish shart — tartib yo'q.
16. 12 va 6: farq 6. Har juftni ko'rish shart — tartib yo'q.
17. 15 ta taqqoslash. n = 6 da chidasa bo'ladi, n = 10 000 da 50 million bo'ladi.
18. Endi ro'yxatni SARALAYMIZ. Saralashni o'zimiz yozmaymiz — Python sorted() bor.
19. 3 va 6: farq 3. Saralangan ro'yxatda eng yaqin juft faqat YONMA-YON bo'la oladi.
20. 6 va 9: farq 3. Saralangan ro'yxatda eng yaqin juft faqat YONMA-YON bo'la oladi.
21. 9 va 12: farq 3. Saralangan ro'yxatda eng yaqin juft faqat YONMA-YON bo'la oladi.
22. 12 va 17: farq 5. Saralangan ro'yxatda eng yaqin juft faqat YONMA-YON bo'la oladi.
23. 17 va 25: farq 8. Saralangan ro'yxatda eng yaqin juft faqat YONMA-YON bo'la oladi.
24. Javob: 3 va 6. 15 taqqoslash o'rniga 5 ta. Saralash o'zi javob bermadi — u masalani osonlashtirdi.

xom

170312529312465

saralangan

??????

eng yaqin

Masala: qaysi ikki son bir-biriga eng yaqin? Avval saralanmagan ro'yxatda ishlaymiz.

Taqqoslash0

OrqagaO‘ynatishOldinga1/24Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

6 / 40

MasalaUylar ro'yxatidagi eng yaqin ikki uy masofasini toping.

Taklif qilingan yechim

1. 1Avval ro‘yxatni saralaymiz: uylar = uylar.sort().
2. 2Saralangandan keyin eng yaqin juftlik albatta qo‘shni bo‘ladi.
3. 3Barcha qo‘shni juftliklar farqini hisoblaymiz.
4. 4Eng kichigini chiqaramiz.

Bu javobning 1-qismi noto'g'ri. sort() ro'yxatni joyida saralaydi va None qaytaradi. uylar = uylar.sort() yozilsa, uylar o'zgaruvchisi None bo'lib qoladi va keyingi qatorda TypeError chiqadi. To'g'risi: yo uylar.sort() (o'zlashtirmasdan), yo uylar = sorted(uylar).

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1sort() va sorted() orasidagi farq nima?

Javobni ko'rish

sort() ro’yxatning o’zini o’zgartiradi va None qaytaradi. sorted() yangi ro’yxat qaytaradi, originalga tegmaydi. Asl tartib keyin kerak bo’lsa — sorted().

2Nega saralangandan keyin faqat qo'shnilarni ko'rish yetadi?

Javobni ko'rish

Saralangan ro’yxatda a < b < c bo’lsa, c − a har doim b − a dan katta yoki teng. Demak qo’shni bo’lmagan juftlik hech qachon eng yaqin bo’la olmaydi.

3Saralashning o'zi nechta amal oladi?

Javobni ko'rish

Taxminan n log n. n = 200000 da bu 3,5 million atrofida — 10⁸ chegarasidan ancha past, shuning uchun saralash deyarli har doim «arzon» hisoblanadi.

4key=lambda x: -x[1] nima qiladi?

Javobni ko'rish

Har elementni ikkinchi maydonining manfiy qiymati bo’yicha solishtiradi, ya’ni kamayuvchi tartib hosil qiladi. Xuddi shu natijani reverse=True bilan ham olish mumkin.

5Masalani ko'rganda saralash haqida qanday savol berasiz?

Javobni ko'rish

«Saralangandan keyin qaysi savolga javob berish osonlashadi?» Agar javob topilmasa, saralash bu masalada foyda bermaydi va boshqa yo’l izlash kerak.

Masalalar

Masalalar

3 ta

• Helpful MathsCodeforces 339Aoson

  Ifodani belgilarga ajrating, sonlarni saralang, keyin qayta yig‘ing.

• Distinct NumbersCSES 1621oson

  Saralangandan keyin bir xil sonlar yonma-yon turadi. To‘plamsiz ham yechiladi.

• Stick LengthsCSES 1074o'rta

  Saralang va o‘rtadagi elementga qarang. Nega aynan o‘rtasi — buni isbotlashga urinib ko‘ring.

Lokal mashq: mashqlar/06-eng-yaqin/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Sinfdoshlaringiz ismini va bo’yini ro’yxat qilib yozing, keyin uni bo’y bo’yicha kamayuvchi tartibda qayta yozing. Qo’lda nechta taqqoslash qilganingizni sanang.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

06-eng-yaqin masalasini yeching. Yechimingizni ikki xil kirishda sinang: barcha sonlar bir xil bo’lgan ro’yxat va ikkita elementli ro’yxat. Ikkalasida ham to’g’ri javob chiqdimi?

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Stick Lengths masalasini yeching va nega o’rtadagi element optimal ekanini yozma isbotlang. Ishora: tanlangan nuqtani bir birlik siljitsangiz, qancha tayoq yutadi va qanchasi yutqazadi?

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim