Quick Sort

---

Vaqt murakkabligi nima ekani haqidagi umumiy tushuntirish uchun ushbu sahifaga qarang.

---

Quicksort’ning vaqt murakkabligi

Quicksort algoritmi bitta qiymatni tayanch (pivot) element sifatida tanlaydi va boshqa qiymatlarni kattaroq qiymatlar tayanch elementning o‘ng tomonida, kichikroq qiymatlar esa chap tomonida bo‘ladigan qilib ko‘chiradi.

So‘ngra Quicksort algoritmi massiv saralanmaguncha tayanch elementning chap va o‘ng tomonidagi qism massivlarni rekursiv ravishda saralashda davom etadi.

---

Eng yomon holat

Quicksort vaqt murakkabligini topish uchun eng yomon holatni ko‘rib chiqishdan boshlashimiz mumkin.

Quicksort uchun eng yomon holat — massiv allaqachon saralangan bo‘lishi. Bunday holatda har bir rekursiv chaqiruvdan keyin faqat bitta qism massiv qoladi va yangi qism massivlar oldingi massivdan atigi bitta elementga qisqa bo‘ladi.

Bu Quicksort o‘zini rekursiv ravishda \(n\) marta chaqirishi va har safar o‘rtacha \(\frac{n}{2}\) ta taqqoslash bajarishi kerakligini anglatadi.

Eng yomon holatdagi vaqt murakkabligi:

\[ O(n \cdot \frac{n}{2}) = \underline{\underline{O(n^2)}} \]

---

O‘rtacha holat

O‘rtacha olganda Quicksort aslida ancha tezroq ishlaydi.

Quicksort o‘rtacha holatda tez ishlaydi, chunki Quicksort har safar rekursiv ishga tushganda massiv taxminan teng ikkiga bo‘linadi. Shu sababli qism massivlar hajmi juda tez kichrayadi, demak, unchalik ko‘p rekursiv chaqiruv kerak bo‘lmaydi va Quicksort eng yomon holatdagiga qaraganda tezroq yakunlanadi.

Quyidagi rasmda 23 ta qiymatdan iborat massiv Quicksort bilan saralanganda qanday qilib qism massivlarga bo‘linishi ko‘rsatilgan.

Pivot element (yashil) o‘rtaga ko‘chiriladi va massiv qism massivlarga (sariq) bo‘linadi. Tobora kichrayib boruvchi qism massivlardan iborat 5 ta rekursiya darajasi bor va har bir darajada taxminan \(n\) ta qiymat u yoki bu tarzda ishtirok etadi: taqqoslanadi, ko‘chiriladi yoki ikkalasi ham.

\( \log_2 \) sonni necha marta 2 ga bo‘lish mumkinligini ko‘rsatadi, shuning uchun \( \log_2 \) rekursiya darajalari soni uchun yaxshi baho hisoblanadi. \( \log_2(23) \approx 4.5 \) — bu yuqoridagi aniq misoldagi rekursiya darajalari soniga yetarlicha yaqin qiymat.

Aslida qism massivlar har safar aynan teng ikkiga bo‘linmaydi va har bir darajada aynan \(n\) ta qiymat taqqoslanmaydi yoki ko‘chirilmaydi, ammo vaqt murakkabligini topish uchun buni o‘rtacha holat deb aytishimiz mumkin:

\[ \underline{\underline{O(n \cdot \log_2n)}} \]

Quyida o‘rtacha holatda Quicksort vaqt murakkabligi avvalgi saralash algoritmlari — Bubble, Selection va Insertion Sort bilan solishtirganda sezilarli darajada yaxshi ekanini ko‘rishingiz mumkin:

Quicksort algoritmining rekursiv qismi aslida o‘rtacha holatda saralash juda tez bo‘lishining sabablaridan biri, chunki pivot element yaxshi tanlanganda algoritm har safar o‘zini chaqirganda massiv taxminan teng ikkiga bo‘linadi. Shuning uchun qiymatlar soni \(n \) ikki baravar oshsa ham, rekursiv chaqiruvlar soni ikki baravar oshmaydi.

---

Quicksort simulyatsiyasi

Nazariy vaqt murakkabligi \(O(n^2)\) (qizil chiziq) haqiqiy Quicksort ishga tushirishlaridagi amallar soni bilan qanday solishtirilishini ko‘rish uchun quyidagi simulyatsiyadan foydalaning.

Yuqoridagi qizil chiziq eng yomon holat uchun nazariy yuqori chegara vaqt murakkabligi \(O(n^2)\) ni, yashil chiziq esa tasodifiy qiymatlar bilan o‘rtacha holatdagi vaqt murakkabligi \(O(n \log_2n)\) ni ifodalaydi.

Quicksort uchun o‘rtacha tasodifiy holatlar bilan massivlar allaqachon saralangan holatlar o‘rtasida katta farq bor. Buni yuqoridagi turli simulyatsiyalarni ishga tushirib ko‘rishingiz mumkin.

Allaqachon o‘sish tartibida saralangan massiv shuncha ko‘p amal talab qilishining sababi shundaki, algoritm qanday amalga oshirilganiga ko‘ra, bu holat elementlarning eng ko‘p o‘rin almashtirilishini talab qiladi. Bu holatda oxirgi element pivot element sifatida tanlanadi va oxirgi element ayni paytda eng katta son hamdir. Shuning uchun har bir qism massivdagi barcha boshqa qiymatlar pivot elementning chap tomoniga tushishi uchun o‘rin almashtiriladi (garchi ular allaqachon o‘sha yerda joylashgan bo‘lsa ham).

---

---