Samarali saralash algoritmlari

def birlashtirib_sarala(massiv):
    """Merge sort. Kafolatlangan O(n log n), barqaror, O(n) qo'shimcha xotira."""
    if len(massiv) <= 1:
        return list(massiv)

    orta = len(massiv) // 2
    chap = birlashtirib_sarala(massiv[:orta])
    ong = birlashtirib_sarala(massiv[orta:])

    return _birlashtir(chap, ong)


def _birlashtir(chap, ong):
    """Ikkita tartiblangan ro'yxatni bittaga birlashtiradi. O(n)."""
    natija = []
    i = j = 0

    while i < len(chap) and j < len(ong):
        if chap[i] <= ong[j]:          # <= barqarorlikni ta'minlaydi
            natija.append(chap[i])
            i += 1
        else:
            natija.append(ong[j])
            j += 1

    natija.extend(chap[i:])            # qolganini qo'shamiz
    natija.extend(ong[j:])
    return natija


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

def birlashtirishni_korsat(chap, ong):
    natija = []
    i = j = 0

    while i < len(chap) and j < len(ong):
        if chap[i] <= ong[j]:
            print(f"  {chap[i]} <= {ong[j]}  ->  {chap[i]} olindi")
            natija.append(chap[i])
            i += 1
        else:
            print(f"  {chap[i]} >  {ong[j]}  ->  {ong[j]} olindi")
            natija.append(ong[j])
            j += 1

    qolgan = chap[i:] + ong[j:]
    if qolgan:
        print(f"  qolgani qo'shildi: {qolgan}")
    return natija + qolgan


print("Natija:", birlashtirishni_korsat([2, 5, 8], [1, 3, 9]))

def tez_sarala(massiv):
    """Quick sort - sodda, o'qish oson variant. O'rtacha O(n log n)."""
    if len(massiv) <= 1:
        return list(massiv)

    tayanch = massiv[len(massiv) // 2]

    kichiklar = [x for x in massiv if x < tayanch]
    tenglar   = [x for x in massiv if x == tayanch]
    kattalar  = [x for x in massiv if x > tayanch]

    return tez_sarala(kichiklar) + tenglar + tez_sarala(kattalar)


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

def tez_sarala_joyida(massiv, chap=None, ong=None):
    """Quick sort - joyida ishlaydi, O(log n) xotira (stek uchun)."""
    if chap is None:
        massiv = list(massiv)
        chap, ong = 0, len(massiv) - 1

    if chap < ong:
        bolgich = _bol(massiv, chap, ong)
        tez_sarala_joyida(massiv, chap, bolgich - 1)
        tez_sarala_joyida(massiv, bolgich + 1, ong)

    return massiv


def _bol(massiv, chap, ong):
    """Lomuto usuli: oxirgi elementni tayanch qilib, massivni ikkiga ajratadi."""
    tayanch = massiv[ong]
    i = chap - 1

    for j in range(chap, ong):
        if massiv[j] <= tayanch:
            i += 1
            massiv[i], massiv[j] = massiv[j], massiv[i]

    massiv[i + 1], massiv[ong] = massiv[ong], massiv[i + 1]
    return i + 1


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

import random


def tez_sarala_tasodifiy(massiv):
    """Tasodifiy tayanch - eng yomon holat ehtimolini deyarli nolga tushiradi."""
    if len(massiv) <= 1:
        return list(massiv)

    tayanch = random.choice(massiv)
    kichiklar = [x for x in massiv if x < tayanch]
    tenglar   = [x for x in massiv if x == tayanch]
    kattalar  = [x for x in massiv if x > tayanch]

    return tez_sarala_tasodifiy(kichiklar) + tenglar + tez_sarala_tasodifiy(kattalar)


tartiblangan = list(range(1, 11))
print(tez_sarala_tasodifiy(tartiblangan))

import random
import time


def olcha(nomi, ma_lumot):
    boshlanish = time.perf_counter()
    sorted(ma_lumot)
    print(f"{nomi:<28}{time.perf_counter() - boshlanish:.5f} soniya")


N = 1_000_000
tasodifiy = random.sample(range(N * 2), N)
tartiblangan = sorted(tasodifiy)
teskari = tartiblangan[::-1]
deyarli = tartiblangan[:]
for _ in range(100):                       # 100 ta elementni aralashtiramiz
    i, j = random.randrange(N), random.randrange(N)
    deyarli[i], deyarli[j] = deyarli[j], deyarli[i]

olcha("Tasodifiy", tasodifiy)
olcha("Tartiblangan", tartiblangan)
olcha("Teskari tartiblangan", teskari)
olcha("Deyarli tartiblangan", deyarli)

def sanash_bilan_sarala(sonlar, eng_katta):
    """Counting sort. O(n + k) - lekin faqat kichik butun sonlar uchun."""
    hisoblagich = [0] * (eng_katta + 1)

    for son in sonlar:
        hisoblagich[son] += 1

    natija = []
    for qiymat, soni in enumerate(hisoblagich):
        natija.extend([qiymat] * soni)

    return natija


baholar = [85, 92, 78, 95, 85, 78, 92, 100, 60]
print(sanash_bilan_sarala(baholar, 100))