برنامه بازی برج های هانوی (Tower of Hanoi) به زبان پاسکال

این کد برنامه کامل "برج هانوی" می باشد. همانطور که می دانید این بازی به طوری است که سه میله و تعدادی دیسک داریم. دیسک ها به ترتیب شماره گذاری شده از پائین به بالا (و از بزرگ به کوچک) در میله اول چینده شده اند. ما باید برنامه ای بنویسیم که این دیسک ها از میله یک به میله سوم منتقل شوند (و به همین ترتیب چیده شوند) این بازی یک قانون دارد که هیچگاه یک دیسک بزرگتر نمی تواند روی یک دیسک کوچکتر قرار گیرد. این برنامه به وسیله توابع بازگشتی نوشته شده است. البته این تنها راه نوشتن این بازی نیست!

program hanoi;

var     n,i:integer;

procedure transfer(n,m1,m3,m2:integer);

          procedure diskmove(m1,m3:integer);

          begin

               writeln(i,') Move ',m1,' To ',m3); i:=i+1

          end;

begin

     if n>0 then

     begin

          transfer(n-1,m1,m2,m3);

          diskmove(m1,m3);

          transfer(n-1,m2,m3,m1);

     end

end;

begin   {main begin}

     i:=1;

     write('Enter the number of disks: ');

     readln(n);

     writeln;

     transfer(n,1,3,2);

     readln

end.

مرتب سازی درجی (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) 

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

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

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

مرتب سازی انتخابی (Selection Sort)

روش انتخابی اولین روشیه که به ذهن می رسه: بزرگترین رکورد بین رکوردهای لیست رو پیدا می کنیم و به انتهای لیست انتقال می دیم. از بقیه رکوردها بزرگترین رو انتخاب می کنیم و انتهای لیست - کنار رکورد قبلی - قرار می دیم. در این روش یک عنصر انتخاب و با تمام  عناصر مقایسه مشود  و ... مثلا :

0:  9 1 6 4 7 3 5

1:  5 1 6 4 7 3 9

2:  5 1 6 4 3 7 9

3:  5 1 3 4 6 7 9

4:  4 1 3 5 6 7 9

5:  3 1 4 5 6 7 9

6:  1 3 4 5 6 7 9

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

void selection_sort ( int arr[] , int n )

{

  register int i , j ;

  int max , temp ;

  for ( i = n - 1 ; i > 0 ; i -- )

  {

    max = 0 ;

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

      if ( arr[ max ] < arr[ j ] )

            max = j ;

            temp = arr[ i ] ;

            arr[ i ] = arr[ max ] ;

            arr[ max ] = temp ;

  }

}

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

procedure selection_sort ( var arr : array of integer ) ;

var

    i , j , max , temp : integer ;

begin

    for i := High ( arr ) downto Low ( arr ) + 1 do

    begin

        max := 0 ;

        for j := Low ( arr ) + 1 to i do

            if arr[ max ] < arr [ j ] then

                        max := arr[j] ;

                        temp := arr[ i ] ;

                        arr[ i ] := arr[ max ] ;

                        arr[ max ] := temp ;

    end ;

end ;

بررسی مرتب سازی انتخابی 

اگر تعداد رکوردها برابر n باشه ، n-1 مرحله لازم است تا تمام داده ها مرتب شوند. مرحله اول n-1 مقایسه ، مرحله دوم n-2 مقایسه ، ... و مرحله آخر 1 مقایسه انجام می گیرد. پس روی هم رفته برای مرتب کردن n رکورد به n(n-1)/2 مقایسه نیاز داریم ، که نشون میده این روش چندان مناسب نیست.

اولین عیب این روش ثابت بودن تعداد مقایسه ها و در نظر گرفتن شیوه چینش رکوردهاست. مثلا حالتی که رکوردها به طور کاملا معکوس باشند (یعنی رکورد اول بزرگترین رکورد و لیست نزولی باشه) با حالتی که لیست کاملا مرتب باشه هیچ تفاوتی نداره ، و همیشه n(n-1)/2 مقایسه باید انجام بگیره!!!

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

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

دو حلقه تکرار وجود دارد که حلقه خارجی n-1  بار (n  تعداد عناصر لیست است) و حلقه داخلی n/2 بار اجرا می شود

تعداد مقایسه = 1/2(n^2-n)

تعداد تعویض ها در بدترین حالت = n^2 / 4+3(n-1)

تعداد تعویض ها در بهترین حالت = 3(n-1)

در بهترین حالت فقطn-1  عنصر باید تغییر مکان یابد و در هر تغییر مکان نیز سه مقایسه باید انجام گیرد. لذا تعداد تعویضها در بهترین حالت برابر 3(n-1)  است. تعداد تعویضها در حالت متوسط از فرمول پیچیده ای محاسبه می شود که نتیجه آن عبارت زیر است .

 تعداد تعویضها در حالت متوسط = x(log n + y)

