Question

الگوریتم merge sort به چه شکل کار می کنه؟ کد سی پلاس پلاس رو هم می خواستم

Answer 1

یه روش تقسیم و حل برای sort کردنه ...

بهترین نیست ولی دو نوع خودش خوبه ...

/* Helper function for finding the max of two numbers */
int max(int x, int y)
{
    if(x > y)
    {
        return x;
    }
    else
    {
        return y;
    }
}

/* left is the index of the leftmost element of the subarray; right is one
 * past the index of the rightmost element */
void merge_helper(int *input, int left, int right, int *scratch)
{
    /* base case: one element */
    if(right == left + 1)
    {
        return;
    }
    else
    {
        int i = 0;
        int length = right - left;
        int midpoint_distance = length/2;
        /* l and r are to the positions in the left and right subarrays */
        int l = left, r = left + midpoint_distance;

        /* sort each subarray */
        merge_helper(input, left, left + midpoint_distance, scratch);
        merge_helper(input, left + midpoint_distance, right, scratch);

        /* merge the arrays together using scratch for temporary storage */ 
        for(i = 0; i < length; i++)
        {
            /* Check to see if any elements remain in the left array; if so,
             * we check if there are any elements left in the right array; if
             * so, we compare them.  Otherwise, we know that the merge must
             * use take the element from the left array */
            if(l < left + midpoint_distance && 
                    (r == right || max(input[l], input[r]) == input[l]))
            {
                scratch[i] = input[l];
                l++;
            }
            else
            {
                scratch[i] = input[r];
                r++;
            }
        }
        /* Copy the sorted subarray back to the input */
        for(i = left; i < right; i++)
        {
            input[i] = scratch[i - left];
        }
    }
}

/* mergesort returns true on success.  Note that in C++, you could also
 * replace malloc with new and if memory allocation fails, an exception will
 * be thrown.  If we don't allocate a scratch array here, what happens? 
 *
 * Elements are sorted in reverse order -- greatest to least */

int mergesort(int *input, int size)
{
    int *scratch = (int *)malloc(size * sizeof(int));
    if(scratch != NULL)
    {
        merge_helper(input, 0, size, scratch);
        free(scratch);
        return 1;
    }
    else
    {
        return 0;
    }
}

 

Answer 2

یه راه حل، برای افراد مبتدی مثل خودم:

فرض کنید ما میخوایم آرایه ی A رو سورت کنیم. میایم اون رو به دو قسمت نصف میکنیم و اون دو قسمت رو سورت میکنیم. بعد با تابع ادغام کننده، اون 2 تا رو که مرتب کردیم، با هم ادغام میکنیم تا آرایه ی سورت شده مون به دست بیاد. برای اطلاعات بیشتر میتونید کتاب Introduction to Algorithm از Cormen رو بخونید(pdf ش هست)

بگذریم، حالا کد با کامنت فارسی :د

//آ و ب ادغام میشن و توی آرایه ی سی ذخیره میشن
//ام و ان، سایز آرایه های بی و اِی هستن
void Merger(int *A, int *B, int n, int m, int *C) 
//تابع ادغام کننده ی دو آرایه که با توجه به کوچک بودن و یا بزرگ بودن اعضای اون
//کار میکنه
{
    int t=0;
    int s=0;
    for(int i=0; i<n+m; i++)
    {
        if(t>=n)
        {
            C[i]=B[s];
            s++;
        }
        else if(s>=m)
        {
            C[i]=A[t];
            t++;
        }
        else
        {
            if(A[t]<B[s])
            {
                C[i]=A[t];
                t++;
            }
            else
            {
                C[i]=B[s];
                s++;
            }
        }
    }
}

void Sorter(int *A, int size_)
//این تابع، تابع بازگشتی سورت کردنمون هست
{
    if(size_==1)
        return;
    int X[size_/2], Y[(size_+1)/2];
    
    /*
    این حلقه نیمه ی اول آرایه را در ایکس و نیمه ی دوم را در ایگرگ
    ذخیره میکند
    */

    for(int i=0; i<size_; i++)
    {
        if(i<size_/2)
            X[i]=A[i];
        else
            Y[i-size_/2]=A[i];
    }
    //در این پایین، ابتدا نیمه ی اول سورت میشود، سپس نیمه ی دوم سورت میشود
    Sorter(X, size_/2);
    Sorter(Y, (size_+1)/2);
    //در این جا هم دو نیمه ی سورت شده با هم ادغام میشوند
    Merger(X, Y, size_/2, (size_+1)/2, A);
}