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

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

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

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

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

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

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

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

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

مثال:

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

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

از طرف دیگر:

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

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

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

الگوریتم‌های مرتب‌سازی از لحاظ پایداری به ۳ دسته تقسیم می‌شوند:

1. الگوریتم‌های پایدار: این دسته شامل مرتب‌سازی هائی از قبیل مرتب‌سازی حبابی، مرتب‌سازی درجی، درخت دودوئی، مرتب‌سازی کتابخانه‌ای و غیره می‌باشند.
2. الگوریتم‌های ناپایدار: مرتب‌سازی صدفی، مرتب‌سازی هیپ، مرتب‌سازی شانه‌ای، مرتب‌سازی صبورانه و غیره از این دسته به شمار می‌روند.
3. الگوریتم هائی که پایداری آن‌ها به پیاده‌سازی بستگی دارد: از این قبیل الگوریتم‌ها می‌توان به مرتب‌سازی انتخابی، مرتب‌سازی ادغامی در جا و مرتب‌سازی سریع اشاره نمود.