موضوع مقاله: مرتب‌سازی مقایسه‌ای | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مرتب‌سازی مقایسه‌ای | مقدمه: در علم کامپیوتر معمولاً الگوریتم‌های مرتب‌سازی بر اساس معیارهای مختلفی چون پیچیدگی زمانی، حافظه، پایداری و همسنجشی (مقایسه‌ای) بودن یا نبودن طبقه‌بندی می‌شوند. | ## بخش 1: مرتب‌سازی مقایسه‌ای | یک الگوریتم مرتب‌سازی همسنجشی (مقایسه‌ای)، الگوریتمی است که در هر مرحله بر حسب صلاح دید الگوریتم، دو خانه از یک آرایه را انتخاب می‌کند و آن دو را با هم می‌سنجد و در صورت نیاز درایه‌های آن‌ها را با هم عوض می‌کند. نحوهٔ عملکرد الگوریتم به صورت زیر است: ۱ اگر a≤b و b≤c آن گاه حتماً عدد a کوچکتر مساوی عدد c است. مثال‌ها برخی از الگوریتم‌های شناخته شده که بر اساس همسنجی اعضا عمل می‌کنند، به شرح زیر هستند: مرتب‌سازی سریع مرتب‌سازی هرمی مرتب‌سازی ادغامی مرتب‌سازی Intro مرتب‌سازی درجی مرتب‌سازی انتخابی مرتب‌سازی حبابی مرتب‌سازی فرد-زوج مرتب‌سازی کوکتل مرتب‌سازی چرخه‌ای مرتب‌سازی فورد-جانسون مرتب‌سازی روان مرتب‌سازی زمانی نمونه‌هایی از الگوریتم‌هایی که در آن‌ها مرتب‌سازی بر اساس همسنجی نیست، عبارتند از: مرتب‌سازی مبنایی(وارسی بیت به بیت) مرتب‌سازی شمارشی (اندیس‌ها از مقادیر کلیدها استفاده می‌کنند) مرتب‌سازی سطلی (وارسی بیت‌های کلید) محدودیت‌های کارایی و مزایای الگوریتم‌های مختلف محدودیت‌های اساسی در الگوریتم‌های مرتب‌سازی همسنجشی وجود دارد. مرتب‌سازی مبنایی، شمارشی و سطلی عملکردی از مرتبه (O(n هستند و عملیاتی جز مقایسه انجام می‌دهند. با این حال، مرتب‌سازی همسنجشی یک مزیت قابل توجه دارد و آن این است که عمل همسنجی برای مرتب‌سازی انواع داده قابل استفاده‌است. هم چنین می‌توان با برعکس کردن نتیجهٔ مرتب‌سازی، اعضای مرتب شده را به صورت معکوس روئیت کرد. تعداد همسنجی‌های لازم برای مرتب‌سازی یک لیست تعداد مقایسه‌های لازم در الگوریتم‌های مرتب‌سازی مقایسه‌ای حداقل به نسبت افزایش می‌یابد که n تعداد اعضای لیست است. | ## بخش 2: مرتب‌سازی مقایسه‌ای | برای تحلیل بدترین حالت صرف زمان در این نوع الگوریتم‌ها، فرض می‌کنیم لیستی از اعداد متمایز داریم و به تعداد !n جایگشت لازم است برای آن که لیست مرتب شود. اگر الگوریتم بعد از حداکثر (f(n مرحله پایان پذیرد، نمی‌توان بیش تر از 2f(n) مورد را تشخیص داد چرا که مقادیر متمایز هستند و نتیجه هر مقایسه دقیقاً دو حالت دارد. مشابه الگوریتم‌هایی که از این دست الگوریتم‌ها پیروی می‌کنند، حد بالای تحلیل زمانی در بدترین حالت به دست می‌آید. حد پایین تقریباً خوب است چرا که با استفاده از یک مرتب‌سازی ادغامی ساده در محدوده خطی قابل دستیابی است. مشخص کردن تعداد دقیق مقایسه‌ها برای یک سری ورودی‌های مشخص ولو با تعداد کم، کار پیچیده‌ای است و هیچ فرمول ساده‌ای برای این مسئله وجود ندارد. حد پایین برای تعداد همسنجی‌ها به طور میانگین یک محدوده مشابه برای میانگین تعداد مقایسه‌ها به کار برده می‌شود. ورودی به صورت یک جایگشت تصادفی است که از یک مجموعه یکنواخت شامل تمامی جایگشت‌های ممکن از nعنصر انتخاب شده‌است. | ## بخش 3: مرتب‌سازی مقایسه‌ای | با این وجود، غیرممکن است که به‌طور میانگین با کمتر از !log2n تعداد مقایسه، مرتب‌سازی انجام گردد. از آن جا که یک نتیجهٔ یک مقایسه، دو حالت دارد بیشینه اطلاعاتی که به دست می‌آید، یک بیت است. در نتیجه بعد از k بار مقایسه، آنتروپی باقی‌مانده جایگشت‌ها به‌طور میانگین و حداقل، log2(n!) - k تعداد بیت است. برای انجام مرتب‌سازی، اطلاعات کامل لازم است لذا آنتروپی باقی‌مانده بایستی ۰ گردد. باید دقت داشت که این موضوع با بحث بدترین حالتی که پیش از این انجام شد، متفاوت است. برای مثال، به ازای n=۳، محدوده پایین برای بدترین حالت ۳ است، برای حالت میانگین تقریباً برابر با ۲٫۵۸ است. | ## جمع‌بندی | در حالتی که مقادیر مختلف برای کلید یکسان به دست بیاید، هیچ گونه تفسیر آماری برای «حالت میانگین» وجود ندارد؛ بنابراین بحثی که شد بدون در نظر گرفتن فرضیات دقیق ارائه شده قابل استفاده نیست.