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

ترجمه و آماده سازی: بهنام منتظر
7-Shell sort:
بالاخره نوبت به هفتمین الگوریتم مرتب سازی(هفتمین خوان) رسید.مرتب سازی لایه ای یک مرتب سازی است که با کاهش رشد یا همان ارتقا کار می کند و در واحد های برنامه نویسی خام بیشتر به عنوان مرتب سازی شانه ای شناخته شده است. این الگوریتم با پیمایش های متعدد بر روی لیست کار می کند و در هربار پیمایش مجموعه داده هایی با اندازه های یکسان را به وسیله ی مرتب سازی درجی مرتب می کند.با هر پیمایش که در لیست صورت می گیرد مجموعه ی داده های مرتب شده بیشتر و بیشتر می شود تا مجموعه شامل کل لیست شود.(هر چه اندازه مجموعه ها بیشتر شود ، تعداد مجموعه هایی که باید مرتب شوند کمتر می شود.)

آیتم هایی که در هر مجموعه هستند ترجیحا به هم متصل نیستند،اگر n مجموعه داشته باشیم هر مجموعه از آیتم های n تا در میان تشکیل شده است.به عنوان مثال اگر 3 مجموعه داریم مجموعه ی اول شامل المان هایی است که در مکان های 1، 4، 7 و … قرار دارند.مجموعه ی دوم شامل المان هایی است که در مکان های 2، 5، 8و… قرار دارند.و مجموعه ی سوم شامل المان هایی است که در مکان های 3، 6، 9 و… قرار گرفته اند. اندازه ی مجموعه هایی که برای هر تکرار استفاده می شوند تاثیر اساسی بر بازده مرتب سازی دارد.

مرتب سازی لایه ای 5 برابر سریع تر از مرتب سازی حبابی است و اندکی بیش از دو برابر مرتب سازی درجی ( نزدیک ترین) رقیبش است. مرتب سازی لایه ای از مرتب سازی ادغامی ،پشته ای و سریع عمدتا آهسته تر است ولی الگوریتم ساده ی مرتبت به آن ،آن را به گزینه ای مناسب برای مرتب سازی لیست ها با آیتم های کمتر از 5000 تا «به غیر از جاهایی که سرعت خیلی مهم است «تبدیل کرده است.همچنین برای مرتب سازی های تکراری با آیتم های کمتر بسیار مناسب است.

تکه کد سی شارپ الگوریتم مرتب سازی لایه ای به صورت زیر است:

 code

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

// number of elements in array
private int x;

// Shell Sort Algorithm
public void sortArray()
{
  int i, j, increment, temp;

  increment = 3;

  while( increment > 0 )
  {
    for( i=0; i < x; i++ )    

     {       j = i;       temp = a[i];      

       while( (j >= increment) && (a[j-increment] > temp) )
      {
        a[j] = a[j - increment];
        j = j - increment;
      }

      a[j] = temp;
    }

    if( increment/2 != 0 )
    {
      increment = increment/2;
    }
    else if( increment == 1 )
    {
      increment = 0;
    }
    else
    {
      increment = 1;
    }
  }
} 

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

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

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

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

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

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

تصویر توییتر

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

عکس فیسبوک

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

عکس گوگل+

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

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

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