Saralash algoritmlari: pufakchali va tanlash usuli Python’da

Saralash — dasturlashdagi eng klassik masalalardan biri: kontaktlar ro‘yxati alifbo bo‘yicha, reyting ballar bo‘yicha, mahsulotlar narx bo‘yicha tartiblanadi. Saralash algoritmlarini o‘rganish algoritmik fikrlash va samaradorlik tushunchasini o‘zlashtirishning eng yaxshi yo‘li.

1. Pufakchali saralash (Bubble sort)

G‘oya: qo‘shni elementlarni solishtirib, agar tartib buzilgan bo‘lsa, ularni almashtiramiz. Har bir o‘tishda eng katta element “pufakcha” kabi oxiriga suzib chiqadi.

1def bubble_sort(a):
2    n = len(a)
3    for i in range(n - 1):
4        almashdi = False
5        for j in range(n - 1 - i):
6            if a[j] > a[j + 1]:
7                a[j], a[j + 1] = a[j + 1], a[j]
8                almashdi = True
9        if not almashdi:   # massiv allaqachon tartiblangan
10            break
11    return a
12
13print(bubble_sort([5, 3, 8, 1, 4]))   # [1, 3, 4, 5, 8]

Qadamlar ([5, 3, 8, 1, 4] uchun, 1-o‘tish):

1[5, 3, 8, 1, 4]  5>3 → almashtir
2[3, 5, 8, 1, 4]  5<8 → qoldir
3[3, 5, 8, 1, 4]  8>1 → almashtir
4[3, 5, 1, 8, 4]  8>4 → almashtir
5[3, 5, 1, 4, 8]  ← 8 o‘z joyida

2. Tanlash usuli (Selection sort)

G‘oya: tartiblanmagan qismdan eng kichik elementni topib, uni shu qismning boshiga qo‘yamiz.

1def selection_sort(a):
2    n = len(a)
3    for i in range(n - 1):
4        min_idx = i
5        for j in range(i + 1, n):
6            if a[j] < a[min_idx]:
7                min_idx = j
8        a[i], a[min_idx] = a[min_idx], a[i]
9    return a

3. Qo‘yish usuli (Insertion sort)

G‘oya: qo‘ldagi o‘yin kartalarini tartiblash kabi — har bir yangi elementni tartiblangan qismdagi to‘g‘ri joyiga qo‘yamiz. Deyarli tartiblangan ma’lumotlarda juda tez ishlaydi.

1def insertion_sort(a):
2    for i in range(1, len(a)):
3        kalit = a[i]
4        j = i - 1
5        while j >= 0 and a[j] > kalit:
6            a[j + 1] = a[j]
7            j -= 1
8        a[j + 1] = kalit
9    return a

Murakkablik: qaysi biri tezroq?

Uchala algoritm ham o‘rtacha holatda O(n²) amal bajaradi: 1 000 element uchun taxminan 1 000 000 solishtirish. 1 000 000 element uchun esa bu juda sekin.

• Pufakchali — eng oddiy, lekin eng ko‘p almashtirish qiladi.
• Tanlash — almashtirishlar soni eng kam (n − 1 ta).
• Qo‘yish — deyarli tartiblangan ma’lumotda O(n) ga yaqin.

Amalda esa O(n log n) algoritmlar ishlatiladi: tez saralash (Quick sort), birlashtirib saralash (Merge sort). Python’ning o‘rnatilgan sorted() funksiyasi Timsort algoritmidan foydalanadi.

Tezlikni o‘zingiz o‘lchang

1import random, time
2
3data = [random.randint(1, 10000) for _ in range(3000)]
4
5t = time.time()
6bubble_sort(data.copy())
7print("Bubble:", round(time.time() - t, 3), "s")
8
9t = time.time()
10sorted(data)
11print("sorted():", round(time.time() - t, 5), "s")

Natija o‘quvchilarni hayratda qoldiradi: o‘rnatilgan funksiya yuzlab marta tezroq!

Darsda vizuallashtirish

1. Tirik saralash — 6–8 o‘quvchi bo‘yi yoki kartochkadagi son bo‘yicha pufakchali usulda qatorga turadi.
2. Kartalar bilan — har bir juftlik o‘yin kartalarini qo‘yish usulida tartiblaydi va solishtirishlar sonini sanaydi.
3. Onlayn vizualizatorlar — visualgo.net saytida algoritmlar animatsiyasini ko‘rsatish.

Mustaqil ish

1. Pufakchali saralashni kamayish tartibida ishlaydigan qilib o‘zgartiring.
2. O‘quvchilar ismlarini alifbo bo‘yicha tanlash usulida saralang.
3. Har bir algoritm nechta solishtirish bajarganini sanaydigan hisoblagich qo‘shing va 10, 100, 1000 elementli massivlarda solishtiring.