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

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

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

۲ به ازای تمامی اعداد مثل a و b، رابطهٔ an\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) است.

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

## حد پایین برای تعداد همسنجی‌ها به طور میانگین
یک محدوده مشابه برای میانگین تعداد مقایسه‌ها به کار برده می‌شود. فرض کنیم:
* تمامی مقادیر متمایز هستند. یعنی نتیجه کلیه مقایسه‌ها یا *a>b* یا *a<b* است.
* ورودی به صورت یک جایگشت تصادفی است که از یک مجموعه یکنواخت شامل تمامی جایگشت‌های ممکن از *n*عنصر انتخاب شده‌است.
با این وجود، غیرممکن است که به‌طور میانگین با کمتر از *!log<sub>2</sub>*n* تعداد مقایسه، مرتب‌سازی انجام گردد. این موضوع با استفاده از مفاهیم [[نظریه اطلاعات]] به سادگی قابل تبیین است. [[آنتروپی شانون]] برای همچین جایگشتی، *!log2*n* بیت است. از آن جا که یک نتیجهٔ یک مقایسه، دو حالت دارد بیشینه اطلاعاتی که به دست می‌آید، یک بیت است. در نتیجه بعد از k بار مقایسه، آنتروپی باقی‌مانده جایگشت‌ها به‌طور میانگین و حداقل، *log<sub>2</sub>(n!)&nbsp;-&nbsp;k* تعداد بیت است. برای انجام مرتب‌سازی، اطلاعات کامل لازم است لذا آنتروپی باقی‌مانده بایستی ۰ گردد. برای تحقق این امر لازم است *k* برابر با *!log<sub>2</sub>*n* باشد. 
باید دقت داشت که این موضوع با بحث بدترین حالتی که پیش از این انجام شد، متفاوت است. در آن بحث اجازه گرد کردن اعداد به نزدیک ترین [[عدد صحیح]] را نداریم. برای مثال، به ازای n=۳، محدوده پایین برای بدترین حالت ۳ است، برای حالت میانگین تقریباً برابر با ۲٫۵۸ است. در صورتی که در حالت بالا این مقدار برابر با ۲٫۶۷ است. در حالتی که مقادیر مختلف برای کلید یکسان به دست بیاید، هیچ گونه تفسیر آماری برای «حالت میانگین» وجود ندارد؛ بنابراین بحثی که شد بدون در نظر گرفتن فرضیات دقیق ارائه شده قابل استفاده نیست.

== منابع ==
[[ویکی‌پدیا:پانویس‌ها]] 



* [[دانلد کنوت]]. *The Art of Computer Programming*, Volume 3: *Sorting and Searching*, Second Edition. Addison-Wesley, 1997. . Section 5.3.1: Minimum-Comparison Sorting, pp. &nbsp;180&ndash;۱۹۷.
* [[توماس اچ کورمن]], [[Charles E. Leiserson]], [[رونالد ریوست]], and [[کلیفورد استین]]. *مقدمه‌ای بر الگوریتم‌ها'', Second Edition. MIT Press and McGraw-Hill, 2001. . Section 8.1: Lower bounds for sorting, pp. &nbsp;165&ndash;۱۶۸.

رده:الگوریتم‌های مرتب‌سازی
رده:مرتب‌سازی‌های سنجشی