താരതമ്യ സോര്ട്ട്
വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.
ഒരു ലിസ്റ്റിലെ അംഗങ്ങളെ തമ്മില് താരതമ്യം ചെയ്യുക എന്ന പ്രക്രിയയിലൂടെ മാത്രം അവയെ ക്രമീകരിക്കുന്ന സോര്ട്ടിങ്ങ് അല്ഗൊരിതങ്ങള്ക്ക് പൊതുവായി പറയുന്ന പേരാണ് താരതമ്യ സോര്ട്ട് (Comparison sort). താരതമ്യ സോര്ട്ട് ചെയ്യണമെന്നുണ്ടെങ്കില് ലിസ്റ്റിലെ അംഗങ്ങളുടെമേല് താരതമ്യത്തിനുള്ള ഓപ്പറേഷന് (സാധാരണയായി ≤) നിര്വ്വചിക്കപ്പെട്ടിരിക്കണം. ഈ താരതമ്യ ഓപ്പറേഷന് പാലിച്ചിരിക്കേണ്ട നിബന്ധനകള് ഇവയാണ്:
- a≤b, b≤c ആണെങ്കില് a≤c ആയിരിക്കണം
- a≤b, b≤a ഇവയില് ഒന്നെങ്കിലും ശരിയായിരിക്കണം
a≤b, b≤a എന്നിവ രണ്ടും ശരിയാകാം. ഈ സന്ദര്ഭത്തില് ക്രമീകരണത്തിനു ശേഷം a b യ്ക്ക് മുമ്പോ പിന്പോ വരാം. അല്ലെങ്കില് a≤b ആണെങ്കില് ലിസ്റ്റില് ക്രമീകരണത്തിനുശേഷം a b യ്ക്ക് മുന്നിലായിരിക്കും.
[തിരുത്തുക] ഉദാഹരണങ്ങള്
വ്യത്യസ്ത ഭാരങ്ങളുള്ള ഒരുകൂട്ടം വസ്തുക്കളെ അവയുടെ ഭാരത്തിന്റെ ക്രമത്തില് ആക്കേണ്ടതുണ്ടെന്നു വിചാരിക്കുക. രണ്ട് വസ്തുക്കളുടെ ഭാരങ്ങള് തമ്മില് താരതമ്യം ചെയ്ത് ഭാരമേറിയതേത് എന്ന് മനസ്സിലാക്കാന് സഹായിക്കുന്ന ഒരു ത്രാസ് മാത്രമേ നമ്മുടെ കയ്യിലുള്ളൂ എങ്കില് ആ വസ്തുക്കളെ ക്രമത്തിലാക്കാന് ഉപയോഗിക്കുന്ന ഏത് അല്ഗൊരിതവും ഒരു താരതമ്യ സോര്ട്ട് ആയിരിക്കും.
താഴെക്കൊടുത്തിരിക്കുന്ന സോര്ട്ടുകള് താരതമ്യ സോര്ട്ടുകളാണ്:
- ബബിള് സോര്ട്ട്
- സെലക്ഷന് സോര്ട്ട്
- ഇന്സര്ഷന് സോര്ട്ട്
- മെര്ജ് സോര്ട്ട്
- ക്വിക് സോര്ട്ട്
- ഹീപ് സോര്ട്ട്
- ഇന്ട്രോ സോര്ട്ട്
എന്നാല് ഈ സോര്ട്ടുകള് താരതമ്യ സോര്ട്ടുകളല്ല :
[തിരുത്തുക] ഗണനപരമായ സങ്കീര്ണ്ണത
ഏതൊരു താരതമ്യസോര്ട്ടിന്റെയും മോശം സമയസങ്കീര്ണ്ണത ചുരുങ്ങിയത് 
ആയിരിക്കും.
[തിരുത്തുക] തെളിവ്
എല്ലാ സംഖ്യകളും വ്യത്യസ്തമായിട്ടുള്ള N നീളമുള്ള ഒരു ലിസ്റ്റ് എടുക്കുക. ഇതിലെ സംഖ്യകളെ N! രീതികളില് ക്രമീകരിക്കാം. 
താരതമ്യങ്ങള് ഉപയോഗിച്ച് ഇതിലെ സംഖ്യകളെ ഊര്ദ്ധ്വശ്രേണിയില് ക്രമീകരിക്കാനാകും എന്ന് കരുതുക. ഓരോ താരതമ്യത്തിനും രണ്ട് ഉത്തരങ്ങളേ ഉണ്ടാകാവൂ (അതെ/അല്ല) എന്നതിനാല് താരതമ്യങ്ങള് ഉപയോഗിച്ച് 
ക്രമീകരണങ്ങളുടെ ഇടയില് മാത്രമേ വ്യത്യാസം കണ്ടെത്താനാകൂ.
അതിനാല് താരതമ്യങ്ങള് ഉപയോഗിച്ച് N! ക്രമീകരണങ്ങളില് നിന്ന് ഊര്ദ്ധ്വശ്രേണി തിരഞ്ഞെടുക്കണമെങ്കില് : 
ആയിരിക്കണം. അഥവാ, 
എന്നാല് സ്റ്റിര്ലിങ്ങ് അപ്രോക്സിമേഷന് ഉപയോഗിച്ചാല് 
എന്ന് കിട്ടുന്നു.
ഇവ ഉപയോഗിച്ച് 
എന്ന് മനസ്സിലാക്കാം. അതായത്, ഏതൊരു താരതമ്യ സോര്ട്ടിന്റെയും മോശം സമയസങ്കീര്ണ്ണത ചുരുങ്ങിയത് ആയിരിക്കും.
