مبانی کامپیوتر · فصل ۰۷
بخش خوانده‌شده۰/ ۱۲
زبان برنامه‌نویسی ۲ · منبع: 06.b.pdf (۷۶ اسلاید)

توابع، آرایه‌ها و مرتب‌سازی

از «چرا تابع؟» تا تحلیل پیچیدگی مرتب‌سازی؛ این صفحه هر دو پارادایم ساخت‌یافته و شیءگرا را به هم می‌بندد و با ابزارهای امروزی مقایسه می‌کند.

سه فصل داخلی: فصل ۱ توابع · فصل ۲ آرایه‌ها · فصل ۳ مرتب‌سازی (همان ساختار اسلایدهای منبع)

۱۲بخش۱۲جدول۱۱قطعه‌کد≈۲۶ دقیقهمطالعهمنبع06.b.pdf
CPP-06B · توابع و آرایه
مرتب‌سازی: از بی‌نظمی به نظم، در چند گذر. unsorted → sorted
۷.۱
بخش ۷.۱

چرا تابع؟ برنامه‌نویسی ساخت‌یافته

Structured programming

در دههٔ ۱۹۶۰ تولید نرم‌افزار به بحران خورد: برنامه‌ها بزرگ و پیچیده می‌شدند، زمان‌بندی تحویل عقب می‌افتاد، هزینهٔ نگه‌داری سرسام‌آور می‌شد و استفادهٔ بی‌قاعده از goto جریان برنامه را غیرقابل‌ردیابی می‌کرد. پاسخ این بحران، برنامه‌نویسی ساخت‌یافته بود: شکستن مسئله به قطعات کوچک‌تر با ورودی و خروجی روشن.

  1. ۱مسئلهٔ بزرگ را به زیرمسئله‌های کوچک‌تر تقسیم کنید — هر زیرمسئله یک کار مشخص.
  2. ۲برای هر زیرمسئله یک تابع بنویسید: نام گویا، ورودی‌های روشن، خروجی مشخص.
  3. ۳هر تابع را جداگانه بیازمایید؛ سپس در برنامهٔ اصلی کنار هم بگذارید.
  4. ۴ساختارهای کنترلی را به سه شکل محدود کنید: ترتیب، انتخاب، تکرار — بدون پرش‌های بی‌قاعده.
دانشجویان در حال کار گروهی روی تمرین برنامه‌نویسی
نمونهٔ کتاب درس: محاسبهٔ میانگین حقوق کارمندان یک شرکت — کاری پیچیده که به کارهای کوچک‌تر می‌شکند: خواندن حقوق هر کارمند، جمع‌کردن، شمردن، تقسیم و چاپ نتیجه.

انتزاع (Abstraction)

انتزاع یکی از مفاهیم کلیدی برنامه‌نویسی و در عین حال گیج‌کننده‌ترین آن‌هاست: در برنامه‌نویسی، انتزاع یعنی نشان دادن ویژگی‌های ضروری و پنهان‌کردن جزئیات پیاده‌سازی. وقتی تابعی با نام average() می‌سازید، کاربر آن فقط می‌داند «میانگین می‌دهد» — نه اینکه داخلش حلقه و جمع و تقسیم است.

نتیجهٔ عملی: تابع، مرز میان «چه» و «چگونه» است. برنامه را از دید «چه» می‌نویسیم (تابع‌های معنادار) و جزئیات «چگونه» را داخل تابع پنهان می‌کنیم. این همان چیزی است که کد را خواندنی، آزمون‌پذیر و قابل‌اصلاح می‌کند.
۷.۲
بخش ۷.۲

از ساخت‌یافته تا شیءگرا

From procedural to object-oriented

برنامه‌نویسی شیءگرا شیوه‌ای است که قطعات نرم‌افزاری قابل‌استفادهٔ مجدد می‌سازد: داده و عملیات مربوط به آن، در یک واحد به نام «شیء» بسته‌بندی می‌شوند.

پارادایمواحد اصلیپرسش محوریزبان‌های نمونه
ساخت‌یافته/رویه‌ایتابع (function)چه گام‌هایی برای حل مسئله لازم است؟C، Pascal، بخش رویه‌ای C++
شیءگراشیء و کلاس (object / class)چه اشیائی در مسئله وجود دارد و هر یک چه رفتاری دارد؟C++، Java، C#، Python
تابعیتابع محض و دادهٔ تغییرناپذیرچگونه داده را بدون حالت و عوارض جانبی تبدیل کنیم؟Haskell، F#، بخش تابعی C++
همگانی/چندپارادایمیترکیبی از همهٔ ابزارهاکدام ابزار برای این مسئله مناسب‌تر است؟C++، Python، Rust

📦کپسوله‌سازی encapsulation

داده و عملیات مربوط به آن در یک واحد بسته‌بندی می‌شوند و دسترسی بیرونی از دروازه‌های مشخص عبور می‌کند.

🧬وراثت inheritance

کلاس تازه می‌تواند ویژگی‌های کلاس پایه را به ارث بگیرد و گسترش دهد؛ ابزار استفادهٔ مجدد از کد.

🎭چندریختی polymorphism

یک نام، رفتارهای متفاوت بر پایهٔ نوع واقعی شیء؛ پایهٔ طراحی انعطاف‌پذیر.

🎯انتزاع abstraction

نمایش آنچه ضروری است و پنهان‌کردن جزئیات؛ از تابع تا واسط (interface).

همان ایده، در C++
struct Student {            // کلاس: داده + رفتار
    std::string name;
    double grade;

    bool isPassed() const { return grade >= 10; }   // رفتار
};

Student s{"Sara", 17.5};      // شیء
if (s.isPassed()) {
    std::cout << s.name << " قبول شد";
}
// اگر تعریف Students را عوض کنیم، بقیهٔ برنامه تغییری نمی‌خواهد.
بسته‌بندی داده و رفتار در یک واحد
۷.۳
بخش ۷.۳

تعریف، اعلان و انواع توابع

Defining, declaring & using functions

زبان C++ خط‌به‌خط و از بالا به پایین ترجمه می‌شود؛ پس اگر تابعی در برنامه استفاده می‌شود، باید پیش از نخستین فراخوانی شناخته شده باشد — یا تعریف شده باشد، یا اعلان شده باشد.

اصطلاحمعنانمونه
اعلان (declaration)نوشتن مشخصات تابع بدون بدنه؛ «قرارداد» تابع با کامپایلرvoid printFunction(int n);
تعریف (definition)مشخصات + بدنهٔ تابع؛ پیاده‌سازی واقعیvoid printFunction(int n) { … }
تابع بازگردانندهٔ مقدارنوع برگشتی غیر از void و دستور returnfloat Power(float x, int n);
تابع بی‌بازگشتکار انجام می‌دهد و چیزی برنمی‌گرداندvoid maghsom(int n);
الگوی منبع: مقسوم‌های یک عدد (تابع بی‌بازگشت)
#include <iostream>

void maghsom(int n) {
    for (int i = 1; i < n; i++)
        if (n % i == 0) {
            std::cout << i << "  ";
        }
    std::cout << n;          // خود عدد هم مقسوم خودش است
}

int main() {
    maghsom(12);             //  خروجی: 1 2 3 4 6 12
    return 0;
}
تابع void: کاری انجام می‌دهد، مقداری برنمی‌گرداند
الگوی منبع: تابع بازگردانندهٔ مقدار
#include <iostream>

float check(int x) {                 // مراقب تقسیم صحیح باشید
    if (x == 0) {
        return 2;
    } else if (x > 0) {
        return 3 * x + 5 / 2.0f;
    } else {
        return 3 * x - 5 / 2.0f;
    }
}

int main() {
    std::cout << check(4) << " " << check(0) << " " << check(-2);
    return 0;                        //  خروجی: 14.5  2  -8.5
}
سه شاخه، سه مقدار برگشتی
اعلان پیش از استفاده — الگوی استاندارد امروز
#include <iostream>

void printFunction(int n);       // اعلان‌ها (پیش‌نمونه‌ها)
float Power(float x, int n);

int main() {
    printFunction(4);
    std::cout << Power(2.0f, 10);   // 1024
    return 0;
}

void printFunction(int n) {      // تعریف‌ها پایین‌تر آمده‌اند
    for (int i = 0; i < n; i++)
        std::cout << i << ' ';
}

float Power(float x, int n) {
    float result = 1;
    for (int i = 0; i < n; i++)
        result *= x;
    return result;
}
ترتیب درست: اعلان‌ها بالای فایل، بدنه پایین
۷.۴
بخش ۷.۴

توابع بازگشتی

Recursion

بازگشتی مفهومی است که در آن تابع خودش را فراخوانی می‌کند — به‌طور مستقیم یا غیرمستقیم. هر تابع بازگشتی دو بخش دارد: حالت پایه (شرط توقف) و گام بازگشتی (کوچک‌کردن مسئله). حذف حالت پایه = بازگشت بی‌پایان و سرریز پشته.

نمونهٔ کلاسیک: فاکتوریل
#include <iostream>

long fact(int x) {
    if (x != 0) {                // گام بازگشتی
        return x * fact(x - 1);
    }
    return 1;                    // حالت پایه:  0! = 1
}

int main() {
    std::cout << fact(5);        // 120
    return 0;
}
fact(5) = 5 × 4 × 3 × 2 × 1 = 120
سری فیبوناچی
#include <iostream>

int Fibonacci(int number) {
    if (number <= 1) {
        return number;                     // حالت پایه
    }
    return Fibonacci(number - 1) + Fibonacci(number - 2);
}

int main() {
    for (int i = 0; i < 10; i++)
        std::cout << Fibonacci(i) << ' ';
    return 0;                                //  0 1 1 2 3 5 8 13 21 34
}
هر جمله: مجموع دو جملهٔ پیشین

تمرین‌های ردگیری از اسلایدهای منبع

تابعفراخوانیردگیریپاسخ
rec(n) = اگر n==1 ← ۱، وگرنه rec(n-1)+rec(n-1)rec(5)هر سطح دو شاخه می‌سازد: rec(5)=16 چون 2×rec(4) و rec(1)=1 → 2⁴ = 16۱۶
func(n) = اگر n==0 ← ۰، وگرنه n + func(n-1)func(100)جمع اعداد ۱ تا ۱۰۰: (100×101)/2۵۰۵۰
sum(n) = اگر n<=1 ← n، وگرنه sum(n-1)+sum(n-3)sum(4)sum(4)=sum(3)+sum(1)؛ sum(3)=sum(2)+sum(0)=0؛ sum(1)=1 ← نتیجه۱
۷.۵
بخش ۷.۵

بارگذاری بیش‌ازحد توابع

Function overloading

در اسلایدهای منبع این مفهوم با نام «چندریختی در توابع» معرفی شده است. تعریف دقیق امروزی: دو یا چند تابع هم‌نام با فهرست پارامترهای متفاوت. کامپایلر بر اساس تعداد و نوع آرگومان‌ها، نسخهٔ درست را انتخاب می‌کند.

سه تابع با یک نام
#include <iostream>

double Multiply()                        { return 1; }                 // بدون آرگومان
double Multiply(double x)                { return x * x; }             // یک آرگومان
double Multiply(double x, double y)      { return x * y; }             // دو آرگومان

int main() {
    std::cout << Multiply() << ' ' << Multiply(4) << ' ' << Multiply(3, 5);
    return 0;                            //  خروجی: 1  16  15
}
یک نام، سه رفتار — انتخاب در زمان ترجمه
قواعد بارگذاری بیش‌ازحد: تعداد یا نوع آرگومان‌ها باید متفاوت باشد · تنها تفاوت در نوع مقدار برگشتی برای بارگذاری کافی نیست · نمی‌توان دو تابع با تعداد و نوع آرگومان‌های یکسان تعریف کرد — کامپایلر خطای تعریف مکرر می‌دهد.
۷.۶
بخش ۷.۶

آرایه‌های ایستا

Static arrays

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

  1. ۱نوع دادهٔ آرایه مشخص می‌شود: int، float و…
  2. ۲نام آرایه درج می‌شود؛ برای همهٔ خانه‌ها یک نام واحد.
  3. ۳تعداد عناصر داخل کروشه می‌آید: int grade[20];
  4. ۴اندیس‌ها از صفر تا n-1 هستند: برای ۲۰ خانه، اندیس‌های ۰ تا ۱۹.

چهار روش مقداردهی

۱) در سطر تعریف — ۲) در سطرهای جداگانه
// ۱) مقداردهی هم‌زمان با تعریف
int a[5] = {2, 4, 6, 8, 10};     // آرایهٔ تازه در C++: int a[5]{};  → همه صفر

// ۲) مقداردهی خانه‌به‌خانه
int b[5];
b[0] = 7;
b[1] = 3;
// …

// ۳) مقداردهی با حلقهٔ for  (روش تعاملی)
double points[5];
for (int i = 0; i < 5; i++)
    std::cin >> points[i];

// ۴) مقداردهی با حلقهٔ for بر پایهٔ الگو
for (int i = 0; i < 5; i++)
    points[i] = i * 10;          //  0 10 20 30 40
راه‌های متعارف مقداردهی به آرایه

چاپ خانه‌های آرایه

روشتوضیحنمونه
چاپ خانه‌به‌خانهنوشتن جداگانهٔ هر خانه با coutstd::cout << a[0] << a[1];
چاپ با حلقهپیمایش همهٔ خانه‌ها در یک حلقهfor (int i=0; i<n; i++) cout << a[i];
پیمایش معکوساز آخرین خانه به اولین خانهfor (int i=n-1; i>=0; i--)
دسترسی پشت‌سرهم در حافظه: عناصر آرایه به‌صورت پیوسته ذخیره می‌شوند؛ مزیت آن دسترسی بسیار سریع به هر خانه است (آدرس خانهٔ i از فرمول ساده به‌دست می‌آید). عیب آن این است که درج و حذف در میان آرایه، جابه‌جایی عناصر را لازم دارد و برای تعداد نامعلوم عناصر، حافظهٔ رزروشده هدر می‌رود.
۷.۷
بخش ۷.۷

آرایه‌های پویا و مدیریت حافظه

Dynamic arrays & memory management

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

تولید و آزادسازی آرایهٔ پویا — الگوی منبع (نادرست در C++ مدرن، ولی آموزشی)
int n;
std::cin >> n;

double* px = new double[n];      // درخواست حافظه از «کپه» (heap)
for (int i = 0; i < n; i++)
    px[i] = i * i;               // مثل آرایهٔ معمولی کار می‌کند

// …
delete[] px;                     // آزادسازی الزامی
px = nullptr;                    // جلوگیری از «اشاره‌گر معلق»
هر new باید یک delete داشته باشد
روش امروزی: بدون new و delete دستی
#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<double> px(n);       // آرایهٔ پویا با مدیریت خودکار حافظه
    for (int i = 0; i < n; i++)
        px[i] = i * i;
    std::cout << px.size() << " عنصر آماده است";
    return 0;                        // حافظه خودکار آزاد می‌شود
}
اصل RAII: حافظه به عمر شیء گره خورده است
خطرتوضیحجلوگیری
نشت حافظه (memory leak)حافظه‌ای که new شده و delete نشده است؛ برنامهٔ طولانی‌مدت کم‌حافظه می‌شودstd::vector، std::unique_ptr و اصل RAII
اشاره‌گر معلقاستفاده از اشاره‌گری که حافظه‌اش آزاد شده استپس از delete، اشاره‌گر را nullptr کنید
آزادسازی نادرستترکیب new[] با delete (بدون کروشه)هماهنگی دقیق: new[] با delete[]
آزادسازی دوبارهدو بار delete روی یک اشاره‌گرمالکیت روشن؛ در کد امروز باید ابزار هوشمند کار را انجام دهد
دو حافظهٔ متفاوت: آرایهٔ ایستا روی «پشتهٔ برنامه» (stack) ساخته می‌شود و با پایان تابع خودکار پاک می‌شود؛ حافظهٔ new از «کپه» آمده و تا وقتی خودتان آزادش نکنید باقی می‌ماند. در مثال منبع، هر خانهٔ آرایهٔ double هشت بایت فاصله دارد؛ به همین دلیل آدرس‌های چاپ‌شده با گام ۸ افزایش می‌یافتند.
۷.۸
بخش ۷.۸

آرایه به‌عنوان آرگومان تابع

Arrays as function arguments

آرایه‌ها همانند متغیرهای معمولی به تابع فرستاده می‌شوند؛ با این تفاوت مهم که آرایه به‌طور کامل کپی نمی‌شود.

ارسال آرایه به تابع
#include <iostream>

void fanc1(int x[]);              // اعلان‌ها
void fanc2(int x[], int len);

void findIterate(float a[], int len);   // میانگین را می‌یابد و تکرارش را می‌شمارد

int main() {
    int x[10];
    fanc1(x);
    fanc2(x, 10);
    return 0;
}

void fanc1(int x[])        { /* طول آرایه را نمی‌دانیم! */ }
void fanc2(int x[], int len) { /* طول را همراه آرایه می‌فرستیم */ }
الگو: طول آرایه را همیشه همراه آن بفرستید
نکتهٔ کلیدی امروزی: نام آرایه هنگام ارسال به تابع، به «اشاره‌گر به اولین خانه» تبدیل می‌شود (فروپاشی آرایه). یعنی تابع خودِ دادهٔ اصلی را می‌بیند و هر تغییری در آن، در تابع فراخواننده نیز دیده می‌شود. راه حل امروزی برای حفظ ایمنی: std::span<int> (C++20) یا const std::vector<int>& که هم طول را می‌شناسند و هم از سرریز جلوگیری می‌کنند.
۷.۹
بخش ۷.۹

مرتب‌سازی: مفاهیم و معیارها

Sorting: concepts

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

اصطلاحتعریفچرا مهم است
کلید (key)فیلدی در رکورد که رکوردها را به‌طور یکتا مشخص می‌کندمبنای مقایسه و ترتیب؛ جست‌وجو بر اساس کلید انجام می‌شود
مرتب‌سازی داخلیمرتب‌سازی رکوردهای موجود در حافظهٔ اصلیسرعت دسترسی بالا؛ روش‌های این فصل از این نوع‌اند
مرتب‌سازی خارجیمرتب‌سازی رکوردهای موجود در حافظهٔ جانبی (دیسک)هزینهٔ خواندن/نوشتن غالب می‌شود؛ الگوریتم‌های ادغامی و توزیعی مناسب‌اند
مرتب‌سازی پایداررکوردهای با کلید مساوی، ترتیب قبلی خود را حفظ می‌کنندمهم در گزارش‌گیری چندسطحی (مثلاً مرتب‌سازی بر اساس نام پس از مرتب‌سازی بر اساس شهر)
مرتب‌سازی درجابا حافظهٔ کمکی ثابت و مستقل از تعداد عناصر انجام می‌شودمناسب محیط‌های کم‌حافظه
مرتب‌سازی با آدرسبه‌جای جابه‌جایی رکوردها، جدول اشاره‌گرها جابه‌جا می‌شودبا رکوردهای بزرگ، صرفهٔ زمانی چشمگیر
الف) جابه‌جایی خود رکوردها رکورد ۱ 7 رکورد ۲ 3 رکورد ۳ 9 رکورد ۴ 1 هر جابه‌جایی = کپی کل دادهٔ رکورد (پرهزینه با رکورد بزرگ) ب) مرتب‌سازی با آدرس رکورد ۱ 7 رکورد ۲ 3 رکورد ۳ 9 رکورد ۴ 1 → رکورد ۴ → رکورد ۲ → رکورد ۱ → رکورد ۳ تنها اشاره‌گرها (آدرس‌ها) جابه‌جا می‌شوند، نه کل داده
مرتب‌سازی با آدرس: در سمت چپ، خودِ رکوردها جابه‌جا می‌شوند (کپی سنگین داده)؛ در سمت راست، تنها جدول اشاره‌گرها (آدرس‌ها) دوباره چیده می‌شود.
مرتب‌سازی یا جست‌وجو؟ چون این دو تنگاتنگ‌اند، همیشه این پرسش مطرح است: ابتدا فایل را مرتب کنیم و بعد جست‌وجو، یا نه؟ اگر فایل به‌طور مکرر برای یافتن عناصر خاص استفاده شود، مرتب‌کردن آن کارایی را بالا می‌برد؛ چون هزینهٔ جست‌وجوهای متوالی در فایل نامرتب به‌سرعت غالب می‌شود. اگر فایل کوچک باشد، روش‌های پیچیده معمولاً بهتر از روش‌های ساده نیستند.
۷.۱۰
بخش ۷.۱۰

هفت روش مرتب‌سازی

Seven sorting methods

فهرست روش‌هایی که در اسلایدهای منبع آمده است، به‌همراه ایدهٔ هر یک و هزینهٔ امروزی‌شان. n تعداد عناصر است.

روشایده در یک جملهمیانگینبدترین حالتحافظهٔ کمکیپایدار
انتخابی (selection)در هر گذر، کوچک‌ترین عنصر باقی‌مانده را پیدا کن و در جایش بگذارO(n²)O(n²)ثابتخیر
حبابی (bubble)همسایه‌ها را مقایسه و جابه‌جا کن تا بزرگ‌ها به انتها بروندO(n²)O(n²)ثابتبله
درجی (insertion)هر عنصر را در جای درست خود در بخش مرتب‌شده وارد کنO(n²)O(n²)ثابتبله
جابجایی/تعویضی (exchange)هر عنصر را با عناصر بعدی مقایسه و در صورت نیاز عوض کنO(n²)O(n²)ثابتخیر
سریع (quick)یک عنصر محور انتخاب کن، کوچک‌ترها یک طرف و بزرگ‌ترها طرف دیگر، سپس بازگشتیO(n log n)O(n²)O(log n)خیر
ادغامی (merge)دو نیمهٔ مرتب را در یک فهرست مرتب ادغام کنO(n log n)O(n log n)O(n)بله
مبنایی (radix)رقم‌به‌رقم از کم‌ارزش‌ترین رقم، عناصر را در سطل‌ها توزیع کنO(d·n)O(d·n)O(n)بله
مرتبهٔ زمانی چیست؟ نشان می‌دهد زمان اجرا با بزرگ‌شدن ورودی چگونه رشد می‌کند. O(n²) برای هزار عنصر حدود یک میلیون عمل است (کند)، در حالی که O(n log n) در همان ورودی حدود ده هزار عمل دارد (تند). این معیار، معیار انتخاب امروزی است — نه تعداد خطوط کد.
۷.۱۱
بخش ۷.۱۱

مرتب‌سازی مبنایی: چه‌گونه کار می‌کند؟

Radix sort in action

مرتب‌سازی مبنایی روشی است که همه به‌طور شهودی از آن استفاده می‌کنیم: وقتی فهرست بزرگی از نام‌ها را به‌ترتیب الفبا مرتب می‌کنیم، مبنا ۲۶ (تعداد حروف انگلیسی) است و نام‌ها نخست بر اساس حرف اول به دسته‌ها تقسیم می‌شوند.

  1. ۱هر عدد را به ترتیبی که در آرایه دارد می‌خوانیم و بر اساس ارزش رقمی که در حال پردازش است، در یکی از ده صف (صفر تا نه) قرار می‌دهیم.
  2. ۲سپس صف‌ها را به ترتیب از صف صفر تا صف نه می‌خوانیم و در آرایه بازنویسی می‌کنیم.
  3. ۳این عمل را برای رقم یکان انجام می‌دهیم، سپس رقم دهگان — یعنی از کم‌ارزش‌ترین رقم به سمت چپ حرکت می‌کنیم.
  4. ۴برای اعداد دورقمی، پس از دو گذر آرایه مرتب است؛ برای اعداد پنج‌رقمی به پنج گذر نیاز داریم.
گذرآرایه پیش از گذرمعیار توزیعآرایه پس از گذر
۰ (ورودی)——57 48 37 12 92 86 33 25
۱57 48 37 12 92 86 33 25رقم یکان12 92 33 25 86 57 37 48
۲12 92 33 25 86 57 37 48رقم دهگان12 25 33 37 48 57 86 92
چرا دو گذر کافی بود؟ چون اعداد دورقمی بودند. تعداد گذرها به «تعداد ارقام بزرگ‌ترین کلید» وابسته است، نه به تعداد عناصر؛ به همین دلیل مرتبهٔ زمانی O(d·n) است — خطی و سریع. شرط کارکرد درست، پایداری توزیع در هر گذر است: عناصر با رقم مساوی باید ترتیب قبلی خود را حفظ کنند.
۷.۱۲
بخش ۷.۱۲

به‌روزرسانی با دانش امروز

2026 update

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

موضوعدر اسلایدهای منبعوضعیت امروز (۲۰۲۶)
حافظهٔ پویاnew[] و delete[] برای آرایههمان دستورها معتبرند، اما در کد امروزی جای خود را به std::vector، std::unique_ptr و std::make_unique داده‌اند؛ مدیریت دستی حافظه فقط در کد پایین‌سطح و کتابخانه‌ای لازم است.
آرایهٔ ایستاint grade[20]; با اندازهٔ ثابتهمچنان رایج، ولی std::array (اندازه در نوع) و std::vector (اندازهٔ پویا) انتخاب‌های ایمن‌تر امروزند.
پارامتر آرایهvoid fanc(int x[], int len) با فروپاشی آرایهstd::span (C++20) طول را همراه می‌برد و سطح مرزها را ایمن نگه می‌دارد.
الگوریتم مرتب‌سازیهفت روش دستی و پیاده‌سازی از صفربرای استفادهٔ عملی: std::sort، std::stable_sort؛ پیاده‌سازی دستی برای درک الگوریتم، آموزش و نیازهای خاص (مانند مرتب‌سازی موازی یا مبنایی).
سنجش کاراییشمارش مقایسه‌ها به‌طور شهودیتحلیل مرتبهٔ زمانی O / Θ / Ω و معادلهٔ بازگشتی، به‌همراه سنجش واقعی با ابزار زمان‌سنجی روی دادهٔ نماینده — معیار پذیرفته‌شدهٔ مهندسی.
نگه‌داشت ترتیبمفهوم پایداری معرفی شده بوددر عمل تعیین‌کننده است: Timsort در Python، Java و مرورگرها؛ پایداری پیش‌فرض بسیاری از زبان‌ها.
انتخاب روشمقدمه‌ای بر معیارها در کتابقاعدهٔ عملی امروز: دادهٔ کوچک یا تقریباً مرتب ← درجی؛ حالت عمومی ← std::sort؛ نیاز به پایداری ← stable_sort؛ کلید با عرض محدود ← مبنایی/شمارشی؛ دادهٔ عظیم ← موازی یا توزیع‌شده.
آزمون صحتچند نمونهٔ دستیآزمون ویژگی‌محور، آزمون یکا روی حالت‌های مرزی (تهی، یک عنصر، عناصر تکراری، دادهٔ معکوس) و اجرای ابزارهای بررسی خطا.
جمع‌بندی فصل: تابع کوچک‌ترین واحد سازمان‌دهی برنامه است: ورودی و خروجی روشن، بدنهٔ پنهان. با بازگشت، مسائل را می‌توان به نسخهٔ کوچک‌تر خودشان فروکاست — به شرط داشتن حالت پایه. آرایه، دادهٔ هم‌نوع را پشت‌سرهم نگه می‌دارد؛ اندازه‌اش یا ثابت است یا در زمان اجرا از کپه گرفته می‌شود. و مرتب‌سازی، عمل بنیادی ایجاد نظم در داده است که کیفیتش امروز با «مرتبهٔ زمانی» سنجیده می‌شود، نه با تعداد خطوط کد.
نقشهٔ پوشش منبع — کدام بخش این صفحه از کدام اسلاید استخراج شده است.
بخش این صفحهاسلایدهای منبع
۷.۱ برنامه‌نویسی ساخت‌یافتهفصل ۱ — مقدمه، ۱-۱ و ۱-۲
۷.۲ شیءگرا و انتزاعفصل ۱ — ۱-۳
۷.۳ تعریف و اعلان توابعفصل ۱ — فرمت کلی، اعلان، void و مقدار برگشتی
۷.۴ بازگشتیفصل ۱ — توابع بازگشتی و تمرین‌ها
۷.۵ بارگذاری بیش‌ازحدفصل ۱ — چندریختی در توابع
۷.۶ آرایهٔ ایستافصل ۲ — تعریف، مقداردهی و چاپ
۷.۷ آرایهٔ پویافصل ۲ — new و آزادسازی حافظه
۷.۸ آرایه و تابعفصل ۲ — ارسال آرایه به توابع
۷.۹–۷.۱۱ مرتب‌سازیفصل ۳ — مفاهیم، هفت روش و مرتب‌سازی مبنایی
۷.۱۲ به‌روزرسانی‌هاافزودهٔ سرویراستار (دانش ۲۰۲۶)
جمع‌بندی تعاملی

پازل مفاهیم فصل

Chapter puzzle — match the concepts

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

🧩 جدول تطبیق مفاهیم — ۱۸ جفت ۰ از ۱۸

مفاهیم

تعریف‌ها

یک مفهوم را انتخاب کنید، سپس تعریفش را بزنید.