شکستن مانع n log n: توضیح الگوریتم‌های مرتب‌سازی زمان-خطی

چرا n log n یک مانع بنیادین به‌نظر می‌رسد

هر الگوریتم مرتب‌سازی مبتنی بر مقایسه که تاکنون در این مجموعه بحث شده — insertion sort، heapsort، و quicksort — در بهترین حالت به زمان اجرای Θ(n log n) دست می‌یابد. این یک پرسش طبیعی مطرح می‌کند: آیا n log n یک محدودیت بنیادین برای مرتب‌سازی است، یا صرفاً محدودیت الگوریتم‌های خاصی که تاکنون مطالعه شده‌اند؟

اثبات کران پایین Ω(n log n) برای مرتب‌سازی‌های مقایسه‌ای

یک Comparison Sort (مرتب‌سازی مقایسه‌ای) هر الگوریتم مرتب‌سازی‌ای است که ترتیب نسبی عناصر را فقط از طریق مقایسه بین جفت‌های عناصر تعیین می‌کند. این اثبات کران پایین از یک مدل Decision Tree (درخت تصمیم) استفاده می‌کند: یک درخت دودویی انتزاعی که هر توالی ممکن از مقایسه‌هایی که یک الگوریتم ممکن است انجام دهد را نمایش می‌دهد، جایی که هر برگ به یک جایگشت نهایی ممکن از ورودی متناظر است.

برای n عنصر، n! جایگشت ممکن وجود دارد،
و هرکدام باید حداقل با یک برگ در درخت تصمیم متناظر باشد

یک درخت دودویی با ارتفاع h حداکثر 2^h برگ دارد،
پس درخت باید برآورده کند: 2^h ≥ n!

گرفتن لگاریتم از هر دو سمت:
h ≥ log₂(n!)

با استفاده از تقریب استرلینگ، log₂(n!) = Θ(n log n)

بنابراین: h = Ω(n log n)

از آنجا که ارتفاع درخت تصمیم نشان‌دهنده تعداد مقایسه‌های بدترین‌حالت است که الگوریتم انجام می‌دهد، این ثابت می‌کند هر الگوریتم مرتب‌سازی مبتنی بر مقایسه باید در بدترین حالت Ω(n log n) مقایسه انجام دهد. این یعنی heapsort و merge sort، هر دو با دستیابی به Θ(n log n)، در میان الگوریتم‌های مبتنی بر مقایسه Asymptotically Optimal (بهینه مجانبی) هستند — هیچ مرتب‌سازی مقایسه‌ای نمی‌تواند اساساً بهتر عمل کند.

شکستن مانع: مرتب‌سازی بدون مقایسه

کران پایین Ω(n log n) به‌طور خاص برای الگوریتم‌های مبتنی بر مقایسه اعمال می‌شود. اگر یک الگوریتم بتواند اطلاعات اضافی درباره عناصری که مرتب می‌شوند را بهره‌برداری کند، مانند دانستن اینکه آن‌ها اعداد صحیح درون یک بازه محدودند، می‌تواند در زمان خطی با اجتناب کامل از مقایسه مرتب کند.

Counting Sort: بهره‌برداری از یک بازه کوچک شناخته‌شده

Counting Sort وقتی کار می‌کند که ورودی شامل اعداد صحیح درون یک بازه شناخته‌شده [0, k] باشد. به‌جای مقایسه عناصر، تعداد عناصر برابر با هر مقدار ممکن را می‌شمارد، سپس از این شمارش‌ها برای تعیین مستقیم موقعیت نهایی هر عنصر استفاده می‌کند.

COUNTING-SORT(A, B, n, k):
  فرض کن C[0..k] یک آرایه جدید باشد، مقداردهی‌شده با 0
  برای i = 1 تا n:
      C[A[i]] = C[A[i]] + 1
  // C[i] اکنون تعداد عناصر برابر با i را دارد

  برای i = 1 تا k:
      C[i] = C[i] + C[i - 1]
  // C[i] اکنون تعداد عناصر ≤ i را دارد

  برای i = n کاهشی تا 1:
      B[C[A[i]]] = A[i]
      C[A[i]] = C[A[i]] - 1
  B را برگردان

مرور یک مثال کوچک با ورودی [2, 5, 3, 0, 2, 3, 0, 3] و بازه [0, 5]:

گام شمارش، C[v] = تعداد مقدار v:
C = [2, 0, 2, 3, 0, 1]   (ایندکس‌های 0 تا 5)

گام تجمعی، C[v] = تعداد مقادیر ≤ v:
C = [2, 2, 4, 7, 7, 8]

قرار دادن عناصر از انتهای A (برای پایداری)،
با استفاده از شمارش‌های تجمعی برای یافتن موقعیت هر عنصر،
خروجی مرتب‌شده تولید می‌کند: [0, 0, 2, 2, 3, 3, 3, 5]

الگوریتم در زمان Θ(n + k) اجرا می‌شود — واقعاً خطی وقتی k = O(n). یک ویژگی مهم Stability (پایداری) است: عناصر با مقادیر برابر ترتیب نسبی اصلی‌شان را حفظ می‌کنند، که وقتی counting sort به‌عنوان یک زیرروال استفاده می‌شود، همان‌طور که در radix sort زیر هست، اهمیت دارد.

Radix Sort: گسترش Counting Sort به اعداد چند-رقمی

Radix Sort رویکرد محدود-به-بازه counting sort را به اعدادی با ارقام بسیار گسترش می‌دهد، با مرتب‌سازی یک موقعیت رقم در یک زمان، از کم‌ارزش‌ترین رقم تا با‌ارزش‌ترین.

RADIX-SORT(A, n, d):
  برای i = 1 تا d:
      از یک مرتب‌سازی پایدار برای مرتب‌سازی آرایه A روی رقم i استفاده کن
      (معمولاً counting sort، چون رقم‌ها بازه کوچکی دارند)

بینش کلیدی‌ای که این را درست می‌کند ظریف است: مرتب‌سازی باید از کم‌ارزش‌ترین رقم تا با‌ارزش‌ترین پیش برود، و مرتب‌سازی استفاده‌شده در هر موقعیت رقم باید Stable (پایدار) باشد، و ترتیب نسبی را در میان عناصر با رقم‌های برابر در آن موقعیت حفظ کند. این تضمین می‌کند وقتی با‌ارزش‌ترین رقم آخرین بار مرتب می‌شود، هر برابری از قبل به‌درستی توسط رقم‌های مرتبه‌پایین‌تر مرتب‌شده در گذرهای قبلی شکسته شده است.

مثال مرتب‌سازی اعداد ۳ رقمی:
[329, 457, 657, 839, 436, 720, 355]

پس از مرتب‌سازی روی رقم یکان (پایدار):
[720, 355, 436, 457, 657, 329, 839]

پس از مرتب‌سازی روی رقم دهگان (پایدار):
[720, 329, 436, 839, 355, 457, 657]

پس از مرتب‌سازی روی رقم صدگان (پایدار):
[329, 355, 436, 457, 657, 720, 839]  — کاملاً مرتب

اگر هرکدام از d گذر رقمی از counting sort با رقم‌ها در بازه [0, k] استفاده کند، هر گذر هزینه Θ(n + k) دارد، که زمان اجرای کل Θ(d(n + k)) می‌دهد. برای اعداد صحیح با اندازه ثابت، مانند اعداد ۳۲ بیتی یا ۶۴ بیتی با تعداد ثابتی رقم، این Θ(n) است، واقعاً زمان خطی.

Bucket Sort: بهره‌برداری از یک توزیع یکنواخت شناخته‌شده

Bucket Sort وقتی خوب کار می‌کند که فرض شود عناصر ورودی به‌طور یکنواخت روی یک بازه شناخته‌شده توزیع شده‌اند، معمولاً بازه حقیقی [0, 1). این بازه را به n سطل با اندازه برابر تقسیم می‌کند، عناصر را در سطل متناظرشان توزیع می‌کند، هر سطل را به‌طور جداگانه مرتب می‌کند (معمولاً با insertion sort، چون انتظار می‌رود سطل‌ها عناصر کمی داشته باشند)، و نتایج را الحاق می‌کند.

BUCKET-SORT(A, n):
  فرض کن B[0..n-1] لیست‌های جدید خالی باشند (سطل‌ها)
  برای i = 1 تا n:
      A[i] را در لیست B[⌊n · A[i]⌋] درج کن
  برای i = 0 تا n - 1:
      لیست B[i] را با insertion sort مرتب کن
  لیست‌های B[0], B[1], ..., B[n-1] را به‌ترتیب الحاق کن

تحت فرض یک توزیع ورودی یکنواخت، تعداد مورد انتظار عناصر به‌ازای هر سطل O(1) است، پس مرتب‌سازی هر سطل کوچک با insertion sort زمان ثابت مورد انتظار می‌گیرد، که زمان اجرای کلی مورد انتظار Θ(n) می‌دهد. این یک تضمین حالت‌میانگین است، که مستقیماً به تکنیک‌های تحلیل احتمالاتی که پیش‌تر در این مجموعه بحث شد متصل می‌شود، نه یک تضمین بدترین‌حالت — اگر فرض توزیع شکست بخورد و همه عناصر در یک سطل بیفتند، کارایی به همان insertion sort به‌تنهایی تنزل می‌یابد.

انتخاب الگوریتم زمان-خطی درست

هرکدام از این سه الگوریتم عمومیت را با سرعت مبادله می‌کنند با بهره‌برداری از یک فرض خاص درباره ورودی.

Counting sort: نیازمند اعداد صحیح در یک بازه کوچک شناخته‌شده [0, k]
Radix sort:    نیازمند اعداد با رقم ثابت (یا کلیدهای طول‌ثابت)
Bucket sort:   نیازمند ورودی توزیع‌شده به‌طور یکنواخت روی یک بازه شناخته‌شده

اگر هیچ‌کدام از این فرضیات برقرار نباشند، مرتب‌سازی‌های مقایسه‌ای
مانند heapsort، merge sort، یا quicksort انتخاب
عمومی‌منظوره درست باقی می‌مانند، محدود به Ω(n log n)

چرا این مبادله بین فرضیات و سرعت اهمیت دارد

این الگوریتم‌های زمان-خطی یک موضوع تکرارشونده در طراحی الگوریتم را نشان می‌دهند: بهره‌برداری از ساختار یا محدودیت‌های شناخته‌شده روی ورودی می‌تواند به یک الگوریتم اجازه دهد یک کران پایین عمومی‌منظوره که فقط برای یک دسته گسترده‌تر و کم‌اطلاع‌تر از الگوریتم‌ها اعمال می‌شود را دور بزند. تشخیص اینکه چه زمانی داده ورودی فرضیات خاص مورد نیاز counting sort، radix sort، یا bucket sort را برآورده می‌کند می‌تواند یک وظیفه مرتب‌سازی Θ(n log n) در غیر این صورت را به یک وظیفه واقعاً زمان-خطی تبدیل کند، یک بهبود عملی قابل‌توجه برای مجموعه‌داده‌های بسیار بزرگ.