Oddiy saralash algoritmlari

def pufakcha_sarala(massiv):
    """Pufakcha usuli. O(n^2) vaqt, O(1) xotira, barqaror."""
    sonlar = list(massiv)
    n = len(sonlar)

    for otish in range(n - 1):
        almashtirildi = False

        # Oxirgi `otish` ta element allaqachon o'z joyida
        for i in range(n - 1 - otish):
            if sonlar[i] > sonlar[i + 1]:
                sonlar[i], sonlar[i + 1] = sonlar[i + 1], sonlar[i]
                almashtirildi = True

        if not almashtirildi:        # allaqachon tartiblangan
            break

    return sonlar


print(pufakcha_sarala([5, 2, 8, 1, 9, 3]))

def tanlash_bilan_sarala(massiv):
    """Tanlash usuli. O(n^2) vaqt, O(1) xotira, barqaror emas."""
    sonlar = list(massiv)
    n = len(sonlar)

    for i in range(n - 1):
        eng_kichik_indeks = i

        for j in range(i + 1, n):
            if sonlar[j] < sonlar[eng_kichik_indeks]:
                eng_kichik_indeks = j

        if eng_kichik_indeks != i:
            sonlar[i], sonlar[eng_kichik_indeks] = sonlar[eng_kichik_indeks], sonlar[i]

    return sonlar


print(tanlash_bilan_sarala([5, 2, 8, 1, 9, 3]))

def tanlash_qadam_bilan(massiv):
    sonlar = list(massiv)
    n = len(sonlar)

    for i in range(n - 1):
        eng_kichik = i
        for j in range(i + 1, n):
            if sonlar[j] < sonlar[eng_kichik]:
                eng_kichik = j
        sonlar[i], sonlar[eng_kichik] = sonlar[eng_kichik], sonlar[i]

        tartiblangan = " ".join(f"[{q}]" for q in sonlar[:i + 1])
        qolgan = " ".join(f" {q} " for q in sonlar[i + 1:])
        print(f"  {i + 1}-qadam: {tartiblangan} {qolgan}")

    return sonlar


tanlash_qadam_bilan([5, 2, 8, 1, 9, 3])

def qoshish_bilan_sarala(massiv):
    """Qo'shish usuli. O(n^2), lekin deyarli tartiblangan massivda O(n)."""
    sonlar = list(massiv)

    for i in range(1, len(sonlar)):
        joriy = sonlar[i]
        j = i - 1

        # Kattaroq elementlarni o'ngga suramiz
        while j >= 0 and sonlar[j] > joriy:
            sonlar[j + 1] = sonlar[j]
            j -= 1

        sonlar[j + 1] = joriy

    return sonlar


print(qoshish_bilan_sarala([5, 2, 8, 1, 9, 3]))

import random
import time


def olcha(funksiya, ma_lumot):
    boshlanish = time.perf_counter()
    funksiya(ma_lumot)
    return time.perf_counter() - boshlanish


N = 2000
tasodifiy = random.sample(range(N * 10), N)
tartiblangan = sorted(tasodifiy)
teskari = tartiblangan[::-1]

algoritmlar = [
    ("Pufakcha", pufakcha_sarala),
    ("Tanlash", tanlash_bilan_sarala),
    ("Qo'shish", qoshish_bilan_sarala),
    ("sorted() [Timsort]", sorted),
]

print(f"{'Algoritm':<22}{'Tasodifiy':>12}{'Tartiblangan':>14}{'Teskari':>12}")
print("-" * 60)
for nomi, funksiya in algoritmlar:
    a = olcha(funksiya, tasodifiy)
    b = olcha(funksiya, tartiblangan)
    c = olcha(funksiya, teskari)
    print(f"{nomi:<22}{a:>11.4f}s{b:>13.4f}s{c:>11.4f}s")

talabalar = [
    ("Husanboy", 85),
    ("Sardor", 92),
    ("Malika", 85),
    ("Bekzod", 78),
]

# Avval ism bo'yicha, keyin baho bo'yicha saralaymiz
ism_boyicha = sorted(talabalar, key=lambda t: t[0])
baho_boyicha = sorted(ism_boyicha, key=lambda t: t[1], reverse=True)

for ism, baho in baho_boyicha:
    print(f"{ism:<10}{baho}")