# مسئله واقعاً چقدر بزرگ است؟
یک میلیون عدد یعنی N = 1,000,000. اگر بخواهیم همه اعداد را با یکدیگر مقایسه کنیم، تعداد مقایسهها تقریباً به این شکل رشد میکند:
problem_size.cpp
// تعداد مقایسههای دوبهدو:
N × (N − 1) / 2
1,000,000 × 999,999 / 2
≈ 499,999,500,000
// ≈ ۵۰۰ میلیارد مقایسه
اینجا اولین نکته مهم مشخص میشود: مسئله اصلی فقط «مرتب کردن» نیست؛ مسئله اصلی کاهش تعداد عملیات است. اگر الگوریتم ما مجبور باشد حدود ۵۰۰ میلیارد مقایسه انجام دهد، حتی یک CPU سریع هم نمیتواند آن را به مسئلهای کوچک تبدیل کند. اما اگر تعداد عملیات به حدود N·log₂(N) برسد:
better.cpp
1,000,000 × log₂(1,000,000)
≈ 1,000,000 × 19.93
≈ 19,930,000
// ≈ ۲۰ میلیون — نه ۵۰۰ میلیارد
این تفاوت، تمام داستان است. رفتن از حدود ۵۰۰ میلیارد عملیات به حدود ۲۰ میلیون، یک بهینهسازی کوچک نیست؛ تقریباً تغییر ماهیت مسئله است. برای دادههای بزرگ، انتخاب الگوریتم گاهی از قدرت CPU مهمتر است.
# یک میلیون عدد؛ دو دنیای کاملاً متفاوت
برای دیدن ابعاد مسئله، هزینه هر خانواده از الگوریتمها برای N = 1,000,000 را کنار هم ببینیم:
| الگوریتم | مرتبه زمانی | عملیات برای N = 1,000,000 |
|---|---|---|
| Bubble Sort | O(N²) | ≈ ۵۰۰ میلیارد مقایسه |
| Selection Sort | O(N²) | ≈ ۵۰۰ میلیارد مقایسه |
| Insertion Sort | O(N²) بدترین حالت | ≈ ۵۰۰ میلیارد در بدترین حالت |
| Merge Sort | O(N log N) | ≈ ۲۰ میلیون |
| Heap Sort | O(N log N) | ≈ ۲۰ میلیون |
| Quick Sort | O(N log N) میانگین | ≈ ۲۰ میلیون بهطور میانگین |
| Counting Sort | O(N + K) | وابسته به بازه اعداد K |
| Radix Sort | O(d·N) | وابسته به تعداد رقمها d |
| std::sort | O(N log N) | ≈ ۲۰ میلیون مرتبه مقایسه |
# اولین الگوریتم؛ سادهترین ایده ممکن
بیایید با روشی شروع کنیم که تقریباً همه در اولین برخورد با مسئله مرتبسازی به ذهنشان میرسد: Bubble Sort. آرایه
[5, 2, 8, 1, 3] را در نظر بگیرید. دو عدد کنار هم را مقایسه میکنیم: 5 > 2 پس جایشان را عوض میکنیم:
bubble_walkthrough.txt
[5, 2, 8, 1, 3] // 5 > 2 → جابهجا
[2, 5, 8, 1, 3] // 5 < 8 → بدون تغییر
[2, 5, 1, 8, 3] // 8 > 1 → جابهجا
[2, 5, 1, 3, 8] // 8 > 3 → جابهجا، 8 سر جایش نشست
... // تا مرتب شدن کامل ادامه بده
[1, 2, 3, 5, 8]
bubble_sort.cpp — C++
void bubbleSort(std::vector<int>& a)
{
int n = a.size();
for (int i = 0; i < n; ++i)
for (int j = 0; j < n - i - 1; ++j)
if (a[j] > a[j + 1])
std::swap(a[j], a[j + 1]);
}
از نظر آموزشی عالی است. از نظر عملی برای یک میلیون عدد؟ تقریباً فاجعه: دو حلقه تودرتو روی یک میلیون عنصر → حدود ۵۰۰٬۰۰۰٬۰۰۰٬۰۰۰ مقایسه.
مزایا
- بسیار ساده و قابل فهم
- مناسب آموزش مفهوم مرتبسازی
- نیاز به حافظه اضافی بسیار کم
- پیادهسازی آسان
معایب
- O(N²) — بسیار کند
- غیرقابل استفاده برای داده بزرگ
- هیچ دلیل خوبی برای استفاده روی یک میلیون عدد نیست
# Selection Sort و Insertion Sort؛ دو آشنای قدیمی
Selection Sort متفاوت کار میکند: در
[7, 4, 9, 1, 6] ابتدا کوچکترین عدد را پیدا میکنیم — یعنی 1 — و به ابتدای آرایه میبریم: [1, 4, 9, 7, 6]. دوباره از بخش باقیمانده کوچکترین را پیدا میکنیم و همینطور ادامه میدهیم.
selection_sort.cpp — C++
void selectionSort(std::vector<int>& a)
{
int n = a.size();
for (int i = 0; i < n - 1; ++i)
{
int minIndex = i;
for (int j = i + 1; j < n; ++j)
if (a[j] < a[minIndex])
minIndex = j;
std::swap(a[i], a[minIndex]);
}
}
پیچیدگی: O(N²). برای N = 1,000,000 باز هم حدود همان ۵۰۰ میلیارد مقایسه را داریم. Selection Sort در تعداد جابهجاییها میتواند وضعیت جالبی داشته باشد، اما مشکل اصلی آن همچنان تعداد بسیار زیاد مقایسههاست.
Insertion Sort کمی متفاوت است. تصور کنید کارتهای بازی در دست دارید و هر کارت جدیدی که میگیرید، آن را در جای درست بین کارتهای قبلی قرار میدهید. با داشتن
[2, 5, 8, 10] و کارت جدید 6، آن را بین 5 و 8 قرار میدهیم: [2, 5, 6, 8, 10].
insertion_sort.cpp — C++
void insertionSort(std::vector<int>& a)
{
for (int i = 1; i < (int)a.size(); ++i)
{
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
--j;
}
a[j + 1] = key;
}
}
Insertion Sort را دستکم نگیرید. بهترین حالت آن O(N) است — اگر داده تقریباً مرتب باشد، عملکرد فوقالعادهای دارد. به همین دلیل است که پیادهسازیهای حرفهای مرتبسازی گاهی برای بخشهای بسیار کوچک آرایه از ایده Insertion Sort استفاده میکنند؛ دقیقاً به این دلیل که در همانجا سریع است.
# حالا اتفاق مهم شروع میشود: Merge Sort
همه الگوریتمهای قبلی یک مشکل مشترک داشتند: با بزرگتر شدن N، کار مثل N² رشد میکند. بیایید از زاویه دیگری نگاه کنیم: بهجای مقایسه همهچیز با همه، آرایه را نصف میکنیم: 1,000,000 ← 500,000 + 500,000 ← 250,000 + 250,000 + ... و این کار را تا رسیدن به بخشهای بسیار کوچک ادامه میدهیم.
merge_walkthrough.txt
// تقسیم:
[8, 3, 7, 4, 9, 2]
[8, 3, 7] | [4, 9, 2]
[8] [3, 7] | [4, 9] [2]
[8] [3] [7] [4] [9] [2]
// ادغام معکوس (هر ادغام خطی است):
[3, 7] + [8] → [3, 7, 8]
[4, 9] + [2] → [2, 4, 9]
[3, 7, 8] + [2, 4, 9] → [2, 3, 4, 7, 8, 9]
merge.cpp — C++
void merge(std::vector<int>& a, int left, int mid, int right)
{
std::vector<int> temp;
int i = left, j = mid + 1;
while (i <= mid && j <= right)
{
if (a[i] <= a[j]) temp.push_back(a[i++]);
else temp.push_back(a[j++]);
}
while (i <= mid) temp.push_back(a[i++]);
while (j <= right) temp.push_back(a[j++]);
for (int k = 0; k < (int)temp.size(); ++k)
a[left + k] = temp[k];
}
merge_sort.cpp — C++
void mergeSort(std::vector<int>& a, int left, int right)
{
if (left >= right)
return;
int mid = left + (right - left) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
// نحوه اجرا:
mergeSort(a, 0, (int)a.size() - 1);
پیچیدگی: O(N log N). برای یک میلیون عدد یعنی حدود 1,000,000 × ~20 ≈ ۲۰٬۰۰۰٬۰۰۰ عملیات — بهجای ≈ ۵۰۰٬۰۰۰٬۰۰۰٬۰۰۰. ایده تقسیم و حل است که سد N² را میشکند.
# نمودار رشد الگوریتمها
در مقیاس کوچک شاید تفاوت زیادی دیده نشود. اما وقتی N بزرگ میشود، فاصله دو منحنی بهشدت زیاد میشود:
growth_chart.txt
| N | N² / 2 | N·log₂N | نسبت |
|---|---|---|---|
| 1,000 | 500,000 | ~10,000 | 50× |
| 100,000 | 5,000,000,000 | ~1,700,000 | ~2,900× |
| 1,000,000 | ~500,000,000,000 | ~19,931,569 | ~25,000× |
| 1,000,000,000 | ~10¹⁸ | ~30,000,000,000 | ~33,000,000× |
این فقط یک بهینهسازی کوچک نیست. این تقریباً تغییر ماهیت مسئله است.
# Quick Sort؛ الگوریتمی که «حدس» میزند
Merge Sort آرایه را بدون توجه به محتوا نصف میکند. Quick Sort میگوید: یک عنصر را به عنوان Pivot انتخاب میکنم و بقیه را نسبت به آن تقسیم میکنم. آرایه
[8, 3, 7, 4, 9, 2, 6] را با Pivot = 7 در نظر بگیرید:
partition.txt
[8, 3, 7, 4, 9, 2, 6] // pivot = 7
کمتر از 7 pivot بیشتر از 7
┌──────────┐ ┌──┐ ┌──────────┐
│ 3 4 2 6 │ │ 7 │ │ 8 9 │
└──────────┘ └──┘ └──────────┘
// حالا همین کار را برای دو سمت انجام بده
[3,4,2,6] → مرتب [8,9] → مرتب
quick_sort.cpp — C++
int partition(std::vector<int>& a, int low, int high)
{
int pivot = a[high];
int i = low - 1;
for (int j = low; j < high; ++j)
if (a[j] < pivot)
std::swap(a[++i], a[j]);
std::swap(a[i + 1], a[high]);
return i + 1;
}
void quickSort(std::vector<int>& a, int low, int high)
{
if (low >= high)
return;
int p = partition(a, low, high);
quickSort(a, low, p - 1);
quickSort(a, p + 1, high);
}
در حالت متوسط: O(N log N). اما یک مشکل خطرناک وجود دارد: بدترین حالت O(N²) است. مثلاً اگر آرایه از قبل مرتب باشد و همیشه بدترین Pivot را انتخاب کنیم، تقسیمها به
[1] [2,3,4,...] ← [2] [3,4,5,...] ← ... تبدیل میشوند و عملاً دوباره به رفتار N² برمیگردیم.
پس چرا هنوز Quick Sort مهم است؟ چون روی دادههای واقعی، انتخاب Pivot مناسب رفتار بسیار خوبی ایجاد میکند. روشهایی مانند Random Pivot، Median-of-three و استراتژیهای Introspective احتمال بدترین حالت را کاهش میدهند یا جلوی آن را میگیرند. اینجا همان جایی است که دنیای واقعی از کتاب الگوریتمها جالبتر میشود: الگوریتمهای واقعی معمولاً یک الگوریتم خالص نیستند، بلکه ترکیبی هستند.
# Heap Sort؛ مرتبسازی با یک Heap
در Heap Sort ابتدا دادهها را به یک ساختار Heap تبدیل میکنیم. در Max Heap، بزرگترین عنصر همیشه بالای ساختار قرار میگیرد:
max_heap.txt
1
استخراج ماکزیمم — 99 از بالای Heap برداشته میشود
2
انتقال به انتها — بزرگترین به جای نهایی خود میرود
3
ساخت دوباره Heap — بازیابی خاصیت Heap
↻
تکرار — هر بار بزرگترین عنصر بعدی
پیچیدگی: O(N log N) در بهترین، میانگین و بدترین حالت. مزیت مهم آن بدترین حالت قابل پیشبینی و حافظه اضافی بسیار کم است. در عمل معمولاً به اندازه یک پیادهسازی بسیار خوب Quick Sort یا std::sort جذاب نیست، اما وقتی به تضمین بدترین حالت نیاز دارید، میدرخشد.
# Counting Sort؛ وقتی اصلاً لازم نیست اعداد را مقایسه کنیم
همه الگوریتمهای قبلی یک کار مشترک انجام میدادند:
a < b ? اما چه میشود اگر بدانیم اعداد ما فقط بین 0 تا 100 هستند؟ [4, 1, 3, 1, 2, 4, 4] را در نظر بگیرید — لازم نیست چیزی را مقایسه کنیم؛ فقط میشماریم:
counting.txt
[4, 1, 3, 1, 2, 4, 4]
// شمارش تکرارها:
0 → 0 1 → 2 2 → 1 3 → 1 4 → 3
// خروجی:
1 1 2 3 4 4 4
counting_sort.cpp — C++
void countingSort(std::vector<int>& a)
{
if (a.empty())
return;
int maxValue = *std::max_element(a.begin(), a.end());
int minValue = *std::min_element(a.begin(), a.end());
int range = maxValue - minValue + 1;
std::vector<int> count(range, 0);
for (int x : a)
++count[x - minValue];
int index = 0;
for (int i = 0; i < range; ++i)
while (count[i]--)
a[index++] = i + minValue;
}
پیچیدگی: O(N + K) که K اندازه محدوده اعداد است. با N = 1,000,000 و K = 100 این فوقالعاده است. اما با K = 4,000,000,000 داستان کاملاً فرق میکند.
چرا Counting Sort همیشه جواب نیست؟ فرض کنید دادههای شما اینها هستند: 12، 8، 92، 4,000,000,000، 17. ساختن آرایه شمارش برای کل بازه 0 تا 4,000,000,000 حافظهای غیرمنطقی مصرف میکند. Counting Sort فقط زمانی فوقالعاده است که محدوده مقادیر نسبت به تعداد عناصر کوچک باشد.
# Radix Sort؛ رقم به رقم جلو برویم
راه دیگری هم وجود دارد. بهجای مقایسه مستقیم اعداد، آنها را رقم به رقم مرتب میکنیم: ابتدا بر اساس یکان، بعد دهگان، بعد صدگان و همینطور ادامه میدهیم:
radix.txt
// ورودی:
170 045 075 090 802 024 002 066
// بعد از مرتبسازی بر اساس یکان:
170 090 802 002 024 045 075 066
// بعد دهگان، بعد صدگان → کاملاً مرتب
002 024 045 066 075 090 170 802
هزینه آن وابسته به تعداد رقمهاست: O(d·N) که d تعداد رقمها و N تعداد عناصر است. برای یک میلیون عدد ۳۲ بیتی، d فقط چند مرحله محدود است — و همین، Radix Sort را برای کلیدهای صحیح با عرض ثابت به گزینهای بسیار قدرتمند تبدیل میکند.
# چیزی که واقعاً در C++ استفاده میکنیم: std::sort
در اکثر پروژههای C++ قرار نیست خودمان از صفر Bubble Sort بنویسیم. کتابخانه استاندارد برای ما دارد: std::sort():
main.cpp — C++
#include <algorithm>
#include <vector>
int main()
{
std::vector<int> numbers = { 8, 3, 7, 1, 9, 2 };
std::sort(numbers.begin(), numbers.end());
}
تمام. اما پشت همین دستور ساده، یک دنیای الگوریتمی قرار دارد. استاندارد C++ برای std::sort پیچیدگی O(N log N) را الزام میکند و ترتیب عناصر مساوی را حفظ نمیکند؛ پیادهسازیهای رایج معمولاً از ایدههایی در خانواده Introsort استفاده میکنند — شروع با Quick Sort، سوییچ به Heap Sort وقتی بازگشت خیلی عمیق میشود، و استفاده از Insertion Sort برای بخشهای کوچک — تا هم سرعت Quick Sort را داشته باشند و هم بدترین حالت در O(N log N) محدود بماند.
benchmark.cpp — C++
#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
int main()
{
constexpr int N = 1'000'000;
std::vector<int> numbers(N);
std::mt19937 rng(42);
std::uniform_int_distribution<int> dist(0, 1'000'000'000);
for (int& x : numbers) x = dist(rng);
auto start = std::chrono::steady_clock::now();
std::sort(numbers.begin(), numbers.end());
auto end = std::chrono::steady_clock::now();
double ms = std::chrono::duration<double, std::milli>(end - start).count();
std::cout << "Sorting time: " << ms << " ms\n";
std::cout << "First: " << numbers.front()
<< " | Last: " << numbers.back() << '\n';
}
یک اشتباه مهم هنگام Benchmark: گذاشتن sort بین دو فراخوانی ساعت، بهطور خودکار یک Benchmark علمی نیست. برای اندازهگیری بهتر: اول Warm-up، چند اجرای مستقل، دادههای یکسان، جلوگیری از اثر I/O، گزارش Median — و مهمتر از همه، به یاد داشته باشید Debug ≠ Release. با
g++ -O2 -std=c++20 main.cpp یا -O3 کامپایل کنید؛ نسخه Debug میتواند بهشدت کندتر از نسخه بهینهشده باشد. اعداد واقعی کاملاً به CPU، کامپایلر، کتابخانه استاندارد، فرکانس، حافظه و شرایط سیستم وابسته است.
# حافظه هم بخشی از مسئله است — و Stability هم
یک
std::vector با یک میلیون عنصر حدود 1,000,000 × 4 بایت ≈ 3.8 مگابایت است — چندان بزرگ نیست. اما الگوریتمهایی مثل Merge Sort به حافظه کمکی هممرتبه نیاز دارند، در حالی که بعضی دیگر تقریباً داخل همان آرایه کار میکنند. پس سؤال هرگز فقط «کدام سریعتر است؟» نیست — بلکه این است: «کدام سریعتر و با چه مصرف حافظهای؟»
یک ویژگی مهم دیگر هم وجود دارد: Stability. فرض کنید کارمندان را بر اساس سن مرتب میکنیم: Ali(30)، Sara(25)، Reza(30)، Mina(25). یک Sort پایدار تضمین میکند که عناصر با کلید مساوی، ترتیب نسبی قبلی خود را حفظ کنند — Ali قبل از Reza میماند و Sara قبل از Mina. در C++ این دقیقاً کار std::stable_sort است: ترتیب عناصر مساوی را حفظ میکند و در صورت وجود حافظه کمکی کافی، پیچیدگی مقایسههای آن O(N log N) است؛ در نبود حافظه کافی میتواند به O(N log² N) برسد.
stable.cpp — C++
std::stable_sort(people.begin(), people.end(),
[](const Person& a, const Person& b)
{
return a.age < b.age;
});
| الگوریتم | بهترین | میانگین | بدترین | حافظه اضافی | Stable |
|---|---|---|---|---|---|
| Bubble | O(N) | O(N²) | O(N²) | O(1) | ✓ |
| Selection | O(N²) | O(N²) | O(N²) | O(1) | ✗ |
| Insertion | O(N) | O(N²) | O(N²) | O(1) | ✓ |
| Merge | O(N log N) | O(N log N) | O(N log N) | O(N) | ✓ |
| Quick | O(N log N) | O(N log N) | O(N²) | O(log N) معمولاً | ✗ |
| Heap | O(N log N) | O(N log N) | O(N log N) | O(1) | ✗ |
| Counting | O(N+K) | O(N+K) | O(N+K) | O(K) | میتواند ✓ |
| Radix | O(dN) | O(dN) | O(dN) | وابسته | ✓ |
| std::sort | O(N log N) | O(N log N) | O(N log N) | وابسته به پیادهسازی | ✗ |
| std::stable_sort | O(N log N)* | O(N log N)* | O(N log N)* | بیشتر | ✓ |
* در حالت داشتن حافظه کمکی کافی؛ در غیر این صورت O(N log² N).
# یک راهنمای ساده برای انتخاب الگوریتم
1
به داده نگاه کن — بازه عددی کوچک؟ → Counting / Radix
2
داده عمومی — Stability مهم است؟ → بله: stable_sort
3
Stability لازم نیست — std::sort
★
نیازهای خاص — partial_sort / nth_element
| وضعیت داده | انتخاب مناسب |
|---|---|
| داده عمومی | std::sort |
| نیاز به Stable | std::stable_sort |
| محدوده عددی کوچک | Counting Sort |
| اعداد با رقم محدود | Radix Sort |
| داده تقریباً مرتب | Insertion / std::sort |
| فقط K عنصر مهم | nth_element |
| نیاز به بدترین حالت مشخص | Heap / introspective |
# شاید اصلاً نباید یک میلیون عدد را Sort کنیم!
این بخش بسیار مهم است. فرض کنید یک میلیون عدد داریم، اما سؤال پروژه فقط این است: «بزرگترین ۱۰ عدد کداماند؟» چرا باید تمام یک میلیون عدد را مرتب کنیم؟ میتوان از روشهای مناسب Selection یا Heap استفاده کرد و فقط بخش موردنیاز را پیدا کرد. یا اگر سؤال این است «عدد میانی چیست؟» — باز هم مرتبسازی کامل لازم نیست:
partial.cpp — C++
// قرار دادن میانه در جای درستش
// بدون مرتبسازی کامل آرایه:
std::nth_element(
numbers.begin(),
numbers.begin() + numbers.size() / 2,
numbers.end());
یک اصل مهم در مهندسی نرمافزار: بهینهترین Sort گاهی Sort نکردن است. std::partial_sort برای مرتبسازی جزئی و std::nth_element برای فقط K عنصر بزرگ یا میانی — همیشه لازم نیست همه یک میلیون عنصر مرتب شوند.
# کامپیوتر واقعاً چه چیزی را مرتب میکند؟ — و کجا Cache وارد میشود
یک تصور اشتباه این است که CPU اعداد را به شکل انسانی میبیند: 17، 23، 42، 100. در سطح سختافزار، آنها به صورت باینری وجود دارند:
00010001، 00010111، 00101010، 01100100. وقتی مینویسیم if (a < b)، در پشت صحنه CPU با ثباتها، حافظه، Cache، پرشها و دستورهای ماشین درگیر است: Load، Compare، Branch، Move، Swap، Store.
ثباتهای CPU
سریعترین — فقط چند جای محدود
L1 Cache
بسیار کوچک، فوقالعاده سریع
L2 / L3 Cache
بزرگتر و کندتر — لایههای مشترک
RAM
ظرفیت بالا، تأخیر زیاد
هرچه پایینتر میرویم: ظرفیت ↑، تأخیر ↑. پس دو الگوریتم با پیچیدگی نظری مشابه میتوانند روی سختافزار واقعی عملکرد متفاوتی داشته باشند، چون نحوه دسترسی آنها به حافظه اهمیت زیادی دارد. به همین دلیل است که در دنیای واقعی، Big O ضروری است — اما همهچیز نیست.
سختافزار نمیتواند الگوریتم بد را نجات دهد. یک CPU سریع با الگوریتم O(N²)، وقتی N بزرگ باشد، از یک CPU متوسط با الگوریتم O(N log N) شکست میخورد. در N = 10 شاید تفاوت دیده نشود؛ در N = 1,000,000 داستان کاملاً عوض میشود. قدرت خام نمیتواند بهراحتی یک الگوریتم بد را رها کند.
# یک میلیون عدد همیشه یک مسئله یکسان نیست
سه آرایه با N = 1,000,000 را تصور کنید: آرایه A برابر
1 2 3 4 5 ...، آرایه B برابر 8 7 6 5 4 ... و آرایه C برابر 92 14 827 3 71 991 .... اندازه یکسان — اما شکل داده کاملاً متفاوت:
مرتب / تقریباً مرتب
- Insertion Sort اینجا میدرخشد — نزدیک O(N)
- Quick Sort ساده میتواند به بدترین حالت بخورد
تصادفی
- حالت کلاسیک Benchmark
- std::sort / Quick Sort عالی عمل میکنند
تکرارهای زیاد
- بازه مؤثر کوچک است
- Counting Sort جذاب میشود
بازه کوچک (مثلاً 0–255)
- فقط ۲۵۶ مقدار ممکن
- فقط بشمار — مرتبسازی مقایسهای بهینه نیست
اگر داده 1 تا 1,000,000 باشد اما فقط ۱۰۰ مقدار اشتباه باشند، Insertion Sort رفتاری کاملاً متفاوت از بدترین حالت خود نشان میدهد. پس هرگز فقط بر اساس N تصمیم نگیرید — همیشه بپرسید: داده چه شکلی است؟ بهترین الگوریتم، سریعترین الگوریتم روی کاغذ نیست؛ الگوریتمی است که با خصوصیات داده سازگار است.
# یک میلیون واقعاً «زیاد» نیست — و یک میلیارد دنیای دیگری است
شاید عجیبترین بخش ماجرا همین باشد: برای انسان، 1,000,000 عدد بزرگی است. برای یک کامپیوتر مدرن، یک میلیون int فقط چند مگابایت است — چیز خارقالعادهای نیست. مسئله واقعی تعداد عناصر نیست؛ این است که برای هر عنصر چند بار عملیات انجام میدهیم؟ اگر N باشد — عالی. اگر N log N باشد — هنوز بسیار خوب. اما اگر N² باشد، با بزرگ شدن N ناگهان زمین زیر پای الگوریتم خالی میشود.
scale.txt
// N = 1,000,000
N log₂N ≈ 20,000,000
// N = 1,000,000,000
N log₂N ≈ 30,000,000,000
N² = 1,000,000,000,000,000,000,000
// در مقیاس یک میلیارد: N² = 10^18
// اینجا است که مفهوم Complexity دندانهایش را نشان میدهد.
و این داستان فقط مخصوص مرتبسازی نیست — در جستوجو، گراف، پایگاه داده، فایلها، رندر، شبیهسازی، هوش مصنوعی، رمزنگاری و پردازش تصویر هم تکرار میشود. همه یک سؤال مشترک دارند: با بزرگ شدن داده، تعداد عملیات چگونه رشد میکند؟ الگوریتمی که امروز با N = 1,000 عالی به نظر میرسد، فردا با N = 1,000,000 میتواند گلوگاه اصلی سیستم شود.
# پس کامپیوتر چگونه یک میلیون عدد را مرتب میکند؟
جواب نهایی خیلی سادهتر از چیزی است که در ابتدا به نظر میرسید. کامپیوتر یک میلیون عدد را با قدرت خام CPU «زورکی» مرتب نمیکند. این مسیر را طی میکند:
1
داده — شناخت ساختار مسئله
2
انتخاب الگوریتم مناسب — کاهش تعداد عملیات
3
حافظه و Cache — استفاده هوشمندانه
4
اجرای بهینه — روی CPU، در بیلد Release
✓
آرایه مرتبشده — در میلیثانیه، نه ساعتها
برای داده عمومی:
std::sort. وقتی Stability مهم است: std::stable_sort. برای محدوده کوچک: Counting Sort. برای اعداد با تعداد رقم محدود: Radix Sort. و وقتی فقط بخشی از ترتیب اهمیت دارد: nth_element. در بیشتر برنامههای معمول C++، std::sort اولین گزینه منطقی است — نه به این دلیل که «همیشه بهترین الگوریتم جهان» است، بلکه چون یک پیادهسازی استاندارد و بسیار بهینه برای مسئله عمومی است، با تضمین O(N log N) از سوی استاندارد C++.
takeaway.txt
مرتبسازی یک میلیون عدد در چند لحظه جادو نیست؛
هنرِ کمتر کار کردن است.
هنرِ کمتر کار کردن است.
