ഹീപ് സോർട്ട്

ഇംഗ്ലീഷ് വിലാസം

https://ml.wikipedia.org/wiki/Heap_sort

ഹീപ് സോർട്ട്

ഹീപ് സോർട്ട് ഉപയോഗിച്ച് ഒരു അറേ സോർട്ട് ചെയ്യുന്നു. ആദ്യം ഹീപ് നിയമം അനുസരിക്കുന്ന രീതിയിൽ അംഗങ്ങളെ ക്രമീകരിക്കുന്നു. സോർട്ടിങ്ങിനു തൊട്ടു മുമ്പുള്ള ഹീപ് ട്രീ കാണിച്ചിരിക്കുന്നു ഹീപ് സോർട്ട് ഉപയോഗിച്ച് ഒരു അറേ സോർട്ട് ചെയ്യുന്നു. ആദ്യം ഹീപ് നിയമം അനുസരിക്കുന്ന രീതിയിൽ അംഗങ്ങളെ ക്രമീകരിക്കുന്നു. സോർട്ടിങ്ങിനു തൊട്ടു മുമ്പുള്ള ഹീപ് ട്രീ കാണിച്ചിരിക്കുന്നു.
കുടുംബം	സോർട്ടിങ്ങ് അൽഗൊരിതം
ദത്തസങ്കേതം	അറേ
കൂടിയ സമയസങ്കീർണ്ണത	$O\left(N\log \;N\right)$
കുറഞ്ഞ സമയസങ്കീർണ്ണത	$O\left(N\log \;N\right)$
ശരാശരി സമയസങ്കീർണ്ണത	$\Theta \left(N\log \;N\right)$
കൂടിയ സ്ഥലസങ്കീർണ്ണത	ആകെ $O\left(N\right)$, അറേയ്ക്കു പുറമെ $O\left(1\right)$
Optimal	അല്ല

ഹീപ് ഉപയോഗിച്ച് സംഖ്യകളയും മറ്റും ക്രമത്തിലാക്കാൻ ഉപയോഗിക്കുന്ന സോർട്ടിങ്ങ് അൽഗൊരിതമാണ്‌ ഹീപ് സോർട്ട്. സെലക്ഷൻ സോർട്ട് കുടുംബത്തില്പ്പെട്ട ഒരു താരതമ്യ സോർട്ട് അൽഗൊരിതമാണ്‌ ഇത്. സാധാരണ രീതിയിൽ ക്വിക്ക് സോർട്ടിനെക്കാൾ മെല്ലെയാണ്‌ ഇതിന്റെ പ്രവർത്തനമെങ്കിലും മോശം സമയസങ്കീർണ്ണത $O\left(N\log \;N\right)$ ആണെന്ന മെച്ചമുണ്ട്. ഒരു in-place അൽഗൊരിതമായതിനാൽ അറേയ്ക്കു പുറമെ $O\left(1\right)$ മെമ്മറി മാത്രമേ ഇതിന്‌ ആവശ്യമുള്ളൂ. ഹീപ് സോർട്ട് ഒരു സ്റ്റേബിൾ സോർട്ട് അല്ല.

അൽഗൊരിതം

അറേയിലെ സംഖ്യകളെ ഒരു ഹീപ് ആക്കി മാറ്റുകയാണ്‌ അൽഗൊരിതത്തിലെ ആദ്യ പടി. ഇത് $O\left(N\right)$ സമയമുപയോഗിച്ച് ചെയ്യാൻ സാധിക്കും. ഇതിനുശേഷം അറേ ഹീപ് നിയമം അനുസരിക്കുമെന്നതിനാൽ ഏറ്റവും വലിയ സംഖ്യ അറേയുടെ ആദ്യത്തിലായിരിക്കും. ഇതിനെ തൽസ്ഥാനത്തുനിന്ന് നീക്കി അറേയുടെ അവസാന സ്ഥാനത്ത് കൊണ്ടിടുന്നു. ഇത് $O\left(\log \;N\right)$ സമയമെടുക്കുന്നു. ഇങ്ങനെ തുടരുന്നതു വഴി സംഖ്യകളെയെല്ലാം ക്രമത്തിലാക്കാം. ഈ പടി N തവണ ചെയ്യണമെന്നതിനാൽ അൽഗൊരിതത്തിന്റെ ആകെ സമയസങ്കീർണ്ണത $O\left(N\log \;N\right)$ ആണ്‌.

