الگوریتم مرتب سازی سریع Quick Sort چیست؟ — به زبان ساده + کد پیاده سازی

پیاده‌سازی الگوریتم QuickSort با پایتون

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

nums = [7, 3, 1, 9, 4, 6]
sorted_nums = quicksort(nums)
print(sorted_nums)

توضیح کد

در این پیاده‌سازی، تابع quicksort به‌صورت بازگشتی تعریف شده است. ابتدا بررسی می‌شود که اگر طول آرایه کمتر یا مساوی ۱ باشد، همان آرایه بازگردانده شود (چون نیازی به مرتب‌سازی نیست). سپس اولین عنصر آرایه به عنوان Pivot انتخاب می‌شود. با استفاده از لیست‌های درک (List Comprehension)، دو لیست جدید ساخته می‌شود: less شامل عناصر کوچکتر یا مساوی Pivot، و greater شامل عناصر بزرگتر از آن. در نهایت، تابع به‌صورت بازگشتی روی این دو لیست فراخوانی می‌شود و نتیجه به‌صورت: quicksort(less) + [pivot] + quicksort(greater) بازگردانده می‌شود. این کد بسیار ساده و قابل فهم است اما به دلیل ایجاد لیست‌های جدید، از حافظه بیشتری نسبت به نسخه‌ی in-place استفاده می‌کند.

