مرتب سازی ادغامی merge sort

برنامه: آرایه ای از اعداد را به روش ادغام، یا همان  marge sort مرتب می کند

الگوریتم : 

از دو تابع استفاده می کنیم

1 - تابع  Marge Sort یا  MS().

void ms(int arr[],int lx,int rx)

این تابع از عنصر lx تا عنصر rx آرایه ی arr[] را پردازش می کند.

 

2 - تابع sort یا sortm

void sort(int arr[],int lx,int mid1,int mid2 , int rx)

این تابع  قسمت اول آرایه ی arr یعنی lx تا mid1  و قسمت دوم یعنی mid2 تا rx  را مرتب کرده  و در آرایه  temp نتیجه را که مرتب شده ی دو قسمت فوق می باشد را ذخیره ، سپس توسط دستور زیر ، عناصر مرتب شده را در آرایه ی اصلی کپی می کند.(که mid2=mid1+1)

for(int i=0,k=lobj;i <j;i++,k++) arr[k]=temp[i];

که lobj همان lx و robj همان rx می باشد.

 

* تابع  run در کد جاوااسکریپت ،رشته ی ورودی را به یک آرایه از اعداد تبدیل می کند.

فرمت ورودی اعدا باید به صورت زیر باشد.

example : 5,2,6,4,2,3,9,8,5,

که پس از هر عددی یک "," باید وارد شود و بدون هیچ گونه فاصله ای.

 برنامه مرتب سازی ادغامی با زبان ++C

#include
#include

#define size 10

void sort(int arr[],int lx,int mid1,int mid2 , int rx)
{
   int j=0; 
   int temp[size];
   int lobj=lx,robj=rx;

   //sorting arr[lx]..arr[mid] with arr[mid2]...arr[rx] and save it in temp[]
   while( (lx <= mid1) && (mid2 <= rx) )
   {
         if (arr[lx] < arr[mid2])
        {
                temp[j++]=arr[lx++];
        }
        else{
              temp[j++]=arr[mid2++];
              }
    }
   while( mid2 <= rx)
   {
          temp[j++]=arr[mid2++];
   }
   while( lx <= mid1)
   {
            temp[j++]=arr[lx++];
   }
   //copy temp[] into the original array ( arr[] )
   for(int i=0,k=lobj;i <j;i++,k++)       arr[k]=temp[i];
  }

void ms(int arr[],int lx,int rx)
{

   if(rx > lx)
   {

          int mid1 = (lx + rx)/2;
           int mid2 = mid1+1;

          ms(arr,lx,mid1);
         ms(arr,mid2,rx);
         sort(arr,lx,mid1,mid2,rx);
   }

}

int main()
{
   int test[size] = {5,9,1,8,2,7,3,6,4,0};

   cout<<"\n Array is ";
   for(int i=0; i          cout<<" "<<test[i];

   ms(test,0,size-1);

    cout<<"\nsorted array is : ";
   for(int i=0; i          cout<<" "<<test[i];
getch();
return 0;
}

 

  برنامه مرتب سازی ادغامی با زبان #C 

 using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}

void sort(int[] arr,int lx,int mid1,int mid2 , int rx)
{
   int j=0; 
   int[] temp = new int[arr.Length];
   int lobj=lx,robj=rx;

   //sorting arr[lx]..arr[mid] with arr[mid2]...arr[rx] and save it in temp[]
   while( (lx <= mid1) && (mid2 <= rx) )
   {
          if (arr[lx] < arr[mid2])
         {
               temp[j]=arr[lx];
                j = j + 1;
                lx = lx + 1;
         }
         else{
                temp[j]=arr[mid2];
                j = j + 1;
                 mid2 = mid2 + 1;
          }
   }
   while( mid2 <= rx)
   {
          temp[j]=arr[mid2];
           j = j + 1;
           mid2 = mid2 + 1;
   }
   while( lx <= mid1)
   {
           temp[j]=arr[lx];
           j = j + 1;
           lx = lx + 1;
   }
   //copy temp[] into the original array ( arr[] )
   for(int i=0,k=lobj;i <j;i++,k++)           arr[k]=temp[i];
}


void ms(int[] arr, int lx, int rx)
{

   if(rx > lx)
   {

             int mid1 = (lx + rx)/2;
             int mid2 = mid1+1;

              ms(arr,lx,mid1);
              ms(arr,mid2,rx);
              sort(arr,lx,mid1,mid2,rx);
 }

}
private void button1_Click(object sender, EventArgs e)
{

   lbl1.Text = "Sorting ...";
   int[] test = { 0,5,2,3,1,3, 9, 0, 8, 1, 7, 2, 6, 3, 4 };
   ms(test, 0, test.Length - 1);
   lbl1.Text = "";
   for (int i = 0; i < test.Length; i++)
             lbl1.Text = lbl1.Text + test[i] + ",";
}
}
}