مرتب‌سازی پایدار

الگوریتم‌های مرتب‌سازی پایدار ترتیب را بین داده‌های دارای کلیدهای برابر حفظ می‌کنند. اگرتمامی کلیدها متفاوت باشند، تمایزبراساس پایداری بین الگوریتم‌ها نیاز نیست.اما اگر داده‌های با کلیدهای یکسان وجود داشته باشد، الگوریتم مراتب سازی ما در صورتی پایدار است که اگر ۲ رکورد مثلابه نام‌های S و R با کلیدهای یکسان داشته باشیم، و R قبل از S در لیست اصلی ما آمده باشد، آنگاه در لیست مرتب شده نیز R قبل از S بیاید. هنگامی که رکوردهای یکسان قابل تشخیص نباشد، مانند اعداد صحیح یا به‌طور عام، زمانی که داده تنها از رکورد تشکیل شده باشد، پایداری دارای اهمیت چندانی نمی‌باشد.

فرض کنید اعداد زیر برحسب رکوردهای اولشان مرتب شوند:

    (۲, ۴)  (۷, ۳)  (۱, ۳)  (۶, ۵)

در این مثال دو نتیجه متفاوت ممکن است رخ بدهد، اول اینکه ترتیب نسبی داده‌ها با رکورد یکسان حفظ شودو دیگر این که این ترتیب حفظ نشود:

    (۶, ۵)  (۲, ۴)  (۱, ۳)  (۷, ۳)       (اگر ترتیب اصلی تغییر کند)

    (۶, ۵)  (۲, ۴)  (۷, ۳)  (۱, ۳)       (اگر ترتیب اصلی حفظ شود)

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

مثال: مرتب سازی زوج اعداد بر اساس مؤلفه اول، و سپس دوم:

    (۴ ،۲)  (۳ ،۷)  (۳ ،۱)  (۵ ،۶)       (ترتیب اصلی)
    (۳ ،۱)  (۴ ،۲)  (۵ ،۶)  (۳ ،۷)       (پس مرتب سازی بر اساس مؤلفه دوم)
    (۳ ،۱)  (۳ ،۷)  (۴ ،۲)  (۵ ،۶)       (پس از مرتب سازی بر اساس مؤلفه اول)

از طرف دیگر:

    (۳ ،۷)  (۳ ،۱) (۴ ،۲) (۵ ،۶)          (پس از مرتب سازی بر اساس مؤلفه اول)

    (۳ ،۱)  (۴ ،۲)  (۵ ،۶)  (۳ ،۷)        (پس مرتب سازی بر اساس مؤلفه دوم مرتب سازی بر اساس مؤلفه اول به هم می‌خورد)

الگوریتم‌های مرتب سازی از لحاظ پایداری

الگوریتم‌های مرتب سازی از لحاظ پایداری به ۳ دسته تقسیم می‌شوند: ۱-الگوریتم‌های پایدار:این دسته شامل مرتب سازی هائی از قبیل مرتب سازی حبابی، مرتب سازی درجی، درخت دودوئی، مرتب سازی کتابخانه‌ای و ...می‌باشند.

۲-الگوریتم‌های ناپایدار:مرتب سازی ها مرتب سازی صدفی، مرتب سازی هیپ، مرتب سازی شانه‌ای، مرتب سازی صبورانه و ... از این دسته به شمار می‌روند.

۳-الگوریتم هائی که پایداری آن‌ها به پیاده‌سازی بستگی دارد:از این قبیل الگوریتم‌ها می‌توان به مرتب سازی مرتب سازی انتخابی، مرتب سازی ادغامی در جا ومرتب سازی سریع اشاره نمود.