താരതമ്യ സോർട്ട്

ഒരു ലിസ്റ്റിലെ അംഗങ്ങളെ തമ്മിൽ താരതമ്യം ചെയ്യുക എന്ന പ്രക്രിയയിലൂടെ മാത്രം അവയെ ക്രമീകരിക്കുന്ന സോർട്ടിങ്ങ് അൽഗൊരിതങ്ങൾക്ക് പൊതുവായി പറയുന്ന പേരാണ്‌ താരതമ്യ സോർട്ട് (Comparison sort). താരതമ്യ സോർട്ട് ചെയ്യണമെന്നുണ്ടെങ്കിൽ ലിസ്റ്റിലെ അംഗങ്ങളുടെമേൽ താരതമ്യത്തിനുള്ള ഓപ്പറേഷൻ (സാധാരണയായി ≤) നിർവ്വചിക്കപ്പെട്ടിരിക്കണം. ഈ താരതമ്യ ഓപ്പറേഷൻ പാലിച്ചിരിക്കേണ്ട നിബന്ധനകൾ ഇവയാണ്‌:

1. a≤b, b≤c ആണെങ്കിൽ a≤c ആയിരിക്കണം
2. a≤b, b≤a ഇവയിൽ ഒന്നെങ്കിലും ശരിയായിരിക്കണം

a≤b, b≤a എന്നിവ രണ്ടും ശരിയാകാം. ഈ സന്ദർഭത്തിൽ ക്രമീകരണത്തിനു ശേഷം a b യ്ക്ക് മുമ്പോ പിൻപോ വരാം. അല്ലെങ്കിൽ a≤b ആണെങ്കിൽ ലിസ്റ്റിൽ ക്രമീകരണത്തിനുശേഷം a b യ്ക്ക് മുന്നിലായിരിക്കും.

ഉദാഹരണങ്ങൾ

വ്യത്യസ്ത ഭാരങ്ങളുള്ള ഒരുകൂട്ടം വസ്തുക്കളെ അവയുടെ ഭാരത്തിന്റെ ക്രമത്തിൽ ആക്കേണ്ടതുണ്ടെന്നു വിചാരിക്കുക. രണ്ട് വസ്തുക്കളുടെ ഭാരങ്ങൾ തമ്മിൽ താരതമ്യം ചെയ്ത് ഭാരമേറിയതേത് എന്ന് മനസ്സിലാക്കാൻ സഹായിക്കുന്ന ഒരു ത്രാസ് മാത്രമേ നമ്മുടെ കയ്യിലുള്ളൂ എങ്കിൽ ആ വസ്തുക്കളെ ക്രമത്തിലാക്കാൻ ഉപയോഗിക്കുന്ന ഏത് അൽഗൊരിതവും ഒരു താരതമ്യ സോർട്ട് ആയിരിക്കും.

താഴെക്കൊടുത്തിരിക്കുന്ന സോർട്ടുകൾ താരതമ്യ സോർട്ടുകളാണ്‌:

• ബബിൾ സോർട്ട്
• സെലക്ഷൻ സോർട്ട്
• ഇൻസർഷൻ സോർട്ട്
• മെർജ് സോർട്ട്
• ക്വിക് സോർട്ട്
• ഹീപ് സോർട്ട്
• ഇൻട്രോ സോർട്ട്

എന്നാൽ ഈ സോർട്ടുകൾ താരതമ്യ സോർട്ടുകളല്ല :

• കൗണ്ടിങ്ങ് സോർട്ട്
• റാഡിക്സ് സോർട്ട്
• ബക്കറ്റ് സോർട്ട്

ഗണനപരമായ സങ്കീർണ്ണത

ഏതൊരു താരതമ്യസോർട്ടും n അംഗങ്ങളുള്ള ഒരു ലിസ്റ്റിനെ ക്രമീകരിക്കാനെടുക്കുന്ന മോശം സമയസങ്കീർണ്ണത ചുരുങ്ങിയത് Ω(n log n) ആയിരിക്കും.

തെളിവ്

എല്ലാ സംഖ്യകളും വ്യത്യസ്തമായിട്ടുള്ള N നീളമുള്ള ഒരു ലിസ്റ്റ് എടുക്കുക. ഇതിലെ സംഖ്യകളെ $N!$ രീതികളിൽ ക്രമീകരിക്കാം. $f\left(N\right)$ താരതമ്യങ്ങൾ ഉപയോഗിച്ച് ഇതിലെ സംഖ്യകളെ ഊർദ്ധ്വശ്രേണിയിൽ ക്രമീകരിക്കാനാകും എന്ന് കരുതുക. ഓരോ താരതമ്യത്തിനും രണ്ട് ഉത്തരങ്ങളേ ഉണ്ടാകാവൂ (അതെ/അല്ല) എന്നതിനാൽ $f\left(N\right)$ താരതമ്യങ്ങൾ ഉപയോഗിച്ച് $2^{f\left(N\right)}$ ക്രമീകരണങ്ങളുടെ ഇടയിൽ മാത്രമേ വ്യത്യാസം കണ്ടെത്താനാകൂ.

അതിനാൽ $f\left(N\right)$ താരതമ്യങ്ങൾ ഉപയോഗിച്ച് $N!$ ക്രമീകരണങ്ങളിൽ നിന്ന് ഊർദ്ധ്വശ്രേണി തിരഞ്ഞെടുക്കണമെങ്കിൽ : $2^{f\left(N\right)}\ge N!$ ആയിരിക്കണം. അഥവാ, $f\left(N\right)\ge {\log }_2(N!)$

എന്നാൽ സ്റ്റിർലിങ്ങ് അപ്രോക്സിമേഷൻ ഉപയോഗിച്ചാൽ ${\log }_2(N!)=\mathrm{\Omega }\left(N{\log }_{2}N\right)$ എന്ന് കിട്ടുന്നു.

ഇവ ഉപയോഗിച്ച് $f\left(N\right)=\mathrm{\Omega }\left(N{\log }_{2}N\right)$ എന്ന് മനസ്സിലാക്കാം. അതായത്, ഏതൊരു താരതമ്യ സോർട്ടിന്റെയും മോശം സമയസങ്കീർണ്ണത ചുരുങ്ങിയത് $O(N\log N)$ ആയിരിക്കും.