روش مرتب‌سازی درجی (Insertion Sort) یکی از روش‌های مقدماتی مرتب‌سازی مبتنی بر مقایسه عناصر است که در مقایسه با روش‌های دیگر بیشتر مورد توجه قرار دارد.

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

عملکرد این الگوریتم به گونه‌ای است که در پایان هر مرحله قسمتی از داده‌ها به صورت کامل مرتب هستند. در مرحله بعدی نیز داده‌ای از میان داده‌های غیرمرتب به این قسمت مرتب وارد شده و در محل مناسب درج می‌شود. اگر بخواهیم با روش مرتب‌سازی درجی لیست اعداد زیر را به صورت صعودی (کوچک به بزرگ) مرتب ‌کنیم، در پایان هر مرحله ترتیب عناصر به صورت زیر خواهد بود:

  

0)    5 1 2 7 3 6

  

1)    1 5 2 7 3 6

2)    1 2 5 7 3 6

3)    1 2 5 7 3 6

4)    1 2 3 5 7 6

5)    1 2 3 5 6 7

  

پیاده‌سازی مرتب‌سازی درجی

  [برگرد بالا]

الگوریتم مرتب‌سازی درجی به زبان‌های برنامه‌نویسی ++C و Python برای مرتب کردن عناصر آرایه‌ای از اعداد صحیح به صورت زیر پیاده‌سازی می‌شود:

  

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;

  }

}

  

def insertion_sort(arr):

    for i in range(1, len(arr)):

        t = arr[i]

         for j in range(i, 0, -1):

             if t >= arr[j - 1]:

                 break

             arr[j] = arr[j - 1]

        arr[j] = t  

  

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

  

5 1 2 7 3 6

  

در مرحله اول i = 1 و t = 1 است:

  

j = 1:    5 5 2 7 3 6

       :    1 5 2 7 3 6

  

در مرحله دوم i = 2 و t = 2 است:

  

j = 2:    1 5 5 7 3 6

j = 1:    1 5 5 7 3 6

       :    1 2 5 7 3 6

  

در مرحله سوم i=3 و t = 7 است:

  

j = 3:    1 2 5 7 3 6

       :    1 2 5 7 3 6

  

در مرحله چهارم i = 4 و t = 3 است:

  

j = 4:    1 2 5 7 7 6

j = 3:    1 2 5 5 7 6

j = 2:    1 2 5 5 7 6

       :    1 2 3 5 7 6

  

و در مرحله پنجم i = 5 و t = 6 است:

  

j = 5:    1 2 3 5 7 7

j = 4:    1 2 3 5 7 7

       :    1 2 3 5 6 7

  

در پایان لیست مرتب شده است.

  

پیچیدگی زمانی مرتب‌سازی درجی

  [برگرد بالا]

بدترین حالت این الگوریتم زمانی اتفاق می‌افتد که لیست به صورت معکوس مرتب باشد. در این حالت حلقه داخلی در مرحله اول یک بار، در مرحله دوم دو بار، در مرحله سوم سه بار و در حالت کلی در مرحله iام (i < n) به تعداد i بار تکرار می‌شود. پس اگر $ T(n) $ تعداد مقایسه‌های حلقه داخلی به ازای n عنصر را نشان دهد، می‌توان نوشت:

  

\[T(n) = 1 + 2 + 3 + ... + (n - 1) = \frac{ n (n - 1)}{ 2 } \approx \frac{ n^2}{ 2} \]

  

که از مرتبه اجرای $ Θ(n^2)$ است.

بهترین حالت الگوریتم زمانی است است که لیست از پیش مرتب شده باشد. در این حالت هر حلقه درونی با یکبار مقایسه خاتمه پیدا می‌کند. در نتیجه تعداد کل مقایسه‌ها از مرتبه $ Θ(n) $ خواهد بود.

حالت متوسط برای شرایطی که عناصر به صورت تصادفی پخش شده باشند محاسبه می‌شود. در این حالت در هر تکرار حلقه بیرونی، حلقه داخلی برای یافتن محل مناسب درج عنصر جدید به طور میانگین نصف لیست مرتب شده را پیمایش می‌کند. در نتیجه حدود $ \frac{n^2}{4} $مقایسه صورت خواهد گرفت (چرا؟). این تعداد اگرچه از مرتبه اجرای $ Θ(n^2) $ است، اما در مقایسه با بدترین حالت (تقریبا $\frac{n^2}{2} $ مقایسه) عملکرد بهتری را نشان می‌دهد.

  

ویژگی‌های مرتب‌سازی درجی

  [برگرد بالا]

1- پیچیدگی زمانی الگوریتم مرتب‌سازی درجی در بدترین حالت و حالت متوسط $ \theta (n^2) $ و در بهترین حالت $ \theta(n) $ است.

