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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مرتب سازی تعدادی وزنه بر اساس وزنشان و با استفاده از یک ترازو، به یک الگوریتم مرتب سازی مقایسه‌ای نیاز دارد.

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

۱ اگر 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 مرحله پایان پذیرد، نمی‌توان بیش تر از 2f(n) مورد را تشخیص داد چرا که مقادیر متمایز هستند و نتیجه هر مقایسه دقیقاً دو حالت دارد. در نتیجه: 2^{f(n)}\geq n! یا آن که f(n)\geq\log_2(n!)

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

\log_2(n!) همان \Omega(n \log_2 n) است.

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

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

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

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

با این وجود، غیرممکن است که به طور میانگین با کمتر از !log2n تعداد مقایسه، مرتب‌سازی انجام گردد. این موضوع با استفاده از مفاهیم نظریه اطلاعات به سادگی قابل تبیین است. آنتروپی شانون برای همچین جایگشتی، !log2n بیت است. از آن جا که یک نتیجهٔ یک مقایسه، دو حالت دارد بیشینه اطلاعاتی که به دست می‌آید، یک بیت است. در نتیجه بعد از k بار مقایسه، آنتروپی باقیمانده جایگشت‌ها به طور میانگین و حداقل، log2(n!) - k تعداد بیت است. برای انجام مرتب‌سازی، اطلاعات کامل لازم است لذا آنتروپی باقیمانده بایستی 0 گردد. برای تحقق این امر لازم است k برابر با !log2n باشد. باید دقت داشت که این موضوع با بحث بدترین حالتی که پیش از این انجام شد، متفاوت است. در آن بحث اجازه گرد کردن اعداد به نزدیک ترین عدد صحیح را نداریم. برای مثال، به ازای n=3، محدوده پایین برای بدترین حالت 3 است، برای حالت میانگین تقریباً برابر با 2.58 است. در صورتی که در حالت بالا این مقدار برابر با 2.67 است. در حالتی که مقادیر مختلف برای کلید یکسان به دست بیاید، هیچ گونه تفسیر آماری برای «حالت میانگین» وجود ندارد. بنابراین بحثی که شد بدون در نظر گرفتن فرضیات دقیق ارائه شده قابل استفاده نیست.

منابع[ویرایش]

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

  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