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

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

3-Insertion sort

سومین الگوریتم مرتب سازی که بررسی می کنیم الگوریتم مرتب سازی درجی (insertion sort) است. مرتب سازی درجی همان طور که از اسمش پیداست هر آیتم را در جای مناسب در لیست نهایی درج می کند.ساده ترین پیاده سازی این الگوریتم به 2 لیست نیاز دارد»یکی لیستی که آیتم های اولیه در آن قرار دارند و دیگری لیستی که آیتم های مرتب شده در آن قرار می گیرند».برای نگه داشتن حافظه در بیشتر جاهایی که این الگوریتم را پیاده سازی می کنند از یک مرتب سازی به جا استفاده می کنند که این گونه کار می کند که آیتم جاری را به پشت آیتم های مرتب سازی شده می برد و این جا به جایی را با عناصر قبل تا جایی ادامه می دهد که هر آیتم سر جای خودش قرار بگیرد.

تاثیر مرتب سازی درجی اندکی بیش از دو برابر مرتب سازی حبابی است .

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

 

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

// number of elements in array
private int x;

// Insertion Sort Algorithm
public void sortArray()
{
  int i;
  int j;
  int index;

  for( i = 1; i < x; i++ )
  {
    index = a[i];
    j = i;

    while( (j > 0) && (a[j-1] > index) )
    {
      a[j] = a[j-1];
      j = j - 1;
    }

    a[j] = index;
  }
}

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

Advertisements

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

  1. من این مرتب سازی رو دوست دارم منتهی گاهی یادم میره الگوریتمش

  2. thanks
    it was good and useful

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

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

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

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

تصویر توییتر

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

عکس فیسبوک

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

عکس گوگل+

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

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

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