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

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.

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

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

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

ഉദാഹരണങ്ങൾ[തിരുത്തുക]

Balance à tabac 1850.JPG

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

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

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

ഗണനപരമായ സങ്കീർണ്ണത[തിരുത്തുക]

ഏതൊരു താരതമ്യസോർട്ടും 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\left(N!\right)

എന്നാൽ സ്റ്റിർലിങ്ങ് അപ്രോക്സിമേഷൻ ഉപയോഗിച്ചാൽ \log_2\left(N!\right) = \Omega\left(N\;\log_2N\right) എന്ന് കിട്ടുന്നു.

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

ഇതും കാണുക[തിരുത്തുക]

"http://ml.wikipedia.org/w/index.php?title=താരതമ്യ_സോർട്ട്&oldid=1691456" എന്ന താളിൽനിന്നു ശേഖരിച്ചത്