خبرگزاری آیصد (جدیدترین و جذاب ترین اخبار ایران و جهان)

نشر توسط:admin Views 37 تاریخ : 2 خرداد 1395

مرتب سازی درجی(insertion sort):

1-     ابتدا ما لیستی از داده های نامرتب را به کامپیوتر داده و آن ها را در یک آرایه ذخیره می کنیم. 

 7  8  5  2  4  6  3 

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

7| 8  5  2  4  6  3       

3- در این مثال اولین عدد نامرتب 8 است.آن را با عدد سمت چپ مقایسه می کنیم و در صورت نیاز عمل swap را انجام می دهیم.سپس pointer (مرز) را یک خانه جلو می بریم.

توجه کنید که در این قسمت عدد 8 تنها با یک مقایسه به خانه مورد نظر رفت.اما در مراحل بعدی تعداد مقایسه ها یشتر می شود

  7  8| 5  2  4  6  3

حال اولین عدد مرتب نشده 5 است که با دو مقایسه به جای درست خود می رود. 

7  5 | 8 2  4  6  3       

5  7 |  8  2  4  6  3     

الان عدد 5 در جای درست خود قرار گرفته پس pointer را یک واحد جلو می بریم.

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

5  7  8 | 2  4   6   3           

2  5  7  8  |  4  6  3  

4-  حال  عددی که مورد بررسی قرار می گیرد 4 است.4 کوچکتر از 7 و 8و 5 است،ولی از 2 کوچکترنیست.در این صورت 4 مقایسه انجام شده و 3 جابه جایی صورت می گیرد.باز هم مرز(pointer)یک واحد اضافه می کنیم.

2  4  5  7  8  |  6  3    

5- در این قسمت عدد 6 با 3 مقایسه و 2 جابه جایی, در مکان درست خود قرار گرفته و با 4 و 2مقایسه نمی شود.

2  4  5  6  7  8  |  3        

6- در آخر, عدد 3 برای انکه در جای درست خود قرار بگیرد تا جایی که اعداد از آن بزرگترند پیش رفته و عمل مقایسه را انجام می دهد.

2  3  4  5  6  7  8  |         

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

void insertion_sort(int *arr, int n)
{
        int i, j, t;
 
        for(i=1; i<n; i++)
        {
                t = arr[i];
                for(j=i; j>0; j--)
                {
                        if(t>=arr[j-1])
                                break;
                        arr[j] = arr[j-1];
                }
                arr[j] = t;
        }
}

برای بدست آوردن مرتبه زمانی باید بررسی کنیم که تو هر حلقه چندتا مقایسه انجام می شود.

در بدترین حالت به همان تعداد i این حلقه انجام می شود.یعنی عدد مورد بررسی به ابتدای آرایه می رود.

a = [1, 2, 3, 4] and t = 0 => 4 compares

a = [1,2,3,…,i] and t = 0 => i compares

 نتیجاً تعداد عملیات انتساب که هر کدام مرتبه ی زمانی O(1) را دارند برابر است با:

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

  (-- for (j = i - 1; j >= 0 && t < a[j]; j

   ; [a [j + 1] = a[j

جمع تعداد مقایسه ها = 1 + 2 + 3 + … + (n-1)

                              =(n-1)n/2

پس مرتبه زمانی آن برابر است با:O(n^2)