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

از ویکی‌پدیا، دانشنامهٔ آزاد.

مثالی ار مرتب‌ساز درجی که یک لیست از اعداد تصادفی را مرتب می‌کند.

مرتب‌ساز درجی (Insertion Sort) یک الگوریتم مرتب‌سازی ساده بر مبنای مقایسه است. این الگوریتم برای تعداد داده‌های زیاد، کارآمد نیست و در این موارد، الگوریتم‌های بهتری مثل مرتب‌ساز سریع، مرتب‌ساز ادغامی و مرتب‌ساز پشته وجود دارد؛ اما این الگوریتم، بعضی مزایا هم دارد:

• پیاده‌سازی آن راحت است.
• برای داده‌های کم، کارآمدتر است.
• برای مجموعه داده‌هایی که تقریباً به صورت مرتب شده هستند، کارآمد است: اگر تعداد وارونگی‌ها، d باشد، این الگوریتم دارای زمان اجرای (O(n + d خواهد بود.
• در عمل از بسیاری از الگوریتم‌های (O(n² مثل مرتب‌ساز انتخابی یا مرتب‌ساز حبابی، بهتر عمل می‌کند: متوسط زمان اجرای آن، n²/4 است که در بهترین حالت، خطی است.
• پایدار است. (ترتیب نسبی عناصر یکسان را حفظ می‌کند.)
• درجا است. (حافظه اضافی ثابت، (O(1 لازم دارد.)
• یک الگوریتم برخط است. یعنی یک لیست را به محض دریافت کردن، مرتب می‌کند.

[ویرایش] الگوریتم

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

معمول‌ترین نسخه از این الگوریتم که روی آرایه‌ها عمل می‌کند، به این صورت است:

1. فرض کنید یک تابع به اسم Insert داریم که که داده را در بخش مرتب شده در ابتدای آرایه درج می‌کند. این تابع با شروع از انتهای سری شروع به کار می‌کند و هر عنصر را به سمت راست منتقل می‌کند تا وقتی که جای مناسب برای عنصر جدید پیدا شود. این تابع این اثر جانبی را دارد که عنصر دقیقاً بعد از بخش مرتب شده را رونویسی می‌کند.
2. برای اعمال مرتب‌ساز درجی، از انتهای سمت چپ آرایه شروع می‌کنیم و با صدا زدن تابع insert، هر عنصر را به موقعیت درستش می‌بریم. آن بخشی که عنصر فعلی را در آن می‌کنیم، در ابتدای آرایه و در اندیس‌هایی است که آنها را قبلاً آزمایش کرده‌ایم. هر بار صدا زدن تابع insert، یک عنصر را رونویسی می‌کند، اما این مسئله مشکلی ایجاد نمی‌کند، زیرا این داده، همانی است که الان در حال درج آن هستیم.

یک شبه‌کد ساده از الگوریتم به صورت زیر است که در اینجا آرایه‌ها از صفر شروع می‌شوند و حلقه for هم دارای هر دو کران بالا و پایین است (مثل پاسکال):

insertionSort(array A)
    for i = 1 to length[A]-1 do
        value = A[i]
        j = i-1
        while j >= 0 and A[j] > value do
            A[j + 1] = A[j]
            j = j-1
        A[j+1] = value

[ویرایش] ورودی‌های خوب و بد

بهتری حالت زمانی است که آرایه از قبل مرتب شده باشد. در این حالت زمان اجرای الگوریتم از (O(n است: در هر مرحله اولین عنصر باقیمانده از لیست اولیه فقط با آخرین عنصر لیست مرتب شده مقایسه می‌شود. این حالت بدترین حالت برای مرتب‌ساز سریع (غیرتصادفی و با پیاده‌سازی ضعیف) است که زمان (O(n² صرف می‌کند. بدترین حالت این الگوریتم، زمانی است که آرایه به صورت معکوس مرتب شده باشد. در این حالت هر اجرای حلقه داخلی، مجبور است که تمام بخش مرتب شده را بررسی کرده و انتقال دهد. در این زمان اجرای الگوریتم، مثل حالت متوسط، دارای زمان اجرای (O(n² است که باعث می‌شود استفاده از این الگوریتم برای مرتب‌سازی تعداد داده‌های زیاد، غیرعملی شود. گرچه حلقه داخلی مرتب‌ساز درجی، خیلی سریع است و این الگوریتم را به یکی از سریع‌ترین الگوریتم‌های مرتب‌سازی، برای تعداد داده‌های کم (معمولاً کمتر از 10)، تبدیل می‌کند.

[ویرایش] مقایسه با دیگر الگوریتم‌های مرتب‌سازی

[ویرایش] نسخه‌های مختلف

[ویرایش] منبع

ویکی‌پدیای انگلیسی