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

در علم کامپیوتر معمولاً الگوریتم های مرتب سازی بر اساس معیارهای مختلفی چون پیچیدگی زمانی، حافظه، پایداری و همسنجشی ( مقایسه ای ) بودن یا نبودن طبقه بندی می شوند. یک الگوریتم مرتب سازی همسنجشی ( مقایسه ای ) ، الگوریتمی است که در هر مرحله بر حسب صلاح دید الگوریتم، دو خانه از یک آرایه را انتخاب می کند و آن دو را با هم می سنجد و در صورت نیاز درایه های آن ها را با هم عوض می کند. نحوهٔ عملکرد الگوریتم به صورت زیر است:
۱ اگر a≤b و b≤c آن گاه حتماً عدد a کوچکتر مساوی عدد c است.
۲ به ازای تمامی اعداد مثل a و b، رابطهٔ a< b یا a≤b صدق می کند.
برخی از الگوریتم های شناخته شده که بر اساس همسنجی اعضا عمل می کنند، به شرح زیر هستند:
• مرتب سازی سریع
• مرتب سازی هرمی
• مرتب سازی ادغامی
• مرتب سازی Intro
• مرتب سازی درجی
• مرتب سازی انتخابی
• مرتب سازی حبابی
• مرتب سازی فرد - زوج
• مرتب سازی کوکتل
• مرتب سازی چرخه ای
• مرتب سازی فورد - جانسون
• مرتب سازی روان
• مرتب سازی زمانی
نمونه هایی از الگوریتم هایی که در آن ها مرتب سازی بر اساس همسنجی نیست، عبارتند از:
• مرتب سازی مبنایی ( وارسی بیت به بیت )
• مرتب سازی شمارشی ( اندیس ها از مقادیر کلیدها استفاده می کنند )
• مرتب سازی سطلی ( وارسی بیت های کلید )
محدودیت های اساسی در الگوریتم های مرتب سازی همسنجشی وجود دارد. یک مرتب سازی مقایسه ای بایستی تعداد اعمال مقایسه اش از ( Ω ( 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 ) مقایسه در یک مرحله انجام می شود و نتیجه اش یا 'بزرگتر است از'، 'یا کوچکتر است از' یا 'مساوی است'، به دست می آید.