یادداشت کامل الگوریتم

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

Insertion Sort

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

نوعالگوریتمدستهمرتب‌سازیسطحپایهپیچیدگی معمولO(n²)

جواب کوتاه و حرفه‌ای

اول این مفهوم را در ذهن نگه دار

توضیح ساده

چطور کار می‌کند؟ ساده و مرحله‌ای

مثل مرتب کردن کارت‌ها در دست است.

به‌طور کلی O(n²) است ولی روی ورودی کوچک یا تقریباً مرتب خوب عمل می‌کند و stable است.

روند اجرا

الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان

ببین هر pass/partition/merge چه بخشی را قطعی می‌کند.

ناحیه‌ای را که دیگر نهایی شده دنبال کن.

تعداد comparison، swap/move و حافظه اضافه را تحلیل کن.

یک مثال کوچک برای فهم بهتر

یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مرتب‌سازی درجی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.

پیاده‌سازی خوانا با JavaScriptJavaScript

function insertionSort(input) {
  const a = [...input];
  for (let i = 1; i < a.length; i++) {
    const value = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > value) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = value;
  }
  return a;
}

این کد را چطور بخوانی؟

syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.

پیچیدگی

O(n²)

این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.

چه زمانی استفاده کنیم؟

موارد مناسب

انتخاب را بر اساس اندازه داده، میزان مرتب بودن، بازه key، stable بودن و محدودیت حافظه انجام بده.

اشتباهات رایج

کجا معمولاً اشتباه می‌کنیم؟

فقط Average Big-O را مقایسه نکن.
stability، in-place بودن، عمق recursion و فرض‌های مربوط به domain را فراموش نکن.

در مصاحبه چطور توضیح بدهیم؟

مدل یک پاسخ حرفه‌ای

به عملکرد خوب روی داده تقریباً مرتب اشاره کن و بگو گاهی در hybrid sortها برای partitionهای کوچک استفاده می‌شود.

مسئله→ایده اصلی→Invariant / State→Big-O→Trade-off

چند سؤال مصاحبه‌ای سریع

مرتب‌سازی درجی چه مسئله‌ای را حل می‌کند؟

درباره Complexity چه چیزی باید بگویم؟

پیچیدگی معمول اینجا O(n²) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.

رایج‌ترین اشتباه چیست؟

فقط Average Big-O را مقایسه نکن.

موضوعات مرتبط برای ادامه مطالعهStable SortIn-place SortDivide and Conquer

function insertionSort(input) { const a = [...input]; for (let i = 1; i < a.length; i++) { const value = a[i]; let j = i - 1; while (j >= 0 && a[j] > value) { a[j + 1] = a[j]; j--; } a[j + 1] = value; } return a; }