DSA Quick Sort (tez saralash)

Quicksort

Nomidan ko‘rinib turganidek, Quicksort eng tez saralash algoritmlaridan biridir.

Quicksort algoritmi qiymatlar massivini oladi, qiymatlardan birini "pivot" (tayanch) element sifatida tanlaydi va boshqa qiymatlarni shunday ko‘chiradiki, kichikroq qiymatlar pivot elementning chap tomonida, kattaroq qiymatlar esa uning o‘ng tomonida bo‘ladi.

Ushbu darslikda massivning oxirgi elementi pivot element sifatida tanlanadi, ammo massivning birinchi elementini yoki, aslida, massivdagi istalgan elementni ham tanlashimiz mumkin edi.

So‘ngra Quicksort algoritmi pivot elementning chap va o‘ng tomonidagi qism massivlar ustida xuddi shu amalni rekursiv ravishda bajaradi. Bu massiv saralanguncha davom etadi.

Algoritmni quyidagicha tavsiflash mumkin:

Quicksort algoritmini va uni o‘zingiz qanday amalga oshirishni to‘liq tushunish uchun o‘qishda davom eting.

Qo‘lda bajarib ko‘rish

Quicksort algoritmini dasturlash tilida amalga oshirishdan oldin, g‘oyani tushunib olish uchun qisqa massiv bo‘ylab qo‘lda o‘tib chiqaylik.

1-qadam: Saralanmagan massivdan boshlaymiz.

2-qadam: Oxirgi qiymat — 3 ni pivot element sifatida tanlaymiz.

3-qadam: Massivdagi qolgan qiymatlarning barchasi 3 dan katta va 3 ning o‘ng tomonida bo‘lishi kerak. 3 ni 11 bilan almashtiramiz.

4-qadam: Endi 3 qiymati to‘g‘ri pozitsiyada. 3 ning o‘ng tomonidagi qiymatlarni saralashimiz kerak. Oxirgi qiymat — 11 ni yangi pivot element sifatida tanlaymiz.

5-qadam: 7 qiymati pivot qiymat — 11 ning chap tomonida, 12 esa uning o‘ng tomonida bo‘lishi kerak. 7 va 12 ni ko‘chiramiz.

6-qadam: Kichikroq qiymatlar — 9 va 7 11 ning chap tomonida, 12 esa o‘ng tomonida bo‘lishi uchun 11 ni 12 bilan almashtiramiz.

7-qadam: 11 va 12 to‘g‘ri pozitsiyalarda. 11 ning chap tomonidagi [ 9, 7] qism massivida 7 ni pivot element sifatida tanlaymiz.

8-qadam: 9 ni 7 bilan almashtirishimiz kerak.

Mana endi massiv saralandi.

Yuqoridagi qadamlarni animatsiyada ko‘rish uchun quyidagi simulyatsiyani ishga tushiring:

Qo‘lda bajarib ko‘rish: nima sodir bo‘ldi?

Algoritmni dasturlash tilida amalga oshirishdan oldin yuqorida nima sodir bo‘lganini batafsilroq ko‘rib chiqishimiz kerak.

Massivning oxirgi qiymati pivot element sifatida tanlanishini va qolgan qiymatlar pivot qiymatdan kichiklari chapda, kattaroqlari esa o‘ngda bo‘ladigan qilib joylashtirilishini ko‘rdik.

Shundan so‘ng pivot element kattaroq qiymatlarning birinchisi bilan almashtiriladi. Bu dastlabki massivni ikkiga bo‘ladi, pivot element esa kichikroq va kattaroq qiymatlar orasida joylashadi.

Endi eski pivot elementning chap va o‘ng tomonidagi qism massivlar bilan ham yuqoridagi kabi ish tutishimiz kerak. Agar qism massivning uzunligi 0 yoki 1 bo‘lsa, uni to‘liq saralangan deb hisoblaymiz.

Xulosa qilib aytganda, Quicksort algoritmi massiv saralanguncha qism massivlarni tobora qisqartirib boradi.

Quicksort’ni amalga oshirish

Massivni tobora qisqaroq qism massivlarga bo‘ladigan "quickSort" metodini yozish uchun rekursiyadan foydalanamiz. Bu "quickSort" metodi pivot elementning chap va o‘ng tomonidagi yangi qism massivlar bilan o‘zini o‘zi chaqirishi kerakligini anglatadi. Rekursiya haqida bu yerda batafsil o‘qing.

Quicksort algoritmini dasturlash tilida amalga oshirish uchun bizga quyidagilar kerak:

1. Saralanadigan qiymatlarga ega massiv.
2. Agar qism massivning o‘lchami 1 dan katta bo‘lsa, o‘zini o‘zi chaqiradigan (rekursiya) quickSort metodi.
3. Qism massivni qabul qiladigan, qiymatlarni ko‘chiradigan, pivot elementni almashtirish orqali qism massivdagi o‘rniga qo‘yadigan va qism massivlarga navbatdagi bo‘linish sodir bo‘ladigan indeksni qaytaradigan partition metodi.

Natijaviy kod quyidagicha ko‘rinadi:

def partition(array, low, high):
    pivot = array[high]
    i = low - 1

    for j in range(low, high):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]

    array[i+1], array[high] = array[high], array[i+1]
    return i+1

def quicksort(array, low=0, high=None):
    if high is None:
        high = len(array) - 1

    if low < high:
        pivot_index = partition(array, low, high)
        quicksort(array, low, pivot_index-1)
        quicksort(array, pivot_index+1, high)

my_array = [64, 34, 25, 12, 22, 11, 90, 5]
quicksort(my_array)
print("Sorted array:", my_array)

Quicksort’ning vaqt murakkabligi

Vaqt murakkabligi nima ekanligi haqida umumiy tushuntirish uchun ushbu sahifaga tashrif buyuring.

Quicksort vaqt murakkabligi haqida yanada chuqurroq va batafsil tushuntirish uchun ushbu sahifaga tashrif buyuring.

Quicksort uchun eng yomon holat — \(O(n^2) \). Bu pivot element har bir qism massivda yo eng katta, yo eng kichik qiymat bo‘lganda yuz beradi va ko‘plab rekursiv chaqiruvlarga olib keladi. Yuqoridagi amalga oshirishimizda bu massiv allaqachon saralangan bo‘lganda sodir bo‘ladi.

Ammo o‘rtacha holatda Quicksort’ning vaqt murakkabligi aslida atigi \(O(n \log n) \) bo‘lib, bu biz ko‘rib chiqqan oldingi saralash algoritmlarinikidan ancha yaxshi. Quicksort’ning bunchalik mashhurligining sababi ham shunda.

Quyida vaqt murakkabligi \(O(n^2) \) bo‘lgan oldingi saralash algoritmlari — Bubble, Selection va Insertion Sort bilan solishtirganda, Quicksort’ning o‘rtacha holatdagi vaqt murakkabligi \(O(n \log n) \) qanchalik sezilarli darajada yaxshiroq 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.

Quyidagi simulyatsiyada Quicksort’ni turli sondagi qiymatlarga ega turli xil massivlarda ishga tushirib ko‘ring:

def partition(array, low, high):
    pivot = array[high]
    i = low - 1

    for j in range(low, high):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]

    array[i+1], array[high] = array[high], array[i+1]
    return i+1

def quicksort(array, low=0, high=None):
    if high is None:
        high = len(array) - 1

    if low < high:
        pivot_index = partition(array, low, high)
        (array, low, pivot_index-1)
        (array, pivot_index+1, high)

my_array = [64, 34, 25, 12, 22, 11, 90, 5]
quicksort(my_array)
print("Sorted array:", my_array)