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

• مرتب‌سازی حبابی بهینه

این الگوریتم در حالت معمول از (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