2- یکی از ویژگی‌های مهم مرتب‌سازی درجی این است که در حالت متوسط برای درج عنصر جدید در لیست مرتب شده نیاز به مقایسه عنصر با تمامی عناصر ندارد. به همین دلیل کارآیی آن در مقایسه با بدترین حالت بهتر است. از سوی دیگر، این روش برای مرتب کردن عناصر به جای عمل جابجایی - که نیاز به سه عمل اصلی مقداردهی دارد - از کپی کردن استفاده می‌کند. در این روش ابتدا مقدار عنصر جدید در یک متغیر کمکی (در قطعه کد فوق متغیر t) ذخیره شده و جابجا کردن عناصر بزرگتر به انتهای لیست با یک عمل اصلی انجام می‌گیرد. در انتها نیز مقدار عنصر جدید در محل مناسب درج می‌شود. در چنین حالتی تعداد اعمال اصلی انچام شده کمتر از تعداد اعمال مورد نیاز در عمل جابجایی است. به همین دلیل این روش به روش‌های مقدماتی دیگر (مانند روش مرتب‌سازی حبابی و انتخابی) ارجحیت داشته و در مراحل نهایی مرتب‌سازی‌های پیشرفته (مانند روش مرتب‌سازی سریع) از این روش به عنوان روش مرتب‌سازی جایگزین استفاده می‌شود. اگر تعداد عناصر لیست کمتر از بیست عنصر باشد، این روش در مقایسه بار روش‌های متداول مرتب‌سازی سریعتر عمل می‌کند.

3- حافظه مصرفی مرتب‌سازی درجی از مرتبه $ \theta(1) $ بوده و مستقل از اندازه لیست است. چنین الگوریتمی را مرتب‌سازی درجا گویند.

