Tez saralash: bo‘lib hal qilish usuli

Tez saralash (quicksort) — “bo‘lib hal qil” tamoyiliga asoslangan algoritm: katta masala kichik masalalarga bo‘linadi, ular alohida hal qilinadi va natijalar birlashtiriladi. Birinchi qadamda massivdan tayanch element tanlanadi. Qolgan elementlar uchga ajratiladi: tayanchdan kichiklari, unga tengları va undan kattalari.

Shundan so‘ng kichiklar va kattalar guruhi o‘sha usulning o‘zi bilan, ya’ni rekursiv saralanadi. Bo‘lak bitta element yoki bo‘sh bo‘lganda u allaqachon tartiblangan hisoblanadi — bu rekursiyaning to‘xtash sharti. Python’da qisqa yozuv: def qs(a): return a if len(a) <= 1 else qs([x for x in a if x < a[0]]) + [x for x in a if x == a[0]] + qs([x for x in a if x > a[0]]).

Massiv 5 2 8 1 5 bo‘lsin, tayanch — 5. Kichiklar: 2 1, tenglar: 5 5, kattalar: 8. 2 1 ni saralash 1 2 ni beradi, natija 1 2 5 5 8. Tayanch massivni taxminan teng ikkiga bo‘lsa, chuqurlik taxminan log₂ n ga teng bo‘ladi va umumiy ish n · log₂ n ga mutanosib; masalan, 1 000 000 ta element uchun bu taxminan 20 million amal, pufakchali saralashdagi 500 milliarddan ancha kam.

Tez saralashning eng yomon holati — tayanch har safar eng kichik yoki eng katta element chiqqanda: bunda vaqt n² ga yaqinlashadi. Buni kamaytirish uchun tayanch o‘rtadan yoki tasodifiy tanlanadi. Amalda saralash uchun Python’ning tayyor sorted() funksiyasi qo‘llanadi, tez saralash esa bo‘lib hal qilish g‘oyasini o‘rganishning eng yaxshi namunasidir.

Asosiy xulosalar

Tez saralash tayanch element atrofida massivni kichiklar, tenglar va kattalarga bo‘ladi.
Kichik va katta qismlar o‘sha usulning o‘zi bilan rekursiv saralanadi.
O‘rtacha holatda vaqt n · log₂ n ga mutanosib — pufakchali saralashdan ancha tez.
Eng yomon holatda (tayanch har safar chetki element) vaqt n² ga yaqinlashadi.
Amalda tayyor sorted() funksiyasidan foydalaniladi.

Amaliy topshiriqlar

Massiv 4 9 1 7 4 3 ni tez saralash usuli bilan qo‘lda saralang: har bir qadamda tayanch elementni, kichiklar, tenglar va kattalar guruhini yozing (tayanch — massivning birinchi elementi).
Yuqoridagi qs funksiyasini faylga yozing va 10 ta tasodifiy sondan iborat ro‘yxat bilan sinab ko‘ring. Natijani sorted() natijasi bilan solishtiring.
Funksiyani o‘zgartiring: saralash kamayish tartibida bo‘lsin. Qaysi shartlar almashishini aniqlang va dasturni tekshiring.

Mustahkamlash savollari

O‘zingizni sinab ko‘ring: avval o‘ylab ko‘ring, keyin javobni oching.

1Tez saralashda tayanch element nima uchun kerak?Javobni ko‘rish

Unga nisbatan elementlar kichiklar, tenglar va kattalar guruhiga ajratiladi, shunda tayanch o‘z joyini egallaydi.

2Tez saralash qachon eng sekin ishlaydi?Javobni ko‘rish

Tayanch har safar eng kichik yoki eng katta element bo‘lib chiqqanda: vaqt n² ga yaqinlashadi.