مرتب سازی مقایسه ای
تعریف
مرتب سازی مقایسه ای نوعی الگوریتم مرتب سازی است که در آن عناصر را تحت یک عملگر مقایسه ای میخواند و مشخص میکند که کدامیک از دو عضو باید در لیست مرتب شده اول بیاید و تنها نیاز آن این است که عملگر دو ویژگی از یک ترتیب کامل را داشته باشد:
1. (خاصیت تراگذری) اگر $b \le c$ و $a \le b$ در نتیجه $a \le c$.
2. (تمامیت) برای هر $a$ و $b$: یا $a \le b$ یا $b \le a$.
ممکن است که هم $a \le b$ و هم $b \le a$ هر دو هم زمان درست باشند دراین صورت هریک از آن دو ممکن است اول بیاید. در یک مرتب سازی پایدار ترتیب ورودی در چنین وضعیتی ترتیب نهایی را مشخص میکند یعنی ورودیهای یکسان در خروجی به ترتیبی که در ورودی آمده اند قرار می گیرند.
محدودیت ها
محدودیتهای اساسی در الگوریتمهای مرتبسازی مقایسه ای وجود دارد. می توان اثبات کرد هر مرتبسازی مقایسهای $\mathcal{\Omega}(n \log n)$ است. مرتبسازی ادغامی از نظر تعداد اعمالی که برای مقایسه باید انجام دهند، در شرایط مطلوبی است. مرتبسازی مبنایی، شمارشی و سطلی عملکردی از مرتبه $\mathcal{O}(n)$ دارند و عملیاتی بجز مقایسه نیز انجام میدهند.
مزیت ها
مرتبسازی مقایسه ای یک مزیت قابل توجه دارد و آن این است که عمل مقایسه برای مرتبسازی انواع داده قابل استفادهاست. هم چنین میتوان با برعکس کردن نتیجهٔ مرتبسازی، اعضای مرتب شده را به صورت معکوس روئیت کرد.
مثال: با استفاده از یک الگوریتم مقایسهای میتوان لیستی از دوتاییهای شامل نام و شمارهی دانشجویی دانشجویان را ابتدا بر اساس نام ودر صورت برابری بر اساس شمارهی دانشجویی مرتب کرد:
