یونیون‌فایند و مرتب‌سازی خطی: دو مبحث کوتاه و پرسود با سه تست و سه اشتباه رایج

یونیون‌فایند: مجموعه‌های مجزا

n عنصر داری که در ابتدا هر کدام یک مجموعهٔ جدا هستند. دو عمل لازم داری: find(x) که نمایندهٔ مجموعهٔ x را برمی‌گرداند و union(x, y) که مجموعه‌های x و y را یکی می‌کند. هر مجموعه را یک درخت نگه می‌داریم که ریشه‌اش نماینده است و هر عنصر فقط به پدرش اشاره می‌کند. هزینهٔ find به ارتفاع درخت بستگی دارد.

بدون هیچ ترفندی

اگر در union همیشه ریشهٔ اولی را زیر دومی بگذاری، دنبالهٔ union(1, 2)، union(2, 3)، … یک زنجیره می‌سازد. در اجرای ما با ۱۰۲۴ عنصر، ارتفاع به ۱۰۲۳ رسید؛ یعنی find در بدترین حالت Θ(n) طول می‌کشد.

ترفند اول: ادغام بر اساس رتبه

برای هر ریشه یک رتبه نگه دار، که کران بالای ارتفاع است. در union، ریشهٔ کم‌رتبه‌تر را زیر ریشهٔ پررتبه‌تر بگذار و فقط وقتی دو رتبه برابرند، رتبهٔ ریشهٔ جدید یکی زیاد می‌شود. نتیجه: درختی با رتبهٔ r دست‌کم 2ʳ عنصر دارد، پس ارتفاع هیچ درختی از ⌊log₂ n⌋ بیشتر نمی‌شود. در اجرای ما، بدترین ترتیب ادغام‌ها با ۱۰۲۴ عنصر دقیقاً ارتفاع ۱۰ ساخت و با ۶۵۵۳۶ عنصر ارتفاع ۱۶.

ترفند دوم: فشرده‌سازی مسیر

در find، بعد از پیدا کردن ریشه، همهٔ گره‌های سر راه را مستقیم به ریشه وصل کن. یک find روی عمیق‌ترین گرهٔ یک زنجیرهٔ ۱۶ تایی، در اجرای ما کل زنجیره را به ارتفاع ۱ رساند. هزینهٔ آن find زیاد است، ولی findهای بعدی تقریباً رایگان می‌شوند؛ این همان ایدهٔ تحلیل سرشکن است.

هر دو با هم

α تابع معکوس آکرمان است و برای هر n که در عمل پیش می‌آید حداکثر ۴ است. پس هر عمل به‌طور سرشکن تقریباً O(1) است. این کران سرشکن است، نه بدترین حالت یک عمل: یک find تکی هنوز می‌تواند تا O(log n) طول بکشد.

کاربرد کنکوری اصلی یونیون‌فایند الگوریتم کراسکال است: یال‌ها را مرتب کن و هر یالی را که دو مجموعهٔ مختلف را وصل می‌کند بپذیر. زمان کل O(m log m) است و گلوگاهش مرتب‌سازی یال‌هاست، نه یونیون‌فایند.

مرتب‌سازی: کران پایین مقایسه‌ای

هر مرتب‌سازی که فقط با مقایسهٔ دو عنصر کار کند، مثل ادغامی و سریع و هرمی، یک درخت تصمیم است. این درخت باید برای هر کدام از n! ترتیب ممکن یک برگ داشته باشد، پس ارتفاعش، یعنی تعداد مقایسه در بدترین حالت، دست‌کم ⌈log₂ n!⌉ است:

مرتب‌سازی در زمان خطی

برای شکستن کران n log n باید از چیزی جز مقایسه استفاده کرد، مثل خود مقدار کلیدها. سه روش معروف:

• مرتب‌سازی شمارشی: برای کلیدهای صحیح در بازهٔ ۰ تا k − ۱. تعداد هر مقدار را می‌شمارد، جمع تجمعی می‌گیرد و هر عنصر را سر جایش می‌گذارد. زمان O(n + k) و پایدار است؛ یعنی عنصرهای با کلید برابر ترتیب ورودی‌شان را حفظ می‌کنند.
• مرتب‌سازی مبنایی: کلیدهای d رقمی را رقم به رقم، از کم‌ارزش‌ترین رقم، با یک مرتب‌سازی پایدار مثل شمارشی مرتب می‌کند. زمان O(d(n + k)) است که k تعداد مقدارهای ممکن هر رقم است.
• مرتب‌سازی سطلی: برای عددهایی که یکنواخت در یک بازه پخش شده‌اند. بازه را به n سطل تقسیم می‌کند، هر سطل را جدا مرتب می‌کند و پشت هم می‌گذارد. زمان میانگین O(n) است.

سه تست

تست ۱: ارتفاع درخت در ادغام بر اساس رتبه

روی n عنصر فقط ادغام بر اساس رتبه، بدون فشرده‌سازی مسیر، به کار رفته است. بیشترین ارتفاع ممکن یک درخت چقدر است؟ جواب ⌊log₂ n⌋ است، چون درختی با رتبهٔ r دست‌کم 2ʳ عنصر دارد. برای ۱۰۲۴ عنصر یعنی ۱۰، و این عدد واقعاً قابل‌رسیدن است.

تست ۲: مرتب کردن n عدد صحیح کوچک‌تر از n³

سریع‌ترین زمان ممکن چیست؟ اگر هر عدد را در مبنای n بنویسی، حداکثر سه رقم دارد که هر رقم بین ۰ و n − ۱ است. مرتب‌سازی مبنایی با سه گذر مرتب‌سازی شمارشی، هر گذر O(n + n)، کل کار را در O(n) انجام می‌دهد. ما این را روی عددهای تصادفی اجرا کردیم و بعد از سه گذر مرتب بودند.

تست ۳: کمترین مقایسه برای مرتب کردن ۵ عنصر

هر مرتب‌سازی مقایسه‌ای در بدترین حالت چند مقایسه لازم دارد؟ ۵! = ۱۲۰ و log₂ ۱۲۰ حدود ۶٫۹ است، پس دست‌کم ۷ مقایسه. این کران برای ۵ عنصر قابل‌رسیدن هم هست.

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

اشتباه ۱: «شمارشی همیشه خطی است»

زمان مرتب‌سازی شمارشی O(n + k) است، نه O(n). اگر کلیدها تا n² باشند، زمانش O(n²) می‌شود و از ادغامی بدتر است. راه درست برای کلیدهای بزرگ همان مرتب‌سازی مبنایی است که بازهٔ بزرگ را به چند رقم کوچک می‌شکند.

اشتباه ۲: مبنایی با مرتب‌سازی ناپایدار

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

اشتباه ۳: «ادغام بر اساس رتبه یعنی α(n)»

ادغام بر اساس رتبه به‌تنهایی هر عمل را O(log n) نگه می‌دارد، نه α(n). کران تقریباً ثابت α(n) فقط وقتی به دست می‌آید که هر دو ترفند با هم به کار بروند، و آن هم کران سرشکن است، نه بدترین حالت یک عمل.

پرسش‌های پرتکرار

چرا مرتب‌سازی شمارشی از کران n log n سریع‌تر است؟

چون مقایسه‌ای نیست. کران Ω(n log n) فقط برای مرتب‌سازی‌هایی است که ترتیب را با مقایسهٔ دوبه‌دو پیدا می‌کنند. شمارشی از خود مقدار کلید به‌عنوان اندیس آرایه استفاده می‌کند و به همین دلیل به بازهٔ کلیدها وابسته است.

پایدار بودن مرتب‌سازی یعنی چه؟

یعنی عنصرهایی که کلید برابر دارند، در خروجی به همان ترتیب ورودی بمانند. شمارشی و ادغامی پایدارند، سریع و هرمی در پیاده‌سازی معمول نه. در مبنایی همین ویژگی است که درستی الگوریتم را تضمین می‌کند.

زمان مرتب‌سازی سطلی در بدترین حالت چقدر است؟

اگر ورودی یکنواخت نباشد و بیشتر عنصرها در یک سطل بیفتند، زمان به مرتب‌سازی داخل آن سطل برمی‌گردد؛ با مرتب‌سازی درجی یعنی O(n²). زمان خطی فقط میانگین و برای ورودی یکنواخت است.

α(n) چقدر کوچک است؟

برای هر اندازهٔ ورودی که در عمل و در تست‌ها پیش می‌آید، حداکثر ۴ است. برای همین در تست‌ها معمولاً O(m·α(n)) را «تقریباً خطی» می‌نامند.

این مبحث در کلاس

من ارشدم را در دانشگاه صنعتی شریف، در نرم‌افزار با گرایش الگوریتم و محاسبات گرفتم. یونیون‌فایند و مرتب‌سازی‌ها، از کران پایین مقایسه‌ای تا مرتب‌سازی خطی، بخشی از دورهٔ داده‌ساختار و الگوریتم من‌اند؛ با ویدیو، جزوهٔ کامل و تست‌های حل‌شده. از ۱۲ تست داده‌ساختار و الگوریتم کنکور ۱۴۰۵، نُه‌تا پیش‌تر در کلاس کار شده بود؛ سند این مقایسه در صفحهٔ مستندات هست. دوره‌ها به‌زودی روی همین سایت منتشر می‌شوند و ویدیوی رایگان چند جلسه از کلاس‌هایم هم به‌زودی در صفحهٔ ویدیوهای رایگان همین سایت قرار می‌گیرد.

قدم بعدی تو

این سه سؤال را جواب بده: ۱) با ادغام بر اساس رتبه روی ۲۰۰۰ عنصر، بیشترین ارتفاع ممکن چند است؟ ۲) مرتب کردن n عدد صحیح در بازهٔ ۰ تا n² − ۱ در بهترین حالت چه زمانی دارد؟ ۳) کمترین تعداد مقایسه در بدترین حالت برای مرتب کردن ۴ عنصر چند است؟

جواب‌ها: ۱) ۱۰، چون ⌊log₂ ۲۰۰۰⌋ = ۱۰. ۲) O(n) با مبنایی در مبنای n و دو گذر. ۳) ۵، چون ⌈log₂ ۲۴⌉ = ۵.