در این مطلب می خواهیم به شما بگوییم می توان برای بهینه سازی الگوریتم Merge-sort از Insertion-sort کمک گرفت!

سوال: چطور می توان برای بهینه سازی الگوریتمی که ((O(nlg(n است از الگوریتم دیگری که (O(n^2 است استفاده کرد؟

جواب: الگوریتم (اصلی) Merge-sort حافظه سربار زیادی دارد (استفاده از آرایه کمکی). و بازگشتی بودن الگوریتم آن هم کمی هزینه زمانی اضافه روی دست ما می گذارد! اما Insertion-sort بدون استفاده از حافظه های کمکی و فقط با ایجاد حلقه روی آرایه و مقایسه ها کار می کند. ولی به هر حال الگوریتم آن از درجه (O(n^2 است. پس بیایید هر کدام را برای تعدادی از ورودی های مختلف اجرا کنیم و ببینیم کدام مزیت و کدام عیب برای چه تعداد ورودی برگ برنده میشوند؟!

زمان اجرا برای آرایه مرتب شده:

زمان اجرا برای آرایه مرتب شده به صورت معکوس:

زمان اجرا برای آرایه ای که ترتیب عتاصر آن به صورت تصادفی است:

ما در مورد آرایه ای که قرار است مرتب کتیم نه خوش بین هستیم نه بدبین! پس به جدول سوم توجه می کنیم. می بینید که برای آرایه ای با ۱۰۰ عنصر که ترتیب آن ها به نسبت یکدیگر تصادفی است، Insertion-sort در زمان کمنری آرایه را مرتب می کند. در حقیقت درجه های زمانی، نمایش هزینه الگوریتم برای تعداد بسیار زیاد ورودی (میل به سوی بی شمار) هستند. اما این که Insertion-sort برای چه تعداد ورودی از Merge-sort سریعتر است به مشخصه های مختلفی بسنگی دارد؛ به طور مثال به نحوه پیاده سازی الگوریتم ها، حافظه کش پردازنده و توزیع نامرتبی عناصر. اما تجربه من ثابت کرده است که حداقل برای ۱۰ عنصر، Insertion-sort سریعتر عمل می کند. خبر خوب این است که در چند روز آینده برنامه ای برای اندازه گرفتن زمان اجرای هر تابعی که دوست دارید را در قالب یک مطلب روی وبسایت می آید!

خیلی خوب! امیدوارم قانع شده باشید! روش کار به این صورت است که در الگوریتم Merge-sort هنگامی که طول تکه های آرایه در هر فراخوانی کمتر از مقدار مشخصی شد به جای ریز ریز کردن دوباره آن تکه، از Insertion-sort بهره می گیریم و مرتب کردن آن بخش را به این الگوریتم می سپاریم. مقدار مشخص را شما و به نسبت طول آرایه ای که برای مرتب سازی به Merge-sort می فرستید مشخص می کنید.

برویم سراغ کد نویسی!

ابتدا الگوریتم Insertion-sort با کمی تغییر؛ تغییرات هم به این صورت که این الگوریتم فقط بخشی از آرایه را که محدوده آن با min و max مشخص شده را مرتب می کند.

void insertionSort(int array[], int min, int max)
{
    int key ;
    // we loop through all elements in the original array from the min + 1 element
    for (int j = min + 1 ; j <= max ; j++)
    {
        // store the current element as the key
        key = array[j] ;
        // get the element just before the current element
        int i = j - 1 ;
        // loop through all elements from the key to the min element
        // check if the current element is smaller than the key
        while (i >= min && array[i] > key)
        {
            // we move the current element backward
            array[i+1] = array[i] ;
            i-- ;
        }
        // we finally move the key
        array[i+1] = key ;
    }
}

سپس الگوریتم Merge-sort با کمی تغییر؛ تغییرات هم به این صورت که شرط خاتمه طوری نوشته می شود که وقتی اندازه تکه ای که در مرحله تقسیم و در آن عمق باید مرتب شود، به اندازه مشخصی که توضیح داده شد رسید، مرتب سازی آن به عهده Insertion-sort باشد.

در ضمن آن مقدار (طول) مشخص هم به الگوریتم فرستاده می شود.

void mergeSort(int array[], int min, int max, int threshold)
{
    // prerequisite
    if ( (max - min + 1) <= threshold )
    {
        insertionSort(array, min, max);
    }
    else
    {
        // get the middle point
        int mid = (max+min) / 2;
        
        // apply merge sort to both parts of this
        mergeSort(array, min, mid, threshold);
        mergeSort(array, mid+1, max, threshold);
        
        // and finally merge all that sorted stuff
        merge(array, min, max, mid) ;
    }
}

void merge(int array[], int min, int max, int mid)
{
    int firstIndex = min;
    int secondIndex = mid + 1;
    int * tempArray = new int [max + 1];
    
 
    // While there are elements in the left or right runs
    for (int index = min; index <= max; index++) {
        // If left run head exists and is <= existing right run head.
        if (firstIndex <= mid && (secondIndex > max || array[firstIndex] <= array[secondIndex]))
        {
            tempArray[index] = array[firstIndex];
            firstIndex = firstIndex + 1;
        }

        else
        {
            tempArray[index] = array[secondIndex];
            secondIndex = secondIndex + 1;
        }
            
    } 
    
    // transfer to the initial array
    for (int index = min ; index <= max ; index++)
        array[index] = tempArray[index];
}

و در آخر هم تابع main برای تست برنامه!

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;


int main()
{
    const int threshold = 10;
    const int size = 100;
    int array[size];

    srand(time(NULL));

    //Populating array
    for (int i = 0 ; i < size  ; i++)
       array[i] = rand() % size;
    
    mergeSort(array, 0, size - 1, threshold);

    //Printing array
    for (int i = 0; i < size - 1; i++){
       cout << array[i] << " ," ;
    }

    return 0;
}

مثالی از خروجی برنامه: