پیاده‌سازی صحیح الگوریتم Bubble Sort با جلوگیری از خطای خارج از محدوده
پیاده‌سازی الگوریتم Selection Sort برای مرتب‌سازی صعودی
تحلیل پیچیدگی زمانی هر دو الگوریتم
مقایسه مدیریت رشته‌ها در زبان C و C++
مقدمه‌ای بر مرتب‌سازی
الگوریتم‌های مرتب‌سازی (Sorting) از پرکاربردترین الگوریتم‌ها در علوم کامپیوتر هستند. هدف آن‌ها چینش عناصر یک آرایه به ترتیب صعودی (کوچک به بزرگ) یا نزولی (بزرگ به کوچک) است.
در این درس دو الگوریتم کلاسیک و ساده را بررسی می‌کنیم:
Bubble Sort (مرتب‌سازی حبابی): در هر مرحله، بزرگ‌ترین عنصر باقیمانده مانند حباب به انتهای آرایه می‌رود.
Selection Sort (مرتب‌سازی انتخابی): در هر مرحله، کوچک‌ترین (یا بزرگ‌ترین) عنصر باقیمانده پیدا شده و در جای مناسب قرار می‌گیرد.
در Bubble Sort، آرایه در چند مرحله پیمایش می‌شود. در هر مرحله، جفت‌های مجاور از ابتدا تا انتهای بخش نامرتب مقایسه شده و اگر عنصر اول بزرگ‌تر از عنصر دوم بود، جای آن‌ها عوض می‌شود.
پس از پایان هر مرحله، بزرگ‌ترین عنصر باقیمانده در انتهای آرایه قرار می‌گیرد و در مرحله بعدی نیازی به بررسی آن نیست.
ویژگی‌ها:
ساده‌ترین الگوریتم مرتب‌سازی برای آموزش
پایدار (Stable) است: ترتیب عناصر برابر حفظ می‌شود
درجا (In-place) است: به حافظه اضافی نیاز ندارد
پیاده‌سازی Bubble Sort (اصلاح‌شده)
مرتب‌سازی صعودی آرایه با Bubble Sortcpp
نمونه اجرا
خروجی
ورودی:
5
12 10 70 1 5
خروجی:
1 5 10 12 70
فلوچارت Bubble Sort
flow.svg
تفاوت سبکی حلقه داخلی: i > 0 یا i >= 0؟
در نسخه‌ی اولیه‌ی جزوه، حلقه بیرونی به‌صورت for(int i=n-1; i>=0; i--) و حلقه درونی for(int j=0; j<i; j++) نوشته شده بود. این کد از نظر کارکرد درست است: چون j < i، بزرگ‌ترین مقدار j برابر i-1 می‌شود و a[j+1] حداکثر به a[i] می‌رسد که همیشه داخل محدوده است — هیچ خطای Out of Bounds رخ نمی‌دهد. تنها اشکالش یک تکرار بی‌اثر است: در تکرار i=0 حلقه درونی اصلاً اجرا نمی‌شود. قرارداد تمیزتر این است که حلقه بیرونی تا i>0 برود تا آن تکرار بی‌فایده حذف شود و خواننده بلافاصله بفهمد در i=0 کاری انجام نمی‌شود.
نسخه اشتباه جزوه
کد دارای باگcpp
نسخه اصلاح‌شده و استاندارد
کد صحیحcpp
الگوریتم مرتب‌سازی انتخابی (Selection Sort)
در Selection Sort، آرایه به دو بخش تقسیم می‌شود: بخش مرتب (ابتدای آرایه) و بخش نامرتب (انتهای آرایه). در هر مرحله، کوچک‌ترین عنصر از بخش نامرتب پیدا شده و با اولین عنصر بخش نامرتب تعویض می‌شود.
پس از n-1 مرحله، کل آرایه مرتب می‌شود.
ویژگی‌ها:
تعداد تعویض‌ها کم است (حداکثر n-1 تعویض)
پایدار نیست: ممکن است ترتیب عناصر برابر به هم بریزد
درجا (In-place) است
پیاده‌سازی Selection Sort (اصلاح‌شده)
مرتب‌سازی صعودی با انتخاب کوچک‌ترین عنصرcpp
فلوچارت Selection Sort
flow.svg
اصلاح منطق Selection Sort در جزوه
کد اصلی جزوه به دنبال بزرگ‌ترین عنصر (با شرط a[j] > a[m]) می‌گشت و سپس آن را با a[i-1] تعویض می‌کرد؛ یعنی در واقع آرایه را به‌صورت نزولی مرتب نمی‌کرد چون بزرگ‌ترین را به انتها می‌برد و حلقه بیرونی از i=n شروع می‌شد که از محدوده خارج است. همچنین در تصویر اصلی به‌جای a[m] اشتباهاً a] تایپ شده بود.
نسخه اشتباه جزوه
کد دارای باگcpp
نسخه اصلاح‌شده و استاندارد
کد صحیحcpp
تحلیل پیچیدگی زمانی (Time Complexity)
هر دو الگوریتم Bubble Sort و Selection Sort دارای پیچیدگی زمانی O(n²) در حالت میانگین و بدترین حالت هستند.
الگوریتم
بهترین حالت
حالت میانگین
بدترین حالت
حافظه
Bubble Sort
O(n)
O(n²)
O(n²)
O(1)
Selection Sort
O(n²)
O(n²)
O(n²)
O(1)
بهترین حالت Bubble Sort وقتی رخ می‌دهد که آرایه از قبل مرتب باشد و از بهینه‌سازی «بدون تعویض = پایان زودهنگام» استفاده کنیم.
Selection Sort همیشه تعداد مقایسه‌های ثابت n(n-1)/2 دارد ولی تعداد تعویض‌های آن کم است.
برای داده‌های بزرگ، الگوریتم‌های سریع‌تری مانند Quick Sort (میانگین O(n log n)) یا Merge Sort (O(n log n) تضمینی) پیشنهاد می‌شوند.
مقایسه مدیریت رشته‌ها در C و C++
در جزوه (صفحه ۳۳) جدولی برای مقایسه دو سبک مدیریت رشته آورده شده است. در زبان C از آرایه کاراکتری استفاده می‌شود، اما در C++ کلاس std::string امکانات بسیار بیشتری می‌دهد.
موضوع
زبان C (char[])
C++ (std::string)
تعریف
char ch[100];
string s;
ورودی ساده
cin >> ch;
cin >> s;
ورودی با فاصله
cin.getline(ch, 100);
getline(cin, s);
طول رشته
strlen(ch);
s.length();
خروجی
cout << ch;
cout << s;
انتساب
strcpy(ch2, ch1);
s2 = s1;
الحاق
strcat(ch1, ch2);
s2 = s2 + s1;
مقایسه برابری
strcmp(ch1, ch2) == 0
s1 == s2
نکته: در C++ مدرن، عملگر‌های ==, <, > و + روی std::string به‌درستی کار می‌کنند و نیازی به توابع string.h نیست.
جلوگیری از VLA: استفاده از std::vector
در جزوه از int a[n]; استفاده شده که با n متغیر است. این قابلیت Variable Length Array (VLA) در استاندارد ISO C++ مجاز نیست (هرچند GCC آن را پشتیبانی می‌کند).
به جای آن، از std::vector استفاده کنید:
main.cppcpp
مزیت‌ها: مدیریت خودکار حافظه، امکان تغییر اندازه، عدم خطر نشت حافظه.
هدر <utility> برای تابع swap
تابع swap در C++ مدرن در هدر <utility> تعریف شده است. در بسیاری از کامپایلر‌ها به‌صورت ضمنی از طریق <iostream> نیز قابل دسترس است، اما برای اطمینان کامل، در ابتدای برنامه‌ای که از swap استفاده می‌کند، این خط را اضافه کنید:
پیاده‌سازی صحیح الگوریتم Bubble Sort با جلوگیری از خطای خارج از محدوده
پیاده‌سازی الگوریتم Selection Sort برای مرتب‌سازی صعودی
نکات کلیدی:
Bubble Sort با مقایسه و تعویض جفت‌های مجاور کار می‌کند و بزرگ‌ترین عنصر را در هر مرحله به انتها می‌برد.
Selection Sort در هر مرحله کوچک‌ترین عنصر باقیمانده را پیدا کرده و در جای مناسب قرار می‌دهد.
هر دو الگوریتم پیچیدگی O(n²) دارند و برای داده‌های بزرگ مناسب نیستند.
در Bubble Sort نوشتن `i > 0` به‌جای `i >= 0` در حلقه بیرونی فقط تمیزتر است: تکرار `i=0` هیچ کاری انجام نمی‌دهد (حلقه داخلی اجرا نمی‌شود) و حذفش کد را روشن‌تر می‌کند — نه به‌خاطر خطای Out of Bounds، چون چنین خطایی در این الگو رخ نمی‌دهد.
برنامه‌ای بنویسید که n عدد را از ورودی بگیرد، آن‌ها را با **Bubble Sort** به‌صورت **نزولی** (بزرگ به کوچک) مرتب کند و سپس چاپ کند.
نمایش راهنما
کافی است جهت علامت مقایسه را از `>` به `<` تغییر دهید: `if (a[j] < a[j+1]) swap(...)`.
02
تمرین•حل کامل دارد
برنامه‌ای بنویسید که n عدد را بگیرد و با **Selection Sort** به‌صورت صعودی مرتب کند. سپس میانگین، کوچک‌ترین و بزرگ‌ترین عدد را چاپ کند.
نمایش راهنما
بعد از مرتب‌سازی، کوچک‌ترین در `a[0]` و بزرگ‌ترین در `a[n-1]` خواهد بود.
03
تمرین•حل کامل دارد
برنامه‌ای بنویسید که آرایه‌ای از n رشته (کلمه) را بگیرد و آن‌ها را بر اساس **طول** به‌صورت صعودی مرتب کند. اگر طول دو کلمه برابر بود، ترتیب الفبایی اعمال شود.
نمایش راهنما
از `vector<string>` و تابع عضو `.length()` استفاده کنید. مقایسه مستقیم `s1 < s2` ترتیب الفبایی می‌دهد.
04
تمرین•حل کامل دارد
بهینه‌سازی Bubble Sort: پرچمی به نام `swapped` اضافه کنید که اگر در یک مرحله کامل هیچ تعویضی انجام نشد، الگوریتم زودتر خاتمه یابد. پیاده‌سازی کنید.
نمایش راهنما
در ابتدای هر مرحله `swapped = false` و در صورت تعویض `swapped = true`. بعد از حلقه داخلی اگر `!swapped` بود، `break` کنید.
// نکات-کلیدی۶
01Bubble Sort با مقایسه و تعویض جفت‌های مجاور کار می‌کند و بزرگ‌ترین عنصر را در هر مرحله به انتها می‌برد.
02Selection Sort در هر مرحله کوچک‌ترین عنصر باقیمانده را پیدا کرده و در جای مناسب قرار می‌دهد.
03هر دو الگوریتم پیچیدگی O(n²) دارند و برای داده‌های بزرگ مناسب نیستند.
04در Bubble Sort نوشتن `i > 0` به‌جای `i >= 0` در حلقه بیرونی فقط تمیزتر است: تکرار `i=0` هیچ کاری انجام نمی‌دهد (حلقه داخلی اجرا نمی‌شود) و حذفش کد را روشن‌تر می‌کند — نه به‌خاطر خطای Out of Bounds، چون چنین خطایی در این الگو رخ نمی‌دهد.
05به جای VLA مانند `int a[n]` از `std::vector<int>` یا تخصیص پویا استفاده کنید.
06در C++ مدرن از کلاس `std::string` به‌جای آرایه کاراکتری استفاده کنید تا عملگر‌های `=`, `+`, `==` پشتیبانی شوند.
گام بعدی پیشنهادی
توابع کتابخانه‌ای رشته C (string.h)
آشنایی با strlen، strcpy، strcat و strcmp به همراه اصلاح اشتباهات رایج جزوه
نام درس، موضوع یا کلمه کلیدی را بنویسید و با Enter به آن بروید
1#include<iostream>2#include<vector>3usingnamespace std;45intmain(){6int n;7 cin >> n;8 vector<int>a(n);910// دریافت عناصر آرایه11for(int i =0; i < n; i++)12 cin >> a[i];1314// حلقه اصلی مرتب‌سازی حبابی15for(int i = n -1; i >0; i--){16for(int j =0; j < i; j++){17if(a[j]> a[j +1])18swap(a[j], a[j +1]);19}20}2122// چاپ آرایه مرتب‌شده23for(int i =0; i < n; i++)24 cout << a[i]<<" ";25 cout << endl;2627return0;28}29
flow.svg100%
Press enter or space to select a node. You can then use the arrow keys to move the node around. Press delete to remove it and escape to cancel.
Press enter or space to select an edge. You can then press delete to remove it or escape to cancel.
شروع/پایانپردازشتصمیمورودی/خروجی
1// نسخه جزوه — درست اما با یک تکرار بی‌اثر2for(int i = n -1; i >=0; i--){3for(int j =0; j < i; j++){4if(a[j]> a[j +1])5swap(a[j], a[j +1]);6}7}8// در تکرار i=0 حلقه درونی اجرا نمی‌شود (شرط j<i از همان اول برقرار نیست)؛9// نتیجه درست است، فقط یک مرحله اضافه دارد.
1// نسخه تمیزتر2for(int i = n -1; i >0; i--){3for(int j =0; j < i; j++){4if(a[j]> a[j +1])5swap(a[j], a[j +1]);6}7}8// تکرار بی‌اثر i=0 حذف شد؛ کد کوتاه‌تر و روشن‌تر است.
1#include<iostream>2#include<vector>3usingnamespace std;45intmain(){6int n;7 cin >> n;8 vector<int>a(n);910for(int i =0; i < n; i++)11 cin >> a[i];1213// حلقه اصلی مرتب‌سازی انتخابی14for(int i =0; i < n -1; i++){15int m = i;// فرض: کوچک‌ترین در اندیس i16for(int j = i +1; j < n; j++){17if(a[j]< a[m])18 m = j;19}20swap(a[i], a[m]);21}2223for(int i =0; i < n; i++)24 cout << a[i]<<" ";25 cout << endl;2627return0;28}29
flow.svg100%
Press enter or space to select a node. You can then use the arrow keys to move the node around. Press delete to remove it and escape to cancel.
Press enter or space to select an edge. You can then press delete to remove it or escape to cancel.
شروع/پایانپردازشتصمیمورودی/خروجی
1// نسخه دارای اشکال در جزوه2int n, m;3cin >> n;4int a[n];// VLA غیراستاندارد در C++5for(int i =0; i < n; i++) cin >> a[i];6for(int i = n; i >=0; i--){// i=n خارج از محدوده7 m =0;8for(int j =0; j < i; j++)9if(a[j]> a[m]) m = j;// بزرگ‌ترین را پیدا می‌کند10swap(a], a[i -1]);// اشتباه تایپی a]11}
1// نسخه اصلاح‌شده (مرتب‌سازی صعودی با انتخاب کوچک‌ترین)2int n;3cin >> n;4vector<int>a(n);// استاندارد C++5for(int i =0; i < n; i++) cin >> a[i];6for(int i =0; i < n -1; i++){7int m = i;8for(int j = i +1; j < n; j++)9if(a[j]< a[m]) m = j;// کوچک‌ترین10swap(a[i], a[m]);11}
#include<vector>int n;cin >> n;vector<int>a(n);// استاندارد و امن