بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین 20 Quera

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسأله‌ی انتخابات

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مرتب‌سازی درجی - الگوریتمستان
الگوریتمستان
6214.405.00
  »  

       

آشنایی با روش مرتب‌سازی درجی، همراه با قطعه کد به زبان برنامه‌نویسی ++C

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «مرتب سازی درجی» مهر ماه 1385 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


آنچه در این نوشته می‌خوانید:

روش مرتب‌سازی درجی (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 برای مرتب کردن عناصر آرایه‌ای از اعداد صحیح به صورت زیر پیاده‌سازی می‌شود:

      

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];
    }
10     arr[j] = t;
11   }
12 }

  

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

      

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 استفاده شود، الگوریتم ناپایدار خواهد شد.


این نوشته آخرین بار در تاریخ جمعه، ۸ خرداد ماه ۱۳۹۴ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
        آشنایی با روش مرتب‌سازی سریع، همراه با قطعه کدهای نمونه به زبان برنامه‌نویسی ++C
        آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C
        آشنایی با روش مرتب‌سازی انتخابی،همراه با قطعه کد به زبان برنامه‌نویسی ++C
        آشنایی با روش مرتب‌سازی هرمی (Heap Sort)
        آشنایی با روش مرتب‌سازی حبابی و بحث در مورد عملکرد آن، با قطعه کد به زبان برنامه‌نویسی ++C
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» شوگو

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

» زانیا

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

» یلدا

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

» دوست عزیز

یکشنبه، ۱۱ اسفند ماه ۱۳۹۲، ساعت ۱۱:۴۵
صد باریک12121212121212

» علی

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

» منا

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

» نجم الدین

دوشنبه، ۲ اردیبهشت ماه ۱۳۹۲، ساعت ۰۹:۵۵
خیلی ممنون که مطالب خوب و مفیدی در مورد الگوریتم ها در این سایت گذاشتید
واقعا دستتون درد نکنه03

» صمد

دوشنبه، ۴ دی ماه ۱۳۹۱، ساعت ۰۲:۱۴
08130301مرسی خیلی ممنون عالی بود داشتم آماده میکردم با پاور پوینت ببرم برای استاد که گفتن وقتش دیروز بود تموم شد !!

www.sami-chat.ir
هی خداااا07

» صمد

دوشنبه، ۴ دی ماه ۱۳۹۱، ساعت ۰۲:۱۲
08130301مرسی خیلی ممنون عالی بود داشتم آماده میکردم با پاور پوینت ببرم برای استاد که گفتن وقتش دیروز بود تموم شد !!

هی خداااا07

» الناز

یکشنبه، ۲۹ مرداد ماه ۱۳۹۱، ساعت ۲۰:۱۹
مرسي خيلي مفيد بود من داشتم مي خوندمش از روي الگوريتم گيج شدم اما با توضيحاتي كه قسمت اول دادين و مثالي كه با اعداد زدين متوجه شدم.
خيلي خيلي تشكر01