താരതമ്യ സോർട്ട്
ഒരു ലിസ്റ്റിലെ അംഗങ്ങളെ തമ്മിൽ താരതമ്യം ചെയ്യുക എന്ന പ്രക്രിയയിലൂടെ മാത്രം അവയെ ക്രമീകരിക്കുന്ന സോർട്ടിങ്ങ് അൽഗൊരിതങ്ങൾക്ക് പൊതുവായി പറയുന്ന പേരാണ് താരതമ്യ സോർട്ട് (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 നീളമുള്ള ഒരു ലിസ്റ്റ് എടുക്കുക. ഇതിലെ സംഖ്യകളെ രീതികളിൽ ക്രമീകരിക്കാം. താരതമ്യങ്ങൾ ഉപയോഗിച്ച് ഇതിലെ സംഖ്യകളെ ഊർദ്ധ്വശ്രേണിയിൽ ക്രമീകരിക്കാനാകും എന്ന് കരുതുക. ഓരോ താരതമ്യത്തിനും രണ്ട് ഉത്തരങ്ങളേ ഉണ്ടാകാവൂ (അതെ/അല്ല) എന്നതിനാൽ താരതമ്യങ്ങൾ ഉപയോഗിച്ച് ക്രമീകരണങ്ങളുടെ ഇടയിൽ മാത്രമേ വ്യത്യാസം കണ്ടെത്താനാകൂ.
അതിനാൽ താരതമ്യങ്ങൾ ഉപയോഗിച്ച് ക്രമീകരണങ്ങളിൽ നിന്ന് ഊർദ്ധ്വശ്രേണി തിരഞ്ഞെടുക്കണമെങ്കിൽ : ആയിരിക്കണം. അഥവാ,
എന്നാൽ സ്റ്റിർലിങ്ങ് അപ്രോക്സിമേഷൻ ഉപയോഗിച്ചാൽ എന്ന് കിട്ടുന്നു.
ഇവ ഉപയോഗിച്ച് എന്ന് മനസ്സിലാക്കാം. അതായത്, ഏതൊരു താരതമ്യ സോർട്ടിന്റെയും മോശം സമയസങ്കീർണ്ണത ചുരുങ്ങിയത് ആയിരിക്കും.