درک مرتب سازی سریع در کاتلین: راهنمای مبتدیان

QuickSort چیست؟

QuickSort یک الگوریتم مرتب‌سازی بسیار کارآمد و مبتنی بر مقایسه است که از استراتژی تفرقه و غلبه استفاده می‌کند. این الگوریتم که توسط تونی هور در سال 1959 توسعه یافت، به دلیل عملکرد عالی در ابعاد متوسط ​​و استفاده کارآمد از حافظه، به یکی از پرکاربردترین الگوریتم‌های مرتب‌سازی تبدیل شده است.

این الگوریتم با انتخاب یک عنصر 'pivot' از آرایه و تقسیم عناصر دیگر به دو آرایه فرعی بر اساس کوچکتر یا بزرگتر بودن آنها از pivot کار می کند. سپس آرایه های فرعی به صورت بازگشتی مرتب می شوند.

چه زمانی از QuickSort استفاده کنیم؟

QuickSort یک الگوریتم مرتب سازی همه منظوره عالی با چندین مورد استفاده ایده آل است:

• مجموعه داده های بزرگ: میانگین پیچیدگی زمانی O(n log n) QuickSort آن را برای آرایه های بزرگ کارآمد می کند.

• حافظه محدود: قابلیت مرتب سازی در محل آن باعث کارآمدی حافظه می شود.

• حافظه دسترسی تصادفی: QuickSort هنگام دسترسی به عناصر در موقعیت های دلخواه عملکرد خوبی دارد.

با این حال، زمانی که مرتب‌سازی پایدار مورد نیاز است یا هنگام برخورد با داده‌های تقریبا مرتب‌شده، ممکن است بهترین انتخاب نباشد.

QuickSort چگونه کار می کند

QuickSort از طریق پارتیشن بندی حول یک عنصر محوری از یک استراتژی تقسیم کن و حکومت کن استفاده می کند.

توضیح گام به گام

1. Pivot را انتخاب کنید:

   • یک عنصر محوری را از آرایه انتخاب کنید (معمولا عنصر اول، آخرین یا وسط).

2. پارتیشن:

   • عناصر را طوری مرتب کنید که همه عناصر کوچکتر از محور در سمت چپ قرار گیرند.
   • همه عناصر بزرگتر از محور در سمت راست قرار دارند.

3. مرتب سازی بازگشتی:

   • به صورت بازگشتی همین فرآیند را برای آرایه های فرعی در دو طرف پیوت اعمال کنید.

نمایش بصری QuickSort

برای مرتب کردن آرایه [64, 34, 25, 12, 22] با آخرین عنصر به عنوان محور:

1. پارتیشن اول (pivot = 22):
   • نتیجه: [12, 34, 25, 64, 22] → [12, 22, 25, 64, 34]
2. پارتیشن های چپ و راست را به صورت بازگشتی مرتب کنید

کد شبه برای QuickSort

function quickSort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quickSort(arr, low, pivot_index - 1)
        quickSort(arr, pivot_index + 1, high)

function partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j from low to high - 1:
        if arr[j] <= pivot:
            i = i + 1
            swap arr[i] with arr[j]
    swap arr[i + 1] with arr[high]
    return i + 1

پیاده سازی QuickSort در Kotlin

fun quickSort(arr: IntArray, low: Int = 0, high: Int = arr.size - 1) {
    if (low < high) {
        val pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, high)
    }
}

fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low - 1

    for (j in low until high) {
        if (arr[j] <= pivot) {
            i++
            // Swap elements
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }
    // Place pivot in correct position
    arr[i + 1] = arr[high].also { arr[high] = arr[i + 1] }
    return i + 1
}

مرور کد

• عملکرد اصلی:

  • به صورت بازگشتی آرایه را به پارتیشن های کوچکتر تقسیم می کند.
  • تا زمانی که پارتیشن ها به اندازه 1 یا 0 باشند ادامه می یابد.

• عملکرد پارتیشن:

  • آخرین عنصر را به عنوان محور انتخاب می کند.
  • عناصر کوچکتر را در سمت چپ، بزرگتر به راست قرار می دهد.
  • موقعیت نهایی محور را برمی‌گرداند.

فرآیند گام به گام بصری

آرایه اولیه: [64, 34, 25, 12, 22]

پارتیشن اول:

