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