مرتب سازی درجی (Insertion Sort)

یکی از روشهای مرتب سازی رایج و البته نه چندان کارا محسوب می شه. این روش در مقایسه با مرتب سازی حبابی و انتخابی سرعت بهتری داره و برای مرتب کردن تعداد کمی از عناصر مناسبه. به همین خاطر مراحل انتهایی روشهای مرتب سازی پیشرفته مثل مرتب سازی سریع (Quick Sort) با کمک گرفتن از این روش انجام می گیره.

الگوریتم مرتب سازی درجی بر اساس مرتب سازیهایی که معمولا خود ما بصورت دستی انجام می دیم طراحی شده. فرض کنید دسته کارتی با شماره های 1 تا 10 بصورت نامرتب و کنار هم روی زمین چیده شدن:

5  2  9  3  1  10  4  6  8  7

کارت دوم رو نسبت به کارت اول در جای مناسب خودش قرار می دیم:

2  5  9  3  1  10  4  6  8  7

حالا نوبت به کارت سوم می رسه. این کارت رو نسبت به دو کارت قبلی در جای مناسب قرار می دیم. چون 9 در مقایسه با 2 و 5 جای درستی داره بدون هیچ جابجایی به کارت چهارم می رسیم. جای این کارت رو نسبت به سه کارت قبلی مشخص می کنیم:

2  3  5  9  1  10  4  6  8  7

و به همین ترتیب تا آخر ادامه می دیم.

اگه n تعداد عناصر رو مشخص کنه ، این روش n-1 مرحله رو برای مرتب کردن  طی می کنه. بعد از اتمام مرحله i ام مطمئنا i+1 عنصر اول به صورت مرتب شده هستن این مساله یکی از حسنهای مرتب سازی درجی محسوب می شه: در هر مرحله حتما قطعه ای از عناصر مرتب شده هستن. مرتب سازی حبابی این ویژگی رو نداره.

پیاده سازی (مرتب سازی درجی) در c++

void insertion_sort ( int arr[ ] , int n )

{

  register int i , j , t ;

  for ( i = 1 ; i < n ; i++ )

  {

    t = arr[ i ] ;

    for ( j = i ; j > 0 && arr[ j - 1 ] >= t ; j-- )

      arr[ j ] = arr[ j - 1 ] ;

    arr[ i ] = t ;

  }

}

پیاده سازی (مرتب سازی درجی) در پاسکال

procedure insertion_sort ( arr : array of integer ) ;

var

    i , j , t : integer;

begin

    for i := 1 to high ( arr ) do

    begin

        t := arr[ i ] ;

        j = i ;

        while ( j > low ( arr ) ) and ( arr[ j - 1 ] >= t ) do

        begin

            arr[ j ] = arr[ j - 1 ] ;

            dec ( j ) ;

        end ;

        arr[ i ] = t ;

    end ;

end ;

بررسی مرتب سازی درجی

بر خلاف الگوریتم مرتب سازی حبابی و انتخابی ، در الگوریتم درج تعداد مقایسه ها به وضعیت اولیه لیست بستگی دارد . اگرلیست مرتب باشد، تعداد مقایسه ها برابر با n-1  واگرلیست مرتب نباشد، تعداد مقایسه برابر با 1/2(N^2+n)-1   و در حالت متوسط برابر با 1/4(N^2+n-2) است و تعداد تعویضها در حالات مختلف عبارتند از:

در بهترین حالت  :2(n-1) 

در حالت متوسط : 1/4 (n^2-9n-10)

در بدترین حالت  :1/2(n2 +3n-4) 

 بدترین حالت روش مرتب سازی درج ، از بدترین حالات مرتب سازی حبابی بدتر است ولی حالت متوسط آن کمی بهتر می باشد. به هر حال الگوریتم مرتب سازی درج دارای و مزیت است :

 اولا : یک الگوریتم طبیعی است . یعنی اگر لیست مرتب باشد ساده تر عمل می کندو اگر لیست نا مرتب باشد(مثلا به طور معکوس مرتب باشد) تعداد مقایسه ها و تعویضها بیشتر خواهد بود. این خاصیت باعث میشود که الگوریتم درج در مواقعی که لیست نسبتا مرتب  باشد مفید واقع می شود.

 ثانیا :  در مورد مقادیر مساوی ، عمل تعویض را انجام نمی دهد . یعنی اگر لیستی  بر اساس دو مقدار مرتب باشد . پس از انجام عمل مرتب سازی ، این ترتیب در هر دو مقدار باقی می ماند