ഏറ്റവും വലിയ സംഖ്യയെ തുടർച്ചയായി കണ്ടുപിടിക്കുന്നതുവഴിയാണ്‌ ഈ അൽഗൊരിതം സോർട്ടിങ്ങ് നടത്തുന്നതെന്നതിനാൽ ഇത് സെലക്ഷൻ സോർട്ട് കുടുംബത്തിൽ പെടുന്നതാണ്‌.

താരതമ്യം

സാധാരണരീതിയിൽ $O\left(N\log \;N\right)$ സമയമെടുക്കുന്ന മറ്റൊരു താരതമ്യസോർട്ടിങ്ങ് അൽഗൊരിതമായ ക്വിക്ക് സോർട്ട് ഹീപ് സോർട്ടിനെക്കാൾ വേഗതയേറിയതാണ്‌. എങ്കിലും ക്വിക്ക് സോർട്ടിന്റെ മോശം സമയസങ്കീർണ്ണത $O\left(N^{2}\right)$ ആയതിനാൽ ചില വലിയ അറേകൾ ക്രമത്തിലാക്കാൻ വളരെയധികം സമയമെടുക്കുന്ന ക്വിക്ക് സോർട്ട് പ്രാവർത്തികമല്ല. ക്വിക്ക് സോർട്ട് അൽഗൊരിതം അറിയുന്ന വ്യക്തിക്ക് അതിനെക്കൊണ്ട് വളരെയധികം സമയമെടുപ്പിക്കാനാകുമെന്നതിനാൽ സുരക്ഷാപ്രശ്നങ്ങളുമുണ്ടാകാൻ സാദ്യതയുണ്ട്. അതിനാൽ ചില റിയൽ-ടൈം അൽഗൊരിതങ്ങളും സുരക്ഷ ആവശ്യമുള്ള അൽഗൊരിതങ്ങളും ക്വിക്ക് സോർട്ടിനെക്കാൾ ഹീപ് സോർട്ടിന്‌ മുൻഗണന നൽകുന്നു.

മെർജ് സോർട്ടും സാധാരണരീതിയിൽ $O\left(N\log \;N\right)$ സമയമെടുക്കുന്നു. എങ്കിലും ലിസ്റ്റിനു പുറമെ $\emptyset \left(N\right)$ മെമ്മറി മെർജ് സോർട്ടിന്‌ ആവശ്യമുണ്ട്. എങ്കിലും ചില കാര്യങ്ങളിൽ മെർജ് സോർട്ട് ഹീപ് സോർട്ടിനെക്കാൾ മികച്ചുനിൽക്കുന്നു:

• മെർജ് സോർട്ട് ഒരു സ്റ്റേബിൾ സോർട്ട് ആണ്‌
• സാധാരണ കം‌പ്യൂട്ടറുകളിലെ അറേകളിൽ മെർജ് സോർട്ട് ഹീപ് സോർട്ടിനെക്കാൾ വേഗത്തിൽ സോർട്ടിങ്ങ് നടത്തുന്നു
• ഒന്നിലധികം പ്രോസസ്സറുകൾ സമാന്തരമായി ഉപയോഗിക്കുന്നതു വഴി മെർജ് സോർട്ടിന്റെ വേഗത വർദ്ധിപ്പിക്കാം. ഹീപ് സോർട്ട് ഇങ്ങനെ വേഗത്തിലാക്കാൻ സാധിക്കില്ല
• ലിങ്ക്ഡ് ലിസ്റ്റുകളിൽ മെർജ് സോർട്ട് ചെയ്യാൻ സാധിക്കും. എന്നാൽ ഹീപ് സോർട്ട് ചെയ്യാൻ സാധിക്കില്ല

ഇതും കൂടി കാണുക

• ഹീപ് (ഡാറ്റാ സ്ട്രക്‌ച്ചർ)

വിവരസാങ്കേതികവിദ്യ കവാടം