الگوریتم های sort در c#(قسمت چهارم)

ترجمه و آماده سازی:بهنام منتظر

4-Merge sort 

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

شکل های اولیه ی پیاده سازی مرتب سازی ادغامی مجبور به استفاده از سه آرایه هستند» برای هر یک از نیمه ها یک آرایه و یکی هم برای این که لیست مرتب شده در آن ذخیره شود «.الگوریتم زیر آرایه ها را در جا ادغام می کند و در نتیجه فقط به دو آرایه نیاز است.ساختار های غیر بازگشتی هم برای مرتب سازی ادغامی وجود دارد،ولی آن ها در بیشتر دستگاه ها در بالا بردن بازده نسبت به الگوریتم های بازگشتی هیچ تاثیر مهمی نداشته اند.

مرتب سازی ادغامی در مجموعه های بزرگ اندکی سریع تر از مرتب سازی پشته ای-Heap sort- است،ولی به خاطر آرایه ی دوم به حافظه ی دو برابر نسبت به مرتب سازی پشته ای نیاز دارند.این نیاز به حافظه ی اضافی مرتب سازی ادغامی را برای بسیاری از اهداف نا مناسب می کند»مرتب سازی سریع-Quick sort-در بیش تر مواقع گزینه ی مناسب تری است و مرتب سازی پشته ای-Heap sort-برای مجموعه های خیلی بزرگ مناسب تر است».

مرتب سازی ادغامی هم مانند مرتب سازی سریع ساختار بازگشتی دارد که آن را به گزینه ای نامناسب «برای برنامه هایی که روی دستگاه هایی با حافظه محدود اجرا می شوند» تبدیل می کند.

 code
// array of integers to hold values
private int[] a = new int[100];
private int[] b = new int[100];

// number of elements in array
private int x;

// Merge Sort Algorithm
public void sortArray()
{
  m_sort( 0, x-1 );
}

public void m_sort( int left, int right )
{
  int mid;

  if( right > left )
  {
    mid = ( right + left ) / 2;
    m_sort( left, mid );
    m_sort( mid+1, right );

    merge( left, mid+1, right );
  }
}

public void merge( int left, int mid, int right )
{
  int i, left_end, num_elements, tmp_pos;

  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;

  while( (left <= left_end) && (mid <= right) )
  {
    if( a[left] <= a[mid] )
    {
      b[tmp_pos] = a[left];
      tmp_pos = tmp_pos + 1;
      left = left +1;
    }
    else
    {
      b[tmp_pos] = a[mid];
      tmp_pos = tmp_pos + 1;
      mid = mid + 1;
    }
  }

  while( left <= left_end )
  {
    b[tmp_pos] = a[left];
    left = left + 1;
    tmp_pos = tmp_pos + 1;
  }

  while( mid <= right )
  {
    b[tmp_pos] = a[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
  }

  for( i = 0; i < num_elements; i++ )
  {
    a[right] = b[right];
    right = right - 1;
  }
}

منبع:www.publicjoe.f9.co.uk

Advertisements