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

الگوریتم‌های مرتب‌سازی که از وجود ترتیب خاصی در ورودی برای بهبود زمان اجرا استفاده می‌کنند جزو این دسته هستند. این ترتیب معمولاً به صورتی است که داده‌ها تقریباً مرتبند؛ پراکندگی کمی دارند یا به اندازهٔ مشخصی نابه‌جایی (به انگلیسی: Inversion) دارند. انگیزهٔ ایجاد این الگوریتم‌ها به این دلیل است که مرتب‌سازی‌های مقایسه‌ای محدود به پیچیدگی زماتی (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

منابع

• Hagerup, Torben; Jyrki Katjainen (2004). Algorithm Theory – SWAT 2004. Berlin Heidelberg: Springer-Verlag. pp. 221–222. ISBN 3-540-22339-8.
• Estivill-Castro, Vladmir; Wood, Derick (December 1992). "A survey of adaptive sorting algorithms". ACM. New York, NY, USA: ACM. 24 (4): 441–476. CiteSeerX 10.1.1.45.8017. doi:10.1145/146370.146381. ISSN 0360-0300.
• Petersson, Ola; Alistair Moffat (1992). "A framework for adaptive sorting". Lecture Notes in Computer Science. Berlin: Springer Berlin / Heidelberg. 621: 422–433. doi:10.1007/3-540-55706-7_38. ISSN 1611-3349. Retrieved February 23, 2009.