پیاده‌سازی الگوریتم QuickSort به زبان C

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // انتخاب عنصر آخر
    int i = (low - 1);

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// تست الگوریتم
int main() {
    int arr[] = {9, 4, 6, 2, 8, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);

    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

توضیح کد

در این پیاده‌سازی، الگوریتم QuickSort به‌صورت in-place و بازگشتی طراحی شده است. در ابتدا، با استفاده از تابع partition، الگوریتم یک عنصر را به عنوان Pivot انتخاب می‌کند و آرایه را به دو قسمت تقسیم می‌کند: قسمت اول شامل عناصری است که از Pivot کوچک‌تر یا برابرند و قسمت دوم شامل عناصری است که بزرگ‌تر از Pivot هستند. سپس، با استفاده از بازگشت، هر قسمت به‌طور مستقل مرتب می‌شود. از آنجا که این پیاده‌سازی نیازی به استفاده از حافظه اضافی (جز حافظه‌ای که برای آرایه‌ها استفاده می‌شود) ندارد، برای محیط‌های محدود به‌ویژه در سیستم‌های سطح پایین بسیار کارآمد است. همچنین، استفاده از زبان C که به‌دلیل کار با حافظه و عملکرد بالا شناخته می‌شود، این الگوریتم را برای برنامه‌های پردازش سریع و بهینه بسیار مناسب می‌سازد.

 پیاده‌سازی الگوریتم مرتب سازی سریع به زبان Java

public class QuickSort {

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // انتخاب عنصر آخر
        int i = (low - 1);

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);
        return i + 1;
    }

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 4, 6, 2, 8, 1, 5};

        quickSort(arr, 0, arr.length - 1);

        System.out.print("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

توضیح کد

در پیاده‌سازی Java، الگوریتم QuickSort به‌صورت مشابه با C، به‌صورت in-place و بازگشتی طراحی شده است. با این تفاوت که در این پیاده‌سازی از ویژگی‌های زبان شیءگرایی (Object-Oriented) برای مدیریت بهتر کد و استفاده از متدهای استاتیک بهره‌برداری شده است. تابع partition همانند نسخه‌ی C عمل می‌کند و با انتخاب Pivot، آرایه را به دو بخش تقسیم کرده و سپس آن را به ترتیب مرتب می‌کند. این پیاده‌سازی در محیط‌های توسعه‌ی نرم‌افزار شیءگرا و پروژه‌های بزرگ‌تر مناسب است، زیرا کد مرتب‌تر و قابل‌نگهداری‌تر است. همچنین استفاده از زبان Java که در دنیای نرم‌افزارهای تجاری و اپلیکیشن‌های بزرگ محبوب است، این پیاده‌سازی را برای پروژه‌های مقیاس‌پذیر مناسب می‌سازد.

مزایا و معایب الگوریتم مرتب‌ سازی سریع (Quicksort)

الگوریتم مرتب‌ سازی سریع (Quicksort) به‌عنوان یکی از محبوب‌ترین الگوریتم‌های مرتب‌سازی، مزایا و معایب خاص خود را دارد. در اینجا به بررسی این مزایا و معایب می‌پردازیم:

• عملکرد کارآمد: الگوریتم Quicksort در بهترین حالت و حالت میانگین دارای پیچیدگی زمانی O(nlogn) است، که آن را بسیار سریع‌تر از دیگر الگوریتم‌های مرتب‌سازی می‌کند.
• استفاده کم از حافظه: Quicksort به‌عنوان یک الگوریتم در محل (In-place) شناخته می‌شود، به این معنی که نیازی به فضای اضافی برای ذخیره آرایه مرتب ندارد و معمولاً فقط به فضای O(logn) برای ذخیره‌سازی پشته نیاز دارد.
• سهولت در پیاده‌سازی: پیاده‌سازی Quicksort در زبان‌های برنامه‌نویسی مختلف بسیار ساده و قابل فهم است، که آن را برای برنامه‌نویسان تازه‌کار و حرفه‌ای جذاب می‌کند.
• کارایی با داده‌های تصادفی: این الگوریتم برای داده‌های تصادفی بسیار سریع و کارآمد عمل می‌کند، زیرا پیچیدگی آن به انتخاب پیوت بستگی دارد و در حالت تصادفی احتمال وقوع حالات بدترین به حداقل می‌رسد.
• پتانسیل بهینه‌سازی: Quicksort به راحتی می‌تواند با روش‌های مختلفی مانند انتخاب تصادفی پیوت، تغییر در انتخاب پیوت (مثل انتخاب میانه سه عنصر) و استفاده از دیگر الگوریتم‌ها در زیرآرایه‌های کوچک بهینه‌سازی شود.

معایب

• بدترین حالت زمان: در بدترین حالت، که معمولاً زمانی رخ می‌دهد که آرایه مرتب یا معکوس مرتب شده باشد، زمان اجرای الگوریتم به O(n²) افزایش می‌یابد. این مورد به دلیل انتخاب نامناسب پیوت رخ می‌دهد.
• عدم پایداری: Quicksort یک الگوریتم ناپایدار (Unstable) است، که بدان معناست که ترتیب عناصر با مقادیر مشابه در خروجی باید حفظ نشود. این ویژگی می‌تواند در برخی مواقع، مانند مرتب‌سازی داده‌ها با ویژگی‌های خاص، مشکل‌ساز باشد.
• عمیق‌ترین بازگشت و خطا در پشته: در بدترین حالت، عمق بازگشت تابع می‌تواند به O(n) برسد، که این موضوع خطر ایجاد بحران حافظه (Stack Overflow) را به همراه خواهد داشت، به ویژه در زبان‌هایی که استفاده زیادی از پشته دارند.
• نیاز به انتخاب پیوت مناسب: کارایی این الگوریتم به انتخاب پیوت مناسب وابسته است. اگر پیوت به‌درستی انتخاب نشود (به عنوان مثال، همیشه اولین یا آخرین عنصر)، عملکرد آن به‌طرز قابل توجهی کاهش می‌یابد.
• پیچیدگی در پیاده‌سازی پیشرفته: اگرچه پیاده‌سازی پایه‌ای Quicksort ساده است، پیاده‌سازی بهینه‌تر با روش‌هایی مانند دسته‌بندی سه‌گانه یا انتخاب تصادفی پیوت می‌تواند پیچیده‌تر باشد و نیاز به دقت بیشتری داشته باشد.
• سازگاری با داده‌های تقریبا مرتب: اگر داده‌ها تقریباً مرتب باشند، Quicksort ممکن است نسبت به الگوریتم‌های دیگر مانند الگوریتم مرتب سازی ادغامی یا الگوریتم مرتب سازی درجی عملکرد ضعیف‌تری داشته باشد، به‌خصوص زمانی که مرتب‌سازی به سرعت مورد نیاز باشد.

کاربرد الگوریتم مرتب سازی سریع

الگوریتم مرتب‌ سازی سریع (Quicksort) یکی از محبوب‌ترین و کارآمدترین الگوریتم‌های مرتب‌سازی است که در بسیاری از زمینه‌ها و کاربردهای مختلف مورد استفاده قرار می‌گیرد. در زیر به برخی از مهم‌ترین کاربردهای این الگوریتم اشاره می‌کنیم:

۱. مرتب‌سازی داده‌ها: پایه‌ای‌ترین کاربرد Quicksort مرتب‌سازی داده‌ها در آرایه‌ها یا لیست‌ها است. این الگوریتم به‌ویژه برای داده‌های بزرگ و نامنظم بسیار مؤثر است.

۲.  پردازش داده‌های بزرگ: در برنامه‌های تحلیل داده‌ها که نیاز به مرتب‌سازی با حجم بالایی از اطلاعات دارند، مانند پایگاه‌های داده، استفاده از Quicksort می‌تواند باعث افزایش سرعت پردازش شود.

 ۳. جستجو: در صورت مرتب‌سازی یک مجموعه داده با استفاده از Quicksort، می‌توان از جستجوی دودویی (Binary Search) برای یافتن عناصر در آن مجموعه استفاده کرد که بسیار سریع‌تر از جستجوی خطی است.

۴. تحلیل عملکرد: در تحقیقات الگوریتمی و علوم داده، Quicksort به عنوان یک مثال کلاسیک از الگوریتم‌های مرتب‌سازی با تقسیم و حل (Divide and Conquer) برای نشان دادن تکنیک‌های بهینه‌سازی الگوریتم‌ها مورد استفاده قرار می‌گیرد.

۵. کتابخانه‌های زبان‌های برنامه‌نویسی: بسیاری از زبان‌های برنامه‌نویسی، از جمله پایتون، ++C و Java، از الگوریتم Quicksort به عنوان یکی از روش‌های پیش‌فرض برای مرتب‌سازی استفاده می‌کنند.

 ۶. الگوریتم‌های ترکیبی: در الگوریتم‌های دیگر، مانند QuickSelect (برای پیدا کردن kامین عنصر) و استراتژی‌های ترکیبی که از مرتب‌سازی سریع به‌عنوان بخشی از فرآیند خود استفاده می‌کنند، کاربرد دارد.

سخن آخر