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

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

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

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

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

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

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

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

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

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

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

അതിനാൽ  താരതമ്യങ്ങൾ ഉപയോഗിച്ച്  ക്രമീകരണങ്ങളിൽ നിന്ന് ഊർദ്ധ്വശ്രേണി തിരഞ്ഞെടുക്കണമെങ്കിൽ :  ആയിരിക്കണം.
അഥവാ,  

എന്നാൽ സ്റ്റിർലിങ്ങ് അപ്രോക്സിമേഷൻ ഉപയോഗിച്ചാൽ  എന്ന് കിട്ടുന്നു.

ഇവ ഉപയോഗിച്ച്  എന്ന് മനസ്സിലാക്കാം. അതായത്, ഏതൊരു താരതമ്യ സോർട്ടിന്റെയും മോശം സമയസങ്കീർണ്ണത ചുരുങ്ങിയത്  ആയിരിക്കും.

 ഇതും കാണുക 

വർഗ്ഗം:സോർട്ടിങ്ങ് അൽഗൊരിതങ്ങൾ