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

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

2- Heap sort:

دومین الگوریتم مرتب سازی که به شرح آن می پردازیم heap sort یا مرتب سازی به صورت پشته ای است. heap sort به ساختارهای بازگشتی زیاد و یا آرایه های متعدد نیاز ندارد.این ویژگی heap sort را به یک گزینه ی مناسب برای مجموعه های زیاد اطلاعات تبدیل می کند.heapکلا به معنی پشته یا تپه می با شد و مرتب سازی به صورت پشته ای همان طور که از اسمش پیداست با ساختن پشته ای از مجموعه های داده ها شروع می شود، سپس بزرگترین تکه ها را حذف می کند و آن را در انتهای آرایه ی مرتب شده قرار می دهد.بعد  ازحذف بزرگترین تکه پشته را از نو می سازد و بزرگترین تکه ی باقیمانده را حذف می کند و آن را در جای خالی بعدی درانتهای آرایه مرتب شده قرار می دهد.پیاده سازی اولیه به دو آرایه نیاز دارد»یکی برای نگه داشتن پشته ها و دیگری برای نگه داشتن تکه های مرتب شده».برای انجام مرتب سازی به جا و ذخیره ی فضا به آرایه ی دوم نیاز پیدا می شود،الگوریتم زیر با استفاده از یک الگوریتم مشترک برای پشته ها و آرایه ی مرتب شده کلک زده است.هر وقت که یک آیتم(تکه) از پشته حذف می شود ،در انتهای آرایه فضایی را خالی می کند که آیتم حذف شده می تواند در آن جا ذخیره شود. تکه کد سی شارپ heap sort  به صورت زیر می باشد:

 code 

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

// number of elements in array
private int x;

// Heap Sort Algorithm
public void sortArray()
{
  int i;
  int temp;

  for( i = (x/2)-1; i >= 0; i-- )
  {
    siftDown( i, x );
  }

  for( i = x-1; i >= 1; i-- )
  {
    temp = a[0];
    a[0] = a[i];
    a[i] = temp;
    siftDown( 0, i-1 );
  }
}

public void siftDown( int root, int bottom )
{
  bool done = false;
  int maxChild;
  int temp;

  while( (root*2 <= bottom) && (!done) )
  {
   if( root*2 == bottom )
      maxChild = root * 2;
    else if( a[root * 2] > a[root * 2 + 1] )
      maxChild = root * 2;
    else
      maxChild = root * 2 + 1;

    if( a[root] < a[maxChild] )
    {
      temp = a[root];
      a[root] = a[maxChild];
      a[maxChild] = temp;
      root = maxChild;
    }
    else
    {
      done = true;
    }
  }
}

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

Advertisements

Posted on آوریل 27, 2010, in CSharp, آموزش, الگوریتم and tagged , , . Bookmark the permalink. ۱ دیدگاه.

  1. یادش بخیر ما اینو تو ساختمان داده ها داشتیم البته با سودوکد

پاسخی بگذارید

در پایین مشخصات خود را پر کنید یا برای ورود روی شمایل‌ها کلیک نمایید:

نشان‌وارهٔ وردپرس.کام

شما در حال بیان دیدگاه با حساب کاربری WordPress.com خود هستید. بیرون رفتن / تغییر دادن )

تصویر توییتر

شما در حال بیان دیدگاه با حساب کاربری Twitter خود هستید. بیرون رفتن / تغییر دادن )

عکس فیسبوک

شما در حال بیان دیدگاه با حساب کاربری Facebook خود هستید. بیرون رفتن / تغییر دادن )

عکس گوگل+

شما در حال بیان دیدگاه با حساب کاربری Google+ خود هستید. بیرون رفتن / تغییر دادن )

درحال اتصال به %s

%d وب‌نوشت‌نویس این را دوست دارند: