مرتب‌سازی مقایسه‌ای

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

۱ اگر a≤b و b≤c آن گاه حتماً عدد a کوچکتر مساوی عدد c است.

۲ به ازای تمامی اعداد مثل a و b، رابطهٔ a<b یا a≤b صدق می‌کند.

مثال‌ها

برخی از الگوریتم‌های شناخته شده که بر اساس همسنجی اعضا عمل می‌کنند، به شرح زیر هستند:

نمونه‌هایی از الگوریتم‌هایی که در آن‌ها مرتب‌سازی بر اساس همسنجی نیست، عبارتند از:

مرتب‌سازی مبنایی(وارسی بیت به بیت)
مرتب‌سازی شمارشی (اندیس‌ها از مقادیر کلیدها استفاده می‌کنند)
مرتب‌سازی سطلی (وارسی بیت‌های کلید)

محدودیت‌های کارایی و مزایای الگوریتم‌های مختلف

محدودیت‌های اساسی در الگوریتم‌های مرتب‌سازی همسنجشی وجود دارد. یک مرتب‌سازی مقایسه‌ای بایستی تعداد اعمال مقایسه اش از (Ω(n log n فراتر نرود.^[۱] مرتب‌سازی ادغامی، هرمی و intro از نظر تعداد اعمالی که برای مقایسه باید انجام دهند، در شرایط مطلوبی هستند. اگر چه این سنجه، عملیات دیگر را نادیده می‌گیرد. مرتب‌سازی مبنایی، شمارشی و سطلی عملکردی از مرتبه (O(n هستند و عملیاتی جز مقایسه انجام می‌دهند. با این حال، مرتب‌سازی همسنجشی یک مزیت قابل توجه دارد و آن این است که عمل همسنجی برای مرتب‌سازی انواع داده قابل استفاده‌است. هم چنین می‌توان با برعکس کردن نتیجهٔ مرتب‌سازی، اعضای مرتب شده را به صورت معکوس روئیت کرد. برای مثال با استفاده از یک الگوریتم مقایسه‌ای می‌توان لیستی از تاپل‌هایی که به صورت lexicographic هستند را مرتب کرد:

function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
    if lefta ≠ righta
        return compare(lefta, righta)
    else if leftb ≠ rightb
        return compare(leftb, rightb)
    else
        return compare(leftc, rightc)

مقایسه در یک مرحله انجام می‌شود و نتیجه اش یا 'بزرگتر است از'، 'یا کوچکتر است از' یا 'مساوی است'، به دست می‌آید.

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

تعداد مقایسه‌های لازم در الگوریتم‌های مرتب‌سازی مقایسه‌ای حداقل به نسبت $n\log(n)$ افزایش می‌یابد که n تعداد اعضای لیست است. برای تحلیل بدترین حالت صرف زمان در این نوع الگوریتم‌ها، فرض می‌کنیم لیستی از اعداد متمایز داریم و به تعداد !n جایگشت لازم است برای آن که لیست مرتب شود. اگر الگوریتم بعد از حداکثر (f(n مرحله پایان پذیرد، نمی‌توان بیش تر از 2^f(n) مورد را تشخیص داد چرا که مقادیر متمایز هستند و نتیجه هر مقایسه دقیقاً دو حالت دارد. در نتیجه: $2^{f(n)}\geq n!$ یا آن که $f(n)\geq \log _{2}(n!)$

از طریق تقریب استرلینگ می‌دانیم:

$\log _{2}(n!)$ همان $\Omega (n\log _{2}n)$ است.

با استفاده از این موضوع حد پایین تحلیل زمانی به دست می‌آید. مشابه الگوریتم‌هایی که از این دست الگوریتم‌ها پیروی می‌کنند، حد بالای تحلیل زمانی در بدترین حالت به دست می‌آید. استدلال بالا یک تحلیل مطلق را به جای یک تحلیل مجانبی برای حد پایین بیان می‌کند. حد پایین تقریباً خوب است چرا که با استفاده از یک مرتب‌سازی ادغامی ساده در محدوده خطی قابل دستیابی است. اما این موضوع دقیق نیست؛ برای مثال برای آن که ۱۳ عنصر را مرتب کنیم، به ۳۴ مقایسه نیاز داریم.^[۲]. مشخص کردن تعداد دقیق مقایسه‌ها برای یک سری ورودی‌های مشخص ولو با تعداد کم، کار پیچیده‌ای است و هیچ فرمول ساده‌ای برای این مسئله وجود ندارد. برای تعداد کمی از مقادیر محاسبه شده این پیوند را مشاهده کنید. A036604

حد پایین برای تعداد همسنجی‌ها به طور میانگین

یک محدوده مشابه برای میانگین تعداد مقایسه‌ها به کار برده می‌شود. فرض کنیم:

تمامی مقادیر متمایز هستند. یعنی نتیجه کلیه مقایسه‌ها یا a>b یا a<b است.
ورودی به صورت یک جایگشت تصادفی است که از یک مجموعه یکنواخت شامل تمامی جایگشت‌های ممکن از nعنصر انتخاب شده‌است.

با این وجود، غیرممکن است که به‌طور میانگین با کمتر از !log₂n تعداد مقایسه، مرتب‌سازی انجام گردد. این موضوع با استفاده از مفاهیم نظریه اطلاعات به سادگی قابل تبیین است. آنتروپی شانون برای همچین جایگشتی، !log₂n بیت است. از آن جا که یک نتیجهٔ یک مقایسه، دو حالت دارد بیشینه اطلاعاتی که به دست می‌آید، یک بیت است. در نتیجه بعد از k بار مقایسه، آنتروپی باقی‌مانده جایگشت‌ها به‌طور میانگین و حداقل، log₂(n!) - k تعداد بیت است. برای انجام مرتب‌سازی، اطلاعات کامل لازم است لذا آنتروپی باقی‌مانده بایستی ۰ گردد. برای تحقق این امر لازم است k برابر با !log₂n باشد. باید دقت داشت که این موضوع با بحث بدترین حالتی که پیش از این انجام شد، متفاوت است. در آن بحث اجازه گرد کردن اعداد به نزدیک ترین عدد صحیح را نداریم. برای مثال، به ازای n=۳، محدوده پایین برای بدترین حالت ۳ است، برای حالت میانگین تقریباً برابر با ۲٫۵۸ است. در صورتی که در حالت بالا این مقدار برابر با ۲٫۶۷ است. در حالتی که مقادیر مختلف برای کلید یکسان به دست بیاید، هیچ گونه تفسیر آماری برای «حالت میانگین» وجود ندارد؛ بنابراین بحثی که شد بدون در نظر گرفتن فرضیات دقیق ارائه شده قابل استفاده نیست.

منابع

ویکی‌پدیا:پانویس‌ها

↑ PlanetMath
↑ Marcin Peczarski: The Ford-Johnson algorithm is still unbeaten for less than 47 elements. Inf. Process. Lett. 101(3): 126-128 (2007) doi:10.1016/j.ipl.2006.09.001

دانلد کنوت. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.1: Minimum-Comparison Sorting, pp. 180–۱۹۷.
توماس اچ کورمن, Charles E. Leiserson, رونالد ریوست, and کلیفورد استین. مقدمه‌ای بر الگوریتم‌ها, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.1: Lower bounds for sorting, pp. 165–۱۶۸.

[1] PlanetMath

[2] Marcin Peczarski: The Ford-Johnson algorithm is still unbeaten for less than 47 elements. Inf. Process. Lett. 101(3): 126-128 (2007) doi:10.1016/j.ipl.2006.09.001

[۱]

[۲]