4- در صورتی که مرتب‌سازی درجی به صورت قطعه کد فوق پیاده‌سازی شود، یک مرتب‌سازی پایدار خواهد بود. یعنی ترتیب عناصر با مقادیر یکسان در حین مرتب‌سازی تغییر نمی‌کند. اما اگر به جای شرط [t >= arr[j - 1 از شرط [t > arr[j - 1 استفاده شود، الگوریتم ناپایدار خواهد شد.

مسعود اقدسی فام

مسعود اقدسی فام هستم.

دانش‌آموخته‌ی علوم کامپیوتر و فعال حوزه‌های علم داده و یادگیری ماشین؛ علاقه‌مند به یاد دادن و یاد گرفتن :)

algs.ir/spgwext     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
نوشته‌ها از این دست
آخرین نوشته‌ها
       ✦   الگوریتم آنلاین
نوشته‌های پرمخاطب
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک (محرمانه):

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• mahboobeh
سه‌شنبه، ۲۳ آبان ماه ۱۳۸۵، ساعت ۱۵:۳۰

ba salam

man mikhastam ye barnameh benevisam

 moshakhasate chand ta az daneshjoyan ra begirad va be ma namayesh dahad

va vaghti shomareye daneshjoye yeki az danehsjyan ra midahim moshakhaste oon daneshjo ra be ma neshan dahad.

mishe lotf konid in barnameh ra ba c++barye injaneb benevisid ya inke rahnemaye konid?

ba tashakor

• علي
چهارشنبه، ۲۴ آبان ماه ۱۳۸۵، ساعت ۰۹:۰۲

با سلام . لينك شما هم در سايت قرار گرفت . با تشكر

• peyman
چهارشنبه، ۲۴ آبان ماه ۱۳۸۵، ساعت ۰۹:۰۲

salam

vaghti mikham in ketab ro download konam hamoontor ke shoma goftid be tore khodkar ba akrobat baz mikone

chikar konam ke mostaghim download kone?

mamnoon

• حسین
چهارشنبه، ۲۴ آبان ماه ۱۳۸۵، ساعت ۱۳:۱۶

سلام

خسته نباشی مسعود جان.

فکر کنم اگه در حلقه دوم شرط مساوی بودن با t  رو  برداری بهینه تر باشه :

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

• hoda
چهارشنبه، ۲۴ آبان ماه ۱۳۸۵، ساعت ۱۴:۲۴

lotfan barye ma barnameye c++ra derone saitetann biyavaridd

مسعود اقدسی فام
چهارشنبه، ۲۴ آبان ماه ۱۳۸۵، ساعت ۱۴:۵۷

محبوبه خانم ، شما امكاناتي رو كه مي شه استفاده كرد مشخص نكردين. ساختمان؟ آرايه؟ ليست پيوندي؟

به هر حال كار زياد سختي نيست. شما برنامه رو بنويسيد هر جا به مشكل بر خورديد من در خدمتم.

علي جان ، ممنون از لطفت.

پيمان خان ، براي دانلود كتابهاي حجيم مثل مورد شما بهتره از نرم افزار هاي مخصوص دانلود مثل DAP يا IDM استفاده بشه.

حسين جان ، حق با شماست. مي شه بهينه ترش كرد.

هدي خانم ، منظورتون رو متوجه نشدم.

• محمد
پنجشنبه، ۲۵ آبان ماه ۱۳۸۵، ساعت ۰۳:۱۵

لینک شدی

موفق باشی

• رخ
یکشنبه، ۲۸ آبان ماه ۱۳۸۵، ساعت ۰۹:۴۶

با سلام

اگه یک مقدار مطالب بیشر در باره ریاضیلت و کاربرد آۀن در کامپیوتر داشته باشه خیلیی خوب میشه

• maryam
سه‌شنبه، ۱۹ دی ماه ۱۳۸۵، ساعت ۱۷:۱۰

salam   proje  to   proje  shode   veblageton

• سارا
جمعه، ۲۵ اسفند ماه ۱۳۸۵، ساعت ۲۳:۱۴

با سلام

باتشکر از مطالب مفیدی که ارائه داده اید لطفاً روالی برای مرتب سازی درجا با مرتبه پیچیدگی 1 در سایت قرار دهید . همچنین روال پارتیشن را درسایت قرار دهید و ثابت کنید که این روال نمی توانددر زمانی کمتر از n بر قرار باشد .

• سارا
جمعه، ۲۵ اسفند ماه ۱۳۸۵، ساعت ۲۳:۱۵

در ضمن من چندین بار برای شما پیغام فرستادم اما متاسفانه نرسیده لطفا در این مورد کمکم کنید .

• سارا
دوشنبه، ۶ فروردین ماه ۱۳۸۶، ساعت ۲۲:۳۷

با سلام

من الان چند روزی میشه که براتون پیغام گذاشتم ولی مثل اینکه هنوز وقت نکردید پاسخ بدید لطفاً اگر میشه جواب روال پارتیشن و روال درجا را در سایت بگذارید با تشکر

مسعود اقدسی فام
سه‌شنبه، ۷ فروردین ماه ۱۳۸۶، ساعت ۰۰:۲۳

سارا خانم!

معذرت می خوام که جوابتون رو دیر می دم. متاسفانه نمی تونم در این مورد کمکی بهتون بکنم.

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

موفق باشید.

• عباس
چهارشنبه، ۱۶ خرداد ماه ۱۳۸۶، ساعت ۲۳:۴۵

سلام خسته نباشيد

     روش مرتب سازي درجي در برنامه نويسي ويژال بيسيك را اگه ممكنه به ايميلم بفرستيد

• ستايش
جمعه، ۱ تیر ماه ۱۳۸۶، ساعت ۱۹:۲۲

سلام  خسته نباشيد

لطفا پياده سازي مرتب سازي مبنا با ليست پيوندي به ايميلم بفرستيد.خيلي فوري ازتون خواهش مي كنم

• alale
جمعه، ۲۳ آذر ماه ۱۳۸۶، ساعت ۱۵:۰۷

سلام خسته نباشید

پیاده سازی مرتب سازی heap sort  رو میخوام به زبان پاسکال(اگه ممکنه به ایمیلم بفرستین-خیلی حیاتیه)

ممنونم

• sara
یکشنبه، ۱۴ بهمن ماه ۱۳۸۶، ساعت ۲۱:۴۸

salam.man aslan barnam nvisi balad nisam.khastam az site shoma komak begiam vali ghesmate amozeshi nadidam.mishe mano ar estefade az sit rahnamai konid?

• سجاد
پنجشنبه، ۱۶ خرداد ماه ۱۳۸۷، ساعت ۲۰:۵۷

سلام

خسته نباشین می خواستم اگه براتون زحمتی نیست پیاده سازی درخت رو هم توضیح بدین البته تو پاسکال

مرسی

• zahrazohre
جمعه، ۳۱ خرداد ماه ۱۳۸۷، ساعت ۰۱:۳۸

salam ma in code ha ro ke dar file ejraei migzarim  va run mikonim ejra nemishan lotfan code haye bedoone khata gharar bedid lazem darimba tashakor

مسعود اقدسی فام
جمعه، ۳۱ خرداد ماه ۱۳۸۷، ساعت ۲۲:۵۰

زهره و زهرا خانم

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

• fatme
جمعه، ۲۳ اسفند ماه ۱۳۸۷، ساعت ۲۰:۰۷

salam  

man raveshe darji ro be che sorat bazgashti benevisam

mitonid komakam konid

en doroste:mamnon misham komakam konid

insert sort(a ,i. j)                                                                j  

                                                                                          }

                                                                                       if  i==j    return 1

                                                                                                      insert sort(a,i,j)

                                                                                                                           [  if   x[i]>x[i+1

                                                                                                                                     ( swap(xi,xi+1

• bahareh
سه‌شنبه، ۲۲ اردیبهشت ماه ۱۳۸۸، ساعت ۱۴:۰۸

salam

mikhastam in barname haro be zabane vb baram benevisid  

mamnonam

مسعود اقدسی فام
سه‌شنبه، ۲۲ اردیبهشت ماه ۱۳۸۸، ساعت ۱۵:۱۲

سلام بهاره خانم

ای کاش قبل ار ارسال پیام نکاتی رو که تذکر داده شده مطالعه می کردید.

• الناز
یکشنبه، ۲۹ مرداد ماه ۱۳۹۱، ساعت ۲۰:۱۹

مرسي خيلي مفيد بود من داشتم مي خوندمش از روي الگوريتم گيج شدم اما با توضيحاتي كه قسمت اول دادين و مثالي كه با اعداد زدين متوجه شدم.

خيلي خيلي تشكر01

• صمد
دوشنبه، ۴ دی ماه ۱۳۹۱، ساعت ۰۲:۱۲

08130301مرسی خیلی ممنون عالی بود داشتم آماده میکردم با پاور پوینت ببرم برای استاد که گفتن وقتش دیروز بود تموم شد !!

هی خداااا07

• صمد
دوشنبه، ۴ دی ماه ۱۳۹۱، ساعت ۰۲:۱۴

08130301مرسی خیلی ممنون عالی بود داشتم آماده میکردم با پاور پوینت ببرم برای استاد که گفتن وقتش دیروز بود تموم شد !!

www.sami-chat.ir

هی خداااا07

• نجم الدین
دوشنبه، ۲ اردیبهشت ماه ۱۳۹۲، ساعت ۰۹:۵۵

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

واقعا دستتون درد نکنه03

• منا
سه‌شنبه، ۱۰ اردیبهشت ماه ۱۳۹۲، ساعت ۱۸:۴۲

خیلی ممنون عالی بود

• علی
دوشنبه، ۴ آذر ماه ۱۳۹۲، ساعت ۱۵:۱۵

تشکر

• دوست عزیز
یکشنبه، ۱۱ اسفند ماه ۱۳۹۲، ساعت ۱۱:۴۵

صد باریک12121212121212

• یلدا
چهارشنبه، ۱۹ شهریور ماه ۱۳۹۳، ساعت ۱۰:۰۵

عالللللللللللللللللللییییییییییییی بود   تشکر06

• زانیا
چهارشنبه، ۲۳ فروردین ماه ۱۳۹۶، ساعت ۰۸:۱۴

0909090909

• شوگو
چهارشنبه، ۲۳ فروردین ماه ۱۳۹۶، ساعت ۰۸:۱۵

10101010101010

• amir
دوشنبه، ۱۹ آذر ماه ۱۳۹۷، ساعت ۱۰:۵۱

عالی بود

ممنون

• pooya
یکشنبه، ۹ تیر ماه ۱۳۹۸، ساعت ۱۶:۳۵

سلام،در مقابله با برخی از طراحی هاو الگوریتم ها حتی همین الگوریتم های مقدماتی مثل مرتب سازی درجی یا سری فیبونانچی و... تا زمانی که جواب رو مشاهده نکردم نمیتونم اونجور که باید برنامه رو پیاده سازی کنم(کدنوشتن بلدم فقط در طراحی الگوریتم مشکل دارم) یعنی احساس می کنم خط ومشی کلی برنامه ریزی یک الگوریتم نو رو بلد نیستم درصورتی که در حوزه الگوریتم تا به حال چندین فیلم و به صورت پراکنده کتاب دیدم و بررسی کردم(البته به غیر از کتاب معروف  introduction to algorithm clrs که فقط چندصفحه اولش رو خواندم)04حال از شما می پرسم آیا الگوریتم نوشتن یک خط و مشی وترتیب خاصی داره که باید رعایت بشه؟

یعنی وقتی کسی درخواست حل مسئله رو ازماداره درهمان ابتدا میتوان گفت یا حدس زد این مسئله چند متغیر نیاز داره؟چندحلقه باید به کاربرده بشه؟چندتا دستورشرطی میخوادو... .

آیا درکتاب هایی که تابحال خودتان بررسی کردید اینجوری آموزش داده شده؟

یا مثلا اینجور الگوریتم های مقدماتی رو به صورت حفظی میخوانید؟ اگر اینطور نیست پس چطور مسئله رو خرد می کنید و راهبردهایش رو پیدا می کنید؟

لطفا به صورت کلیشه ای پاسخ ندید و اگرهم منبعی(ترجیحا فارسی ولی اگرهم انگلیسی بود اشکالی ندارد)سراغ دارید معرفی کنید و هرکمک وتجربه ای دراین رابطه داریدلطفا بیان کنید.