فهرست مندرجات
مرتب سازی مقایسه ای
تعریف
مرتب سازی مقایسه ای نوعی الگوریتم مرتب سازی است که در آن عناصر را تحت یک عملگر مقایسه ای می خواند و مشخص می کند که کدامیک از دو عضو باید در لیست مرتب شده اول بیاید و تنها نیاز آن این است که عملگر دو ویژگی از یک ترتیب کامل را داشته باشد : 1-(خاصیت تراگذری) اگر b< =c, a< =bدر نتیجه a< =c .
2-(تمامیت) برای هر a,b : یا a< =b یا b< =a .
ممکن است که هم b< =a و هم a< =b هر دو هم زمان درست باشند دراین صورت هریک از آن دو ممکن است اول بیاید در یک مرتب سازی پایدار ترتیب ورودی در چنین وضعیتی ترتیب نهایی را مشخص می کند یعنی ورودی های یکسان در خروجی به ترتیبی که در ورودی آمده اند قرار می گیرند.
محدودیت ها
محدودیت‌های اساسی در الگوریتم‌های مرتب‌سازی مقایسه ای وجود دارد. یک مرتب‌سازی مقایسه‌ای بایستی تعداد اعمال مقایسه اش (Ω(nlogn فراتر نرود.مرتب‌سازی ادغامی از نظر تعداد اعمالی که برای مقایسه باید انجام دهند، در شرایط مطلوبی است. مرتب‌سازی مبنایی، شمارشی و سطلی عملکردی از مرتبه (O(nدارند و عملیاتی جز مقایسه انجام می‌دهند.
مزیت ها
مرتب‌سازی مقایسه ای یک مزیت قابل توجه دارد و آن این است که عمل مقایسه برای مرتب‌سازی انواع داده قابل استفاده‌است. هم چنین می‌توان با برعکس کردن نتیجهٔ مرتب‌سازی، اعضای مرتب شده را به صورت معکوس روئیت کرد.
مثال: با استفاده از یک الگوریتم مقایسه‌ای می‌توان لیستی از دوتایی های شامل نام و شماره ی دانشجویی دانشجویان را ابتدا بر اساس نام ودر صورت برابری بر اساس شماره ی دانشجویی مرتب کرد :
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
