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

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

5-Quick sort:

پنجمین الگوریتم مرتب سازی که مورد بررسی قرار می دهیم الگوریتم مرتب سازی سریع است .مرتب سازی سریع یک الگوریتم مرتب سازی به شدت بازگشتی جایگزین است که ابتدا جدا می کند و سپس مرتب می کند.یک فرد معمولی ممکن است بگوید مسلما این نوع مرتب سازی سریع تر است. الگوریتم  مرتب سازی سریع در ظاهر ساده به نظر می رسد ولی برای تبدیل به کد کار بسیار مشکلی در پیش است.

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

1- اگر یک المان و یا کمتر برای مرتب شدن در آرایه وجود داشته باشد،سریعا بر می گردد.

2-یک المان را از آرایه بر می دارد و به عنوان نقطه ی محوری قرار می دهد.»معمولا از المانی که در سمت چپ سایر المان ها قرار دارد استفاده می شود»

3-آرایه را به دو قسمت تقسیم می کند»یکی با مقادیر بزرگتر از نقطه ی محوری و دیگری با مقادیر کوچکتر از نقطه ی محوری».

4-به طور بازگشتی الگوریتم را برای دو نیمه دیگر تکرار می کند

مرتب سازی سریع به مراتب سریع تر از سایر الگوریتم های مرتب سازی معمول است.ممکن است برای هدف خاص  بتوان الگوریتمی نوشت که  در برخی مجموعه های

داده از مرتب سازی سریع «quick sort» سریع تر باشد ولی در حالت کلی مرتب سازی گزینه ی سریع تری وجود ندارد.

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

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

 code

// array of integers to hold values

private int[] a = new int[100];

// number of elements in array

private int x;

// Quick Sort Algorithm

public void sortArray()

{

  q_sort( 0, x-1 );

}

public void q_sort( int left, int right )

{

  int pivot, l_hold, r_hold;

  l_hold = left;

  r_hold = right;

  pivot = a[left];

  while( left < right )  
     {   
          while( (a[right] >= pivot) && (left < right) )

    {

      right--;

    }

    if( left != right )

    {

      a[left] = a[right];

      left++;

    }

    while( (a[left] <= pivot) && (left < right) )

    {

      left++;

    }

    if( left != right )

    {

      a[right] = a[left];

      right--;

    }

  }

  a[left] = pivot;

  pivot = left;

  left = l_hold;

  right = r_hold;

  if( left < pivot )   
      {    
          q_sort( left, pivot-1 ); 
      }  
  if( right > pivot )
  {

    q_sort( pivot+1, right );

  }

}

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

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

  1. یادمه موقع که ساختمان داده داشتم با حسابی با پیاده سازی این الگوریتم درگیر بودم ….D:

  1. بازتاب: الگوریتم های sort در c#(قسمت پنجم) – وبلاگ دانشجویان نرم افزار

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

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

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

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

تصویر توییتر

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

عکس فیسبوک

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

عکس گوگل+

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

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

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