مرتب‌سازی توافقی

الگوریتم‌های مرتب‌سازی که از وجود ترتیب خاصی در ورودی برای بهبود زمان اجرا استفاده می‌کنند جزو این دسته هستند. این ترتیب معمولاً به صورتی است که داده‌ها تقریباً مرتبند؛ پراکندگی کمی دارند یا به اندازهٔ مشخصی نابه‌جایی  دارند. انگیزهٔ ایجاد این الگوریتم‌ها به این دلیل است که مرتب‌سازی‌های مقایسه‌ای محدود به پیچیدگی زماتی (O (n log n هستند. مرتب‌سازی توافقی معمولاً با تغییر و بهینه‌سازی مرتب‌سازی‌های دیگر انجام می‌شود.

مثال 
  مرتب‌سازی حبابی بهینه
این الگوریتم در حالت معمول از (O(n² مقایسه انجام می‌دهد؛ اما تعداد عملیات (به انگلیسی: swap) آن درست به اندازهٔ نابه‌جایی‌ها در آرایه است. برای مثال اگر بخواهیم آرایهٔ زیر را که نابه‌جایی آن شامل ۳ و ۶ بوده و به ترتیب با جای خود در آرایهٔ مرتب شده فاصله‌های ۷ و ۴ دارند مرتب کنیم؛ طبق کد زیر (به زبان پایتون) و خروجی آن، می‌توان گفت تنها ۱۱ عملیات انجام شده‌است.
6, 1, 2, 4, 5, 7, 8, 9, 10, 3
#Bubble Sort
x = [6, 1, 2, 4, 5, 7, 8, 9, 10, 3]
operations = 0
for i in range (len(x)):
    j = 0
    for j in range (len(x) - i - 1):
        if (x[j+1] <x[j]):
            operations = operations + 1
            x[j], x[j+1], j = x[j+1], x[j], j+1
print (x)
print ("operations:", operations)
و خروجی به صورت زیر خواهد بود:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
operations: 11
 مرتب‌سازی درجی مستقیم
اگر داده‌های استفاده شده در مثال قبل را نیز در این مرتب‌سازی استفاده کنیم، نتیجه یکسان خواهد بود.
#Insertion Sort
x = [6, 1, 2, 4, 5, 7, 8, 9, 10, 3]
operations = 0
for i in range (1, len(x)):
    temp = x[i]
    j = i - 1
    while (j>= 0 and temp <x[j]):
        operations = operations + 1
        x[j], x[j+1], j = x[j+1], x[j], j - 1
    x[j+1] = temp
print (x)
print ("operations:", operations)
خروجی:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
operations: 11

مرتب‌سازی‌های غیر توافقی 
قابل توجه است که همهٔ الگوریتم‌های مرتب‌سازی را نمی‌توان با تغییرات کم به شکل توافقی درآورد. اکثر الگوریتم‌هایی که در بهترین و بدترین حالت در زمان مشخصی خروجی می‌دهند مانند مرتب‌سازی ادغامی و مرتب‌سازی هرمی، به ترتیب ورودی توجه ندارند و در عملیاتشان تأثیری ندارد. اگرچه می‌توان در قسمت ادغام در الگوریتم مرتب‌سازی ادغامی به گونه‌ای تغییر ایجاد کرد که توافقی عمل کند. تنها با اضافه کردن کد زیر در تابع ادغام در مرتب‌سازی ادغامی می‌توان آن را توافقی کرد که در آن دو آرایهٔ مرتب x و y ادغام می‌شوند:
if (x[last] <y [first]):
    x.append(y)
    return x

منابع 

 
 
 

الگوریتم‌های مرتب‌سازی