[64, 34, 25, 12, 22]  // Choose 22 as pivot
                   ↓
[12, 34, 25, 64, 22]  // Arrange elements around pivot
 ↓           ↑   ↓
[12, 22, 25, 64, 34]  // Pivot in final position
     ↓

پارتیشن های بازگشتی:

Left: [12]           // Already sorted
Right: [25, 64, 34]  // Continue partitioning
      [25, 34, 64]   // Final sorted array

افسانه:

• ↓ : عنصر محوری
• ↑ : عناصر در حال مقایسه
• بدون علامت: عناصر مرتب نشده

تحلیل پیچیدگی زمانی

بهترین حالت: O(n log n)

• زمانی اتفاق می‌افتد که پیوت به‌طور پیوسته آرایه را به نصف‌های مساوی تقسیم کند
• هر سطح از بازگشت n عنصر را پردازش می کند
• ورود به سیستم n سطح بازگشت

بدترین حالت: O(n²)

• زمانی اتفاق می افتد که pivot همیشه کوچکترین/بزرگترین عنصر باشد
• هر پارتیشن فقط یک عنصر را حذف می کند
• n سطح بازگشت مورد نیاز است

میانگین مورد: O(n log n)

• انتخاب محوری تصادفی معمولاً پارتیشن بندی خوبی را فراهم می کند
• تقسیم متعادل آرایه در اکثر موارد

پیچیدگی فضا: O (log n)

• پشته تماس بازگشتی در موارد متعادل
• O(n) در بدترین حالت با پارتیشن بندی نامتعادل

تفکیک عملکرد تفصیلی

تعداد عملیات

برای آرایه ای با اندازه n:

1. مقایسه ها:

   • بهترین حالت: n log n
   • بدترین حالت: n²/2
   • میانگین مورد: 1.386n log n

2. مبادله:

   • بهترین حالت: n log n
   • بدترین حالت: n²/2
   • میانگین مورد: 0.693n log n

جدول عملکرد

تکنیک های بهینه سازی

1. میانه از سه انتخاب محوری

fun medianOfThree(arr: IntArray, low: Int, high: Int): Int {
    val mid = (low + high) / 2
    if (arr[low] > arr[mid]) swap(arr, low, mid)
    if (arr[mid] > arr[high]) swap(arr, mid, high)
    if (arr[low] > arr[mid]) swap(arr, low, mid)
    return mid
}

1. پارتیشن بندی سه طرفه

fun quickSort3Way(arr: IntArray, low: Int, high: Int) {
    if (high <= low) return

    var lt = low
    var gt = high
    val pivot = arr[low]
    var i = low + 1

    while (i <= gt) {
        when {
            arr[i] < pivot -> swap(arr, lt++, i++)
            arr[i] > pivot -> swap(arr, i, gt--)
            else -> i++
        }
    }

    quickSort3Way(arr, low, lt - 1)
    quickSort3Way(arr, gt + 1, high)
}

مقایسه با سایر الگوریتم های مرتب سازی

مزایا و معایب QuickSort

مزایا:

• عملکرد متوسط ​​عالی کیس
• مرتب سازی در محل با حداقل حافظه اضافی
• حافظه پنهان به دلیل محل مرجع خوب
• قابل موازی سازی برای پیاده سازی های چند رشته ای

معایب:

• ناپایدار – نظم عناصر برابر را حفظ نمی کند
• عملکرد ضعیف در داده های قبلاً مرتب شده یا تقریباً مرتب شده است
• نسبت به انتخاب ضعیف محور آسیب پذیر است
• ماهیت بازگشتی می تواند منجر به سرریز پشته شود

نتیجه گیری

QuickSort یکی از کاربردی ترین و کارآمدترین الگوریتم های مرتب سازی موجود است. ترکیبی از عملکرد خوب با حروف متوسط، مرتب‌سازی در محل و کارایی حافظه پنهان آن را به انتخابی محبوب در کتابخانه‌های استاندارد بسیاری از زبان‌های برنامه‌نویسی تبدیل کرده است. در حالی که اشکالاتی دارد، بهینه‌سازی‌ها و رویکردهای ترکیبی مختلفی برای رفع این محدودیت‌ها ایجاد شده‌اند که موقعیت QuickSort را به عنوان سنگ بنای پیاده‌سازی مرتب‌سازی مدرن تثبیت می‌کند.