که در فرمول فوق y مقدار ثابتی برابر با 0/577216 است گرچه تعداد مقایسه در الگوریتم حبابی و انتخابی باهم برابر است ولی الگوریتم انتخابی روش بهتری است

مرتب سازی حبابی (Bubble Sort)

فرض کنید n داده داریم که می خواهیم به صورت صعودی مرتب شوند. عنصر اول رو با دومی مقایسه و در صورتی که اولی بزرگتر باشد جاهاشون رو عوض می کنیم. همین کار رو با عناصر دوم و سوم انجام می دهید و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تموم شد بزرگترین عنصر بین داده ها به آخر لیست می رسد. حالا یک بار دیگه از اول این کار رو انجام می دهیم اما این بار تا عنصر  (n -1)ام ادامه می دهیم (عنصر  nام مرحله اول جای خودش رو پیدا کرده). باز هم این کار رو تا عنصر  (n - 2)ام تکرار می کنیم ، و بازهم ... تا اینکه بالاخره داده ها مرتب می شوند مثلا :

0 - 0 )    5 6 4 2

1 - 1 )    5 6 4 2

1 - 2 )    5 4 6 2

1 - 3 )    5 4 2 6

2 - 1 )    4 5 2 6

2 - 2 )    4 2 5 6

3 - 1 )    2 4 5 6

مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم می شوند شش مقایسه. در کل این روش n (n - 1) / 2 مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید :

0 - 0 )    0 7 1 3 5 4

1 - 1 )    0 1 7 3 5 4

1 - 2 )    0 1 7 3 5 4

1 - 3 )    0 1 3 7 5 4

1 - 4 )    0 1 3 5 7 4

1 - 5 )    0 1 3 5 4 7

2 - 1 )    0 1 3 5 4 7

2 - 2 )    0 1 3 5 4 7

2 - 3 )    0 1 3 5 4 7

2 - 4 )    0 1 3 4 5 7

3 - 1 )    0 1 3 4 5 7

3 - 2 )    0 1 3 4 5 7

3 - 3 )    0 1 3 4 5 7

4 - 1 )    0 1 3 4 5 7

4 - 2 )    0 1 3 4 5 7

5 - 1 )    0 1 3 4 5 7

همونطور که می بینید انتهای مرحله 2 داده ها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحله ای رسیدیم که هیچ جابجایی در اون رخ نداد  نتیجه می شه که داده ها مرتب هستن )مرحله سوم). پس بعد از مرحله 3 مطمئن می شیم که داده هامون مرتب شدن و نیازی به مراحل 4 و 5 نیست.

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

void bubble_sort ( int arr [ ] , int n )

{

  register int i , j , t , c ;

  for ( i = n - 2 ; i >= 0 ; i -- )

  {

    c = 0 ;

    for ( j = 0 ; j <= i ; j ++ )

      if ( arr [ j ] > arr [ j + 1 ] )

      {

        t = arr [ j ] ;

        arr [ j ] = arr [ j + 1 ] ;

        arr [ j + 1 ] = t ;

        c ++ ;

      }

      if ( c == 0 )

        break ;

  }

}

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

procedure bubble_sort ( var arr : array of integer ) ;

var

    i , j , c , t : integer ;

begin

    for i := high ( arr ) - 1 downto low ( arr ) do

    begin

        c := 0 ;

        for j := low ( arr ) to i do

            if arr[ j ] > arr[ j + 1 ] then

            begin

                t := arr [ j ] ;

                arr [ j ] := arr [ j + 1 ] ;

                arr [ j + 1 ] := t ;

                inc ( c ) ;

            end ;

        if c = 0 then

            break ;

    end ;

end ;

بررسی مرتب سازی حبابی :

 اگر طول یک لیست ،n  فرض شود. همانطور که در الگوریتم حبابی مشاهد میگردد. دو حلقه تو در تو وجود دارد که اولین حلقه n-1  بار و دومین حلقه n/2  بار تکرار میشود      

n/2(n-1)=1/2(n^2-n) : تعداد مقایسه ها

تعداد تعویض ها در مرتب سازی حبابی :

در بهترین حالت(وقتی که لیست مرتب باشد) صفر است و در بدترین حالت( وقی که لیست به طور معکوس مرتب باشد) برابر با (n^2-n)2/3 و تعداد متوسط تعویضها برابر با (n^2-n)4/3 است. رابطه بدترین حالت به صورت زیر به دست آمده است.

تعداد مقایسه ها  =تعداد تعویضها

1/2(N^2-n)* 3     =     3/2(n^2-n)

با توجه به روابط فوق می توان گفت که الگوریتم مرتب سازی حبابی یک الگوریتم توانی است. زیرا زمان اجرای آن با مربع تعداد عناصر آن متناسب است.