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

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

مرتب سازی انتخابی(selection sort)

مرتب سازی انتخابی و درجی(Selection sort & Insertion sort)

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

مرتب سازی انتخابی(selection sort) :این مرتب سازی  مفهوم ساده ای نسبت به سایر مرتب سازی ها دارد.این الگوریتم هربار کوچکترین مقدار یا بزرگترین مقدار را برداشته( بسته به اینکه اعداد را از بزرگ به کوچک یا از کوچک به بزرگ مرتب می کنید)و در ابتدای آرایه قرار می دهد.سپس عدد بزرگتر بعدی را پیدا می کند و این کار را تا زمانی که همه ی داده ها بررسی شوند انجام می دهد.

این مرتب سازی یه کوچولو از مرتب سازی حبابی ((bubble sort و modified bubble sort سریع تره.

         for(int x=0; x

         {

                 int index_of_min = x;

                 for(int y=x; y

                 {

                          if(array[index_of_min]>array[y])

                          {

                                   index_of_min = y;

                          }

                 }

                int temp = array[x];

                 array[x] = array[index_of_min];

                 array[index_of_min] = temp;

     }       

 

حلقه ی اول از 0 تا n رفته و حلقه ی بعدی از x تا n  داده ها را پیمایش می کند.مرتبه زمانی آن به طور میانگین O(n*n/2) است.  

 

 

Heap یا Merge یا Quick کدام بهتره؟

Heap Sort بهتر است یا Merge Sort  یا Quick Sort :

چه تفاوتی بین کارایی این الگوریتم ها وجود دارد؟

مرتبه زمانی این مرتب سازی ها تقریبا شبیه به هم است.پس کدام یک از آن ها نسبت به دیگری کارایی بیشتری دارد؟

یکی از ارجحیت های heap sort و merge sort نسبت به quick sort :

مرتبه ی زمانی مرتب سازی سریع (quick sort) در بدترین حالت O(n^2) است.اما در دو الگوریتم دیگر O(nlogn) است.

از ارجحیت هایی که heapSort  نسبت به MergeSort دارد این است که این الگوریتم درجا  (in place) است.یعنی از حافظه ی اضافی استفاده نمی کند.در mergesort ما نیاز به یک حافظه ی کمکی داریم تا داده ها را در آن ذخیره کنیم.

 

فرض کنید یک سری داده ی مشابه داریم که می خواهیم آن ها را مرتب کنیم.اگر این داده ها را به heapsort  دهیم مرتبه زمانی آن mergesort ، O(n) مرتبه زمانی O(logn) و مرتبه زمانی   O(n^2) ,quicksort را خواهند داشت.

از طرفی در مرتب سازی سریع از یک pivot استفاده می شود و دو قسمت ایجاد شده هر کدام به صورت بازگشتی مرتب می شوند، که اگرpivot را به درستی تعیین نکنیم(مثلا maximum pivot  یا  minimum باشد). امکان دارد بدترین حالت در مرتبه زمانی یعنی O(n^2) پیش بیاید.

Merge sort یک الگوریتم stable است، در صورتی که quick وunstable ,heap  هستند.

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

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

یکی از ساده ترین مرتب سازی هایی که ترم اول به بچه های کامپیوتر یاد می دن مرتب سازی حبابی است.در این الگوریتم از ابتدای آرایه شروع کرده و هر دو جفت عدد کنار هم, با هم مقایسه شده و در صورت نیاز جابه جا می شوند.و این کار  تا آخر ادامه می یابد. در واقع هر بار بزرگترین مقدار را از بین داده ها پیدا کرده و در انتها قرار می دهیم.این مرتب سازی از دوتا حلقه ی for تشکیل شده. حلقه ی بیرونی شمارنده ای است که هر بار یک عدد را برای مقایسه با بقیه ی اعداد انتخاب کرده و بزرگترین را به جای درست خود می برد.حلقه ی for درونی نیز شمارنده ایست که عمل مقایسه عدد با سایر اعداد را انجام می دهد.

for(int x=0; x

	{

for(int y=0; y

		
if(array[y]>array[y+1]);
{	int temp = array[y+1];
	array[y+1] = array[y];

array[y] = temp;

}    }}

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

n مقایسه صورت می گیرد.

مرتبه زمانی این الگوریتم در بهترین حالت و بدترین حالت:O(n^2)

مرتب سازی حبابی با کمی تغییر(modified bubble sort):

بهترین نسخه ی الگوریتم مرتب سازی حبابی یک flag دارد.این flag  در صورتی که عمل swap بین جفت عدد انجام شود true  شده و در صورتی که swap انجام نشود flag  false می شود.false  بودن flag به این معناست که عمل  sort  پایان یافته و دیگر نیاز نیست تا انتهای آرایه داده ها را پیمایش کنیم.

در این صورت در بهترین حالت مرتبه ی زمانی الگوریتم O(n) می شود.

 

void bubblesort2 (int *a,int n)}    int temp,swap;    for( int i = 0 ; i < n - 2 ; i++ )   { swaps=0;        for ( int j = 0 ; j < n - 1 ; j++ )        {            if ( a[j] > a[j + 1] )            {                temp = a[j];                a[j] = a[j + 1];                a[j + 1] = temp;                swaps++;            }        }        if( swaps == 0 )        {            break;   end of if//    { end of outer for// { end of function// { 

از تفاوت های الگوریتم فلوید و دایجسترا

  از تفاوت های الگوریتم فلوید و دایجسترا :در الگوریتم Dj یک گره با سایر گره ها مقایسه می شود.ولی در الگوریتم فلوید هر بار یک گره مبدا می شود.

اگر تعداد گره ها زیاد باشد، الگوریتم فلوید کاراترست.اما اگر تعداد گره ها کم است، الگوریتم Dj بهتر کار می کند.

وجود چند دستور با مرتبه زمانی (O(1 در الگوریتم Dj باعث شده که در حالت گره های زیاد نتوان از آن ها چشم پوشی کرد.نتیجاً برای گراف هایی با گره های زیاد این الگوریتم کارایی خوبی ندارد.

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

توجه کنید که در یک گراف با n گره در الگوریتم فلوید n مقایسه بیهوده(مقایسه یال کشیده شده از یک گره به خودش) با مرتبه ی زمانی(O(1 صورت می گیرد.

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

 باز هم تاکید می کنم اگر مرتبه زمانی الگوریتم فلوید(O(n^3 است فقط به خاطر این است که برای هر جفت گره کوتاهترین مسیر مشخص می شود.

 

الگوریتم دایجسترا یا دیکسترا

الگوریتم دایجسترا یا دیکسترا :این الگوریتم هم یکی از الگوریتم های پیمایش گراف است که مسئله ی کوتاهترین مسیر از مبداء واحد را برای گراف های وزن داری که یال با وزن منفی ندارند، را حل می کند.

در این الگوریتم یک گره  مثلا گره شماره ی یک به عنوان مبداء تعیین شده سپس این گره با همه ی یال های(i) مقایسه شده و وزن یال مرتبط با گره یک در [D[i قرار می گیرد.سپس برای هر گرهV حلقه ی for تکرار می شود.

([D[w]=min(D[w],D[v]+L[v,w

این الگوریتم مشابه الگوریتم پریم، برای بدست آوردن درخت پوشای مینیمم،می باشد.در صورتی که گراف یال با وزن منفی داشته باشد، این الگوریتم درست کار نمی کند و می بایست از الگوریتم های دیگر نظیر بلمن-فورد اگرچه مرتبه ی زمانی بیشتری دارند استفاده کرد.

مرتبه زمانی:

O(n^2)

 

الگوریتم کوتاهترین مسیر به روش فلوید

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

الگوریتم فلوید:در این الگوریتم هر بار یک گره به عنوان مبداء، یک گره به عنوان واسط و یک گره به عنوان مقصد تعیین می شود.این الگوریتم از سه حلقه ی for تودرتو تشکیل شده.حلقه ی for بیرونی شمارنده ای برای گره ی واسط است.حلقه ی for  درون آن شمارنده ای برای گره مبداء و حلقه ی درونی آن نیز شمارنده ای برای گره مقصد است.

برای مثال اگر قرار است از از نود 3 با واسط نود2 به نود5 برویم،مینیمم وزن یال های (2،5)+ (3,2)و(3،5)به عنوان وزن یال(3،5) قرار می گیرد.

[(C(i,j)=Min[C(i,j),c(i,k)+c(k,j

حال اگر قرار باشد نقطه(3،6) با واسط 5 را بررسی کنیم

[(C(3,6)=min[c(3,6),c(3,5)+c(5,6

در این صورت مقدار (c(5,3  از قبل مشخص شده حال چه با واسط چه بی واسط.

بررسی مرتبه زمانی الگوریتم:

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

O(n^3)

مرتب سازی توده ای یا کپه(Heap Sort):

 

مرتب سازی توده ای  یا کپه(Heap Sort):

برای بررسی این نوع از مرتب سازی ابتدا باید با درختheap آشنا شویم.

درخت Heap:یک درخت دودویی تقریباً کامل است،درخت Max Heap وMin Heap

درخت max heap:در این درخت هر نود یا گره از فرزندانش بزرگتر یا مساویست.

 

 

درخت Min heap:در این درخت هر نود یا گره از فرزندانش کوچکتر یا مساوست.

در مرتب سازی توده ای داده ها را در یک درخت heap min قرار داده  هر بار مقدار موجود در ریشه ی درخت را برداشته و آخرین گره قرار داده شده در درخت را جایگزین آن می کنیم.با این کار آرایش درخت heap به هم خورده و باید دوباره درخت heap را به روز کنیم.این کار را(برداشتن اعداد) آنقدر انجام می دهیم تا همه ی داده ها یکی یکی به جای ریشه قرار بگیرند.این گونه داده ها از بزرگ به کوچک از درخت heap خارج شده و در یک حافظه قرار می گیرند.  

توجه:در درخت heap max یافتن بیشترین مقدار و در درخت min heap یافتن کمترین مقدار بسیار آسان است.

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

در این صورت داده ها به ترتیب در آرایه قرار می گیرند.مسلماً اولین خانه ی آرایه مقدار ریشه را داراست.فرزند سمت چپ و سمت راست به ترتیب در خانه هایی با ایندکس2i و2i+1 قرار می گیرند.

خانه ی صفرم آرایه را خالی بگذارید تا رابطه ی بین ایندکس ها به هم نخورد.در این صورت ایجاد درخت heap آسان می شود.

 

توجه : شکل بالا یک درخت heap min است.که نحوه ی قرارگیری داده ها در آرایه را نشان می دهد.نحوه ی مرتب سازی را نمایش نمی دهد.

بررسی مرتبه ی زمانی این الگوریتم در بهترین و بدترین حالت:

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

بررسی مرتبه زمانی:

فرض کنید یک درخت max heap داریم.مسلماً بزرگترین عدد در ریشه قرار گرفته.آن عدد را برمی داریم و آخرین نود را جایگزین آن می کنیم.حال باید دوباره درخت خود را heap کنیم. بدترین حالت زمانی رخ می دهد که طی مقایسه ی عدد قرار گرفته در ریشه با سایر نودها،عدد(ریشه) در پایین ترین سطح درخت قرار بگیرد.پس اگر ارتفاع درخت1-[(log(n+1] باشد،تعداد مقایسه های انجام شده logn است.نتیجاً برای nنود تعداد کل مقایسه ها nlogn است.

توجه:مبنای لگاریتم دو است.

مرتبه ی زمانی:

(θ(nlogn

heapsort.zip">دانلود

مرتب سازی با ادغام(Merge sort ):

مرتب سازی با ادغام(Merge sort ):

مرتب سازی با ادغام یک نمونه از الگوریتم های تقسیم و غلبه(Divide-and-Conquer)است.مرتبه ی زمانی این الگوریتم در بدترین حالت نسبت به الگوریتم مرتب سازی درجی رشد کمتری دارد، و علت آن به اساس الگوریتم که تقسیم و غلبه است بر می گردد.

ابتدا داده ها را به دو قسمت تقسیم می کنیم.سپس برای  هر مجموعه از داده ها این کار را انجام می دهیم.این کار را آنقدر انجام می دهیم تا هر داده در یک مجموعه ی جداگانه قرار بگیرد.

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

ادغام(Combine):فرض کنید دو بسته کارت مرتب شده دارید که این بسته ها از بالا به پایین به ترتیب از کوچک به بزرگ قرار داده اید.در این صورت برای ادغام این بسته کارت ها به طوری که بسته ی جدید هم مرتب باشد باید هر بار کارت های دو بسته را با هم مقایسه کرده و هرکدام کوچکتر بود را در بسته ی جدید قرار دهیم.این کار را آنقدر انجام می دهیم تا یکی از بسته ها تمام شود.در این صورت کارت های بسته ی دیگر را بدون تغییر چیدمانشان به بسته ی کارت جدید اضافه می کنیم.  

                    

بررسی مرتبه ی زمانی در بهترین حالت:همان طور که از شکل معلوم است می توان داده ها را با درخت نمایش داد.

بهترین حالت زمانی رخ می دهد که وقتی دو آرایه به طول n/2 را با هم ادغام می کنیم تعداد مقایسه ها n/2 باشد.یعنی داده ها مرتب باشند.در این صورت است که بعد از n/2 مقایسه ایندکس یکی از آرایه ها به آخر رسیده و n/2 داده ی دیگر بدون مقایسه در آرایه ی جدید قرار می گیرند.

پس تعداد مقایسه ها در هر سطح درخت به صورت زیر می باشد:    

T(n)=n/2+n/4+n/8+…=nlogn(1/2+1/4+1/8+…)=(n/2)logn

Result: (nlogn)                                                                                                                             

توجه :ارتفاع درخت برابر است با لگاریتم تعداد نودها:logn                               نود                                                                            

مرتبه زمانی در بدترین حالت: بدترین حالت زمانی رخ می دهد که وقتی دو آرایه به طولn/2 را با هم ادغام می کنیم تعداد مقایسه ها nباشد.در این صورت تعداد مقایسه ها در هر سطح درخت به صورت زیر می باشد:

T(n)=n+n/2+n/4+…=nlogn(1+1/2+1/4+…)=(n)logn

Result: O(nlogn)

نتیجاً مرتبه ی زمانی در حالت متوسط نیز برابر (ϴ (nlogn می باشد.چرا که میانگین بهترین حالت و بدترین حالتnlogn می شود.

توجه:در مرتب سازی با ادغام علاوه بر آرایه ای برای دخیره ی داده ها به یک آرایه ی دیگر برای ذخیره ی داده های مرتب شده نیاز داریم.(حافظه ی کمکی)

  مقایسه ای بین الگوریتم مرتب سازی درجی(Insertion Sort) و ادغامی(Merge Sort) :

مرتب سازی درجی در بدترین حالت مرتبه ی زمانی n^2 را داشته که در مقایسه با مرتب سازی با ادغام با مرتبه زمانی (O(nlognکندتر است. تغییر n به logn کاهش بسیار خوبی است.اگر چه باید اضافه کرد که برای داده های کم، الگوریتم درجی نسبت به ادغامی کاراتر بوده و سرعت بالاتری دارد.اما برای داده های زیاد بر عکس است.چرا که رشد nlogn نسبت به n^2  کمتر است.

محاسبه ی مرتبه زمانی الگوریتم با ادغام از طریق فرمول  (T(n)=L T(n/b)+ g(n :

در این فرمول (g(n  جمع مرتبه زمانی تقسیم داده ها و ادغام داده هاست.

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

در مرتب سازی با ادغام b=2 و همه ی زیر مسئله های ایجاد شده بررسی می شوند.

(g(n نیز در این ا لگوریتم برابر n است. چرا که تقسیم مسئله به دو قسمت مرتبه زمانی(O(1 دارد و ادغام هر زیر مسئله نیز در بدترین حالت(O(n است.

پس تابع بازگشتی بدست آمده: T(n)=2T(n/2)+n