مبانی کامپیوتر و الگوریتم؛ از حل مسئله تا پروژهٔ عملی

مرتب‌سازی فقط چیدن عددها نیست؛ نوعی آماده‌سازی داده برای گزارش و جست‌وجو است. اگر بخواهیم نمره‌ها را صعودی ببینیم، هم نتیجهٔ درست مهم است و هم حفظ رابطهٔ هر نمره با صاحب آن. در این درس دو روش ساده را از روی حرکت واقعی داده می‌خوانیم: انتخاب کوچک‌ترین عضوِ باقی‌مانده و درج هر عضو در بخش مرتب قبلی. این روش‌ها ابزار مناسبی برای فهم الگوریتم‌اند، اما توصیهٔ عمومی برای جایگزینی ابزارهای استاندارد روی دادهٔ بزرگ نیستند.

قبل از شروع؛ کلید، ترتیب و مالکیت داده

کلید همان چیزی است که براساس آن مقایسه می‌کنیم؛ مثلاً قیمت محصول، نه لزوماً تمام مشخصات محصول. در نمونهٔ عددی، خود عدد کلید است و ترتیب صعودی می‌خواهیم. قرارداد، آرایهٔ متراکمِ عدد صحیح امن با حداکثر هزار عضو است. محدودیت طول جلوی اجرای ناخواستهٔ تمرینِ درجه‌دو روی ورودی بسیار بزرگ را می‌گیرد. نسخه‌های این درس آرایهٔ ورودی را تغییر نمی‌دهند و یک نسخهٔ تازه می‌سازند؛ این تصمیم هزینهٔ حافظه دارد و در تحلیل باید دیده شود.

دو ویژگی را جدا بررسی کنید: آیا خروجی صعودی است و آیا دقیقاً همان اعضای ورودی را با همان تعداد دارد؟ خروجی[۱،۲،۳] برای ورودی[۳،۱،۲،۱] صعودی است، ولی یک۱ را گم کرده و مرتب‌سازی درست نیست. همچنین عددهای منفی و تکراری نباید با فیلتر خاموش حذف شوند. برای شیءها، باید شناسه و کلید باهم حرکت کنند. جابه‌جایی فقط قیمت‌ها در دو آرایهٔ موازی ممکن است دادهٔ ظاهراً مرتب اما ارتباط کالا و قیمت را خراب کند.

انتخابی؛ هر بار کوچک‌ترینِ بازمانده را جلو بیاورید

در آغاز گذرi، خانه‌های قبل ازi مرتب و قطعی‌اند. در بخشi تاپایان، مکان کوچک‌ترین عضو را پیدا می‌کنیم و آن را با خانهٔi عوض می‌کنیم. سپس مرز قسمت قطعی یک خانه جلو می‌رود. این توضیح دلیل انتخاب نام روش است. یافتن کمینه باید کل قسمتِ باقی‌مانده را ببیند؛ دیدن اولین عدد کوچک‌تر کافی نیست. متغیرmin در شبه‌کد شاخص کمینه است و نه خود مقدار؛ اشتباه این دو هنگام دسترسی به آرایه خطای رایجی است.

selectionSort(a):
    a ← کپی ورودی معتبر
    برای i از 0 تا طول a - 2:
        min ← i
        برای j از i + 1 تا طول a - 1:
            اگر a[j] < a[min]: min ← j
        اگر min ≠ i: خانه‌های i و min را جابه‌جا کن
    برگردان a

برای[۳،۱،۲،۱]، گذر اول نخستین۱ را پیدا و به ابتدا منتقل می‌کند؛[۱،۳،۲،۱] می‌ماند. گذر دوم۱ انتهایی را به خانهٔ۱ می‌آورد و[۱،۱،۲،۳] ساخته می‌شود. گذر سوم هنوز باید بخش کوچک باقی‌مانده را بررسی کند، حتی اگر از ظاهر کل فهرست معلوم باشد مرتب شده است. در نسخهٔ ما وقتیmin=i باشد، تعویض بی‌اثر انجام نمی‌دهیم؛ بنابراین شمار تعویض واقعی با نسخه‌ای که همیشه تعویض می‌کند یکسان نیست. شمارنده باید دقیقاً همین تفاوت را منعکس کند.

درجی؛ بخش مرتب را با هر عضو تازه گسترش دهید

در روش درجی، نخستین عضو به‌تنهایی یک بخش مرتب است. عضو بعدی را موقتاً درkey نگه می‌داریم، عضوهای بزرگ‌ترِ بخش قبلی را یک خانه به راست می‌بریم وkey را در جای خالی می‌گذاریم. نگهداریkey ضروری است، چون جابه‌جایی‌ها ممکن است خانهٔ اولیه‌اش را بازنویسی کنند. در آغاز هر گذر، بخش قبل ازi مرتب است و در پایان، بخش تاخودi مرتب می‌شود. این استدلال کوچک، از حفظ‌کردن نام دوحلقه برای توضیح درستی مفیدتر است.

insertionSort(a):
    a ← کپی ورودی معتبر
    برای i از 1 تا طول a - 1:
        key ← a[i]
        j ← i - 1
        تا زمانی که j >= 0 و a[j] > key:
            a[j + 1] ← a[j]
            j ← j - 1
        a[j + 1] ← key
    برگردان a

همان ورودی[۳،۱،۲،۱] را این بار با درجی ببینید. با آوردن۱، عدد۳ یک خانه راست می‌رود و[۱،۳،۲،۱] می‌شود. برای۲، فقط۳ راست می‌رود و[۱،۲،۳،۱] داریم. برای۱ آخر،۳ و۲ راست می‌روند، اما۱ اول جابه‌جا نمی‌شود، چون شرط «بزرگ‌تر» است. نتیجه[۱،۱،۲،۳] می‌شود. ردگیری هر دو روش نتیجهٔ نهایی یکسانی می‌دهد، ولی مسیر و هزینه یکسان نیستند. این تفاوت را در گزارش عملیات حفظ می‌کنیم.

گذرِ درجی      بخش پردازش‌شده و بازمانده
شروع           [3 | 1, 2, 1]
پس از i = 1    [1, 3 | 2, 1]
پس از i = 2    [1, 2, 3 | 1]
پس از i = 3    [1, 1, 2, 3 | ]

شمارش روشن؛ مقایسهٔ کلید با زمان پردازنده یکی نیست

کد زیر در09-sort-counts.mjs دو روش را اجرا می‌کند. comparisons فقط مقایسهٔ دوکلید را می‌شمارد؛ بررسی نوع، شرط حلقه و کپی اولیه در آن نیست. در انتخابی، swaps تعویض واقعی دوخانه است. در درجی، shifts تعداد حرکت یک عضو بزرگ‌تر به راست است؛ گذاشتن نهاییkey در این شمارنده نیست. پس نمی‌توان گفت یکswap دقیقاً هم‌هزینهٔ یکshift است. این شمارنده‌ها برای فهم رفتارند، نه نتیجه‌گیری دربارهٔ میلی‌ثانیه یا تعداد دستورهای واقعی پردازنده.

import assert from 'node:assert/strict';
function copyNumbers(input) {
  if (!Array.isArray(input) || input.length > 1000) {
    throw new TypeError('Expected an array of at most 1000 numbers');
  }
  const a = [];
  for (let i = 0; i < input.length; i += 1) {
    if (!Object.hasOwn(input, i) || !Number.isSafeInteger(input[i])) {
      throw new TypeError('Expected dense safe-integer data');
    }
    a.push(input[i]);
  }
  return a;
}
function selectionSort(input) {
  const a = copyNumbers(input);
  let comparisons = 0, swaps = 0;
  for (let i = 0; i < a.length - 1; i += 1) {
    let min = i;
    for (let j = i + 1; j < a.length; j += 1) {
      comparisons += 1;
      if (a[j] < a[min]) min = j;
    }
    if (min !== i) {
      const temp = a[i]; a[i] = a[min]; a[min] = temp;
      swaps += 1;
    }
  }
  return { values: a, comparisons, swaps };
}
function insertionSort(input) {
  const a = copyNumbers(input);
  let comparisons = 0, shifts = 0;
  for (let i = 1; i < a.length; i += 1) {
    const key = a[i];
    let j = i - 1;
    while (j >= 0) {
      comparisons += 1;
      if (a[j] <= key) break;
      a[j + 1] = a[j]; shifts += 1; j -= 1;
    }
    a[j + 1] = key;
  }
  return { values: a, comparisons, shifts };
}
const input = [3, 1, 2, 1];
assert.deepEqual(selectionSort(input).values, [1, 1, 2, 3]);
assert.deepEqual(insertionSort(input).values, [1, 1, 2, 3]);
assert.deepEqual(input, [3, 1, 2, 1]);
assert.deepEqual(selectionSort([1, 2, 3, 4]), { values: [1, 2, 3, 4], comparisons: 6, swaps: 0 });
assert.deepEqual(insertionSort([1, 2, 3, 4]), { values: [1, 2, 3, 4], comparisons: 3, shifts: 0 });
assert.deepEqual(insertionSort([4, 3, 2, 1]), { values: [1, 2, 3, 4], comparisons: 6, shifts: 6 });
for (const fn of [selectionSort, insertionSort]) {
  assert.deepEqual(fn([]).values, []);
  assert.deepEqual(fn([-3, -8, 0]).values, [-8, -3, 0]);
  assert.deepEqual(fn([7]).values, [7]);
  assert.throws(() => fn([1, NaN]), TypeError);
  assert.throws(() => fn([, 1]), TypeError);
}
console.log(JSON.stringify(selectionSort(input)));
console.log(JSON.stringify(insertionSort(input)));

برای ورودی نمونه، انتخابی۶ مقایسه و۲ تعویض و درجی۶ مقایسه و۴ شیفت دارد. آرایهٔ اصلی دست‌نخورده می‌ماند. در انتخابی، تعداد مقایسه‌های این نسخه از رابطهٔ n(n−1)/2 به دست می‌آید؛ ورودیِ ازپیش‌مرتب این جست‌وجوی کامل را حذف نمی‌کند. در درجی، ورودی صعودی باعث توقف زودهنگام هر گذر می‌شود؛ برای n عضو، n−1 مقایسهٔ کلید و صفر شیفت داریم. در ورودی نزولیِ با کلیدهای متمایز، تعداد شیفت‌ها به n(n−1)/2 می‌رسد. این‌ها خاصیت نسخهٔ دقیقِ درس‌اند.

پایداری؛ ترتیب برابرها چه می‌شود؟

مرتب‌سازی پایدار، ترتیب نسبی ردیف‌های دارای کلید برابر را حفظ می‌کند. فرض کنید کارتA باکلید۲، سپسB باکلید۲ و بعدC باکلید۱ رسیده‌اند. انتخابی معمول با تعویضC وA، خروجیC,B,A می‌سازد؛A وB جایشان نسبت به هم عوض شده است. درجی با شرط سخت‌گیرانهٔ >، برابر قبلی را هل نمی‌دهد وC,A,B می‌سازد. هر دو خروجی از نظر کلید مرتب‌اند؛ بنابراین برای مشاهدهٔ پایداری باید شناسهٔ جدا از کلید داشته باشیم.

نمونهٔ مستقل09-sort-stability.mjs فقط همین مسئلهٔ کوچک را نمایش می‌دهد. داده‌ها ساختگی و سه‌عضوی‌اند؛ کپی هرکارت باعث می‌شود ورودی نیز عوض نشود. در این بلوک، انتخاب روش از دو نام مشخص مجاز است. اگر الگوریتم را در برنامهٔ بزرگ‌تری استفاده کنید، محدودیت طول، یکتایی شناسه‌ها و قرارداد کلید را در مرز ورودی متناسب با همان برنامه بررسی کنید. یک نمایش سه‌کارتی را بدون تعریف قرارداد، ابزار عمومی مرتب‌سازی اطلاعات کاربران ندانید.

import assert from 'node:assert/strict';
function sortCards(input, method) {
  if (!Array.isArray(input) || !['selection', 'insertion'].includes(method)) {
    throw new TypeError('Expected cards and a known method');
  }
  const a = input.map(card => {
    if (!card || typeof card.id !== 'string' || !Number.isSafeInteger(card.key)) {
      throw new TypeError('Invalid card');
    }
    return { id: card.id, key: card.key };
  });
  if (method === 'selection') {
    for (let i = 0; i < a.length - 1; i += 1) {
      let min = i;
      for (let j = i + 1; j < a.length; j += 1) if (a[j].key < a[min].key) min = j;
      const temp = a[i]; a[i] = a[min]; a[min] = temp;
    }
  } else {
    for (let i = 1; i < a.length; i += 1) {
      const key = a[i]; let j = i - 1;
      while (j >= 0 && a[j].key > key.key) { a[j + 1] = a[j]; j -= 1; }
      a[j + 1] = key;
    }
  }
  return a;
}
const cards = [{ id: 'A', key: 2 }, { id: 'B', key: 2 }, { id: 'C', key: 1 }];
const selection = sortCards(cards, 'selection').map(card => card.id);
const insertion = sortCards(cards, 'insertion').map(card => card.id);
assert.deepEqual(selection, ['C', 'B', 'A']);
assert.deepEqual(insertion, ['C', 'A', 'B']);
assert.deepEqual(cards.map(card => card.id), ['A', 'B', 'C']);
console.log(`selection: ${selection.join(',')}`);
console.log(`insertion: ${insertion.join(',')}`);

خروجی انتخابیselection: C,B,A و خروجی درجیinsertion: C,A,B است. ناپایداربودن به معنی تصادفی‌بودن یا اشتباه‌بودن ترتیب عددی نیست؛ فقط تضمین حفظ ترتیب برابرها وجود ندارد. همچنین پایداری، قانون دوم مرتب‌سازی را اختراع نمی‌کند. اگر برای نمره‌های برابر باید شناسه صعودی باشد، این خواسته را صریحاً در مقایسه‌گر یا قرارداد ترتیب تعریف کنید؛ تکیه بر ترتیب دریافت شبکه لزوماً نتیجهٔ یکسانی در اجراهای مختلف نمی‌دهد. هر دو مفهوم در گزارش پروژهٔ پایانی مهم می‌شوند.

انتخاب روش و تحلیل حافظه

در مدل آموزشی، انتخابی در همهٔ ترتیب‌های ورودی، مقایسهٔ درجه‌دو دارد؛ درجی در حالت مناسب خطی و در بدترین حالت درجه‌دو می‌شود. عبارت «تقریباً مرتب» را هم بی‌تعریف به کار نبرید؛ تعداد زوج‌های وارونه، توصیف دقیق‌تری از کار جابه‌جایی درجی است. یک عنصرِ خیلی جابه‌جا ممکن است تعداد زیادی وارونگی بسازد. هیچ‌یک از این دو روش، جایگزین همیشگی مرتب‌سازی استاندارد برای دادهٔ بزرگ نیست. اندازهٔ داده، هزینهٔ مقایسه، جابه‌جایی و تضمین‌های موردنیاز در انتخاب نقش دارند.

هسته‌های معمول این دو روش روی همان آرایه با حافظهٔ کمکی ثابت کار می‌کنند؛ اما نسخه‌های آموزشی ما ابتدا کپی می‌سازند، پس حافظهٔ خروجی و کارِ کپی متناسب با n است. نگفتن این نکته می‌تواند ادعای «حافظهٔO(1)» را برای تابع کامل غلط کند. برای تمرین، اصل داده را حفظ می‌کنیم تا بتوان قبل و بعد را مقایسه کرد. برای رفتار روش‌های آماده و اندازه‌گیری دقیق‌تر، درس مستقل آرایه‌ها را بخوانید: https://www.darsavand.com/resources/javascript-nodejs-arrays-performance .

نمونه‌سؤال‌های تألیفی و پاسخ تشریحی

سؤال۱: مرتب‌سازی انتخابیِ معمول روی [3,1,2,1] را پس از هر گذر بیرونی بنویسید.

پاسخ۱: در گذر اول، کوچک‌ترین مقدار۱ درشاخص۱ انتخاب می‌شود و نتیجه[1,3,2,1] است. گذر دوم،۱ درشاخص۳ را باخانهٔ۱ عوض می‌کند و[1,1,2,3] می‌دهد. در گذر سوم، کوچک‌ترین عضوِباقی‌مانده همان۲ است و تعویض واقعی رخ نمی‌دهد. در نسخهٔ درس،۶ مقایسهٔ کلید و۲ تعویض واقعی داریم؛ نتیجهٔ مرتب به‌تنهایی تعداد عملیات را مشخص نمی‌کند.

سؤال۲: اگر در درجی، شرط جابه‌جایی از «بزرگ‌تر» به «بزرگ‌تر یا مساوی» عوض شود چه خاصیتی از دست می‌رود؟

پاسخ۲: عنصرهای هم‌کلید هم به راست هل داده می‌شوند و عنصر تازه ممکن است جلوتر از برابرهای قبلی بنشیند. برای کارت‌های A:2 وB:2، پس از پردازشB ترتیبB,A می‌شود. بنابراین پایداری حفظ نمی‌شود؛ هرچند کلیدها همچنان مرتب‌اند. آزمون با عددهای متمایز این تغییر را نشان نمی‌دهد، پس برای آزمودن پایداری باید شناسهٔ جدا از کلید داشته باشیم.

سؤال۳: روی آرایهٔ ازپیش‌مرتب پنج‌عضوی، تعداد مقایسهٔ کلیدِ دو روش در نسخهٔ درس چقدر است؟

پاسخ۳: انتخابی۴+۳+۲+۱ یعنی۱۰ مقایسه انجام می‌دهد، چون هر بار بازمانده را می‌گردد. درجی برای هر عضو از دوم به بعد، یک مقایسه با قبلی انجام می‌دهد و زود متوقف می‌شود؛ پس۴ مقایسه و صفر شیفت دارد. این‌ها شمارش کلید در کد مشخص درس‌اند، نه همهٔ دستورهای پردازنده و نه میلی‌ثانیه. کپی اولیه و بررسی نوع نیز هزینه دارند، ولی در این شمارنده شمرده نشده‌اند.

معیار تحویل و منابع رسمی

هنگام تحویل، یک اجرای دستی، تعریف شمارنده‌ها، آزمون حفظ ورودی و یک نمونهٔ هم‌کلید ارائه کنید. باید بتوانید بگویید چرا مرتب‌بودن به‌تنهایی کافی نیست و چرا مقایسهٔ تعدادswap باshift، زمان واقعی را ثابت نمی‌کند. اگر نتیجه متفاوت شد، نخست مرز حلقه، محل نگهداریkey و شرط برابری را بررسی کنید. متن، داده‌ها و کدهای این درس تألیف مستقل تحریریه درس‌آوند است؛ منابع رسمی زیر برای بررسی مفهوم‌ها و ادامهٔ مطالعه معرفی شده‌اند.

Princeton — Elementary Sorts: https://algs4.cs.princeton.edu/21elementary/
Princeton — Sorting Applications: https://algs4.cs.princeton.edu/25applications/
Princeton — Insertion: https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Insertion.java.html
MIT — Searching and Sorting: https://ocw.mit.edu/courses/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/resources/lecture-12-searching-and-sorting/

فایل مثال‌ها، راهنمای فارسی اجرا و عیب‌یابی، پروژهٔ گزارش نمره‌ها و آزمون جمع‌بندی تألیفی با پاسخ تشریحی، رایگان در صفحهٔ بستهٔ تمرین همین دوره ارائه می‌شود:
https://www.darsavand.com/resources/computer-algorithms-practice-kit
تألیف و مثال‌های اختصاصی: تحریریه درس‌آوند.