ഇൻസർഷൻ സോർട്ട്

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

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

ഇൻസർഷൻ സോർട്ട്

ഇൻസർഷൻ സോർട്ട് ഒരു ലിസ്റ്റ് ക്രമീകരിക്കുന്നു ഇൻസർഷൻ സോർട്ട് ഒരു ലിസ്റ്റ് ക്രമീകരിക്കുന്നു
കുടുംബം	സോർട്ടിങ്ങ് അൽഗൊരിതം
ദത്തസങ്കേതം	അറേ
കൂടിയ സമയസങ്കീർണ്ണത	$O(N^{2})$
കുറഞ്ഞ സമയസങ്കീർണ്ണത	$O(N)$
ശരാശരി സമയസങ്കീർണ്ണത	$O(N^{2})$
കൂടിയ സ്ഥലസങ്കീർണ്ണത	ആകെ $O(N)$, ലിസ്റ്റിനു പുറമെ $O(1)$
Optimal	മിക്കവാറും ക്രമീകരിക്കപ്പെട്ടിട്ടുള്ള ലിസ്റ്റുകളിൽ

ഒരു ലിസ്റ്റിലെ സംഖ്യകളെയും മറ്റും ക്രമത്തിലാക്കാൻ ഉപയോഗിക്കുന്ന ഒരു താരതമ്യ സോർട്ടിങ്ങ് അൽഗൊരിതമാണ്‌ ഇൻസർഷൻ സോർട്ട്. ഇതിന്റെ സമയസങ്കീർണ്ണത $O(N^{2})$ ആയതിനാൽ വലിയ ലിസ്റ്റുകളിൽ ഉപയോഗിക്കുമ്പോൾ ഇത് വളരെയധികം സമയമെടുക്കുന്നു. ഇൻസർഷൻ സോർട്ടിന്റെ മെമ്മറി സങ്കീർണ്ണത $O(N)$ ആണെങ്കിലും ഒരു in-place അൽഗൊരിതമാണ്‌ ഇത് എന്നതിനാൽ ലിസ്റ്റിന്‌ പുറമെ O(1) മെമ്മറി മാത്രമേ ഇതിന്‌ ആവശ്യമുള്ളൂ.

അൽഗൊരിതം

ലിസ്റ്റിലെ 1 മുതൽ i വരെയുള്ള സംഖ്യകൾ ക്രമത്തിലാണെന്നു കരുതുക. i+1 ആമത്തെ സംഖ്യയെ ലിസ്റ്റിൽ ക്രമമനുസരിച്ചുള്ള സ്ഥാനത്തേക്ക് മാറ്റുക. ഈ സ്ഥാനം j ആണെങ്കിൽ j മുതൽ i-1 വരെയുള്ള സ്ഥാനങ്ങളിൽ ഇപ്പോഴുള്ള സംഖ്യകളെ അവയുടെ വലതുവശത്തേക്ക് മാറ്റേണ്ടിവരും. i = 1 മുതൽ N-1 വരെ ഇത് തുടർന്നുകൊണ്ടു പോകുക. ഇങ്ങനെ ചെയ്താൽ ലിസ്റ്റിലെ സംഖ്യകളെല്ലാം ക്രമത്തിലാകും.

സ്യൂഡോകോഡ്

N സംഖ്യകളുള്ള array എന്ന ലിസ്റ്റ് ഇൻസർഷൻ സോർട്ട് വഴി ക്രമത്തിലാക്കാൻ:

1. done <- 1
2. done = N ആണെങ്കിൽ നിർത്തുക 
3. value <- array[done+1]
4. j <- done
5. j = 0 ആകുകയോ array[j] <= value ആകുകയോ ചെയ്യുന്നതു വരെ പടി 6,7 എന്നിവ ചെയ്യുക
6. array[j+1] <- array[j]
7. j <- j-1
8. array[j+1] <- value
9. done <- done+1
10. പടി 2 ലേക്ക് പോകുക

വിശകലനം

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

വലിയ ലിസ്റ്റുകൾ ക്രമത്തിലാക്കാൻ ഇൻസർഷൻ സോർട്ട് സാധാരണ ഉപയോഗിക്കാറില്ല. എങ്കിലും പത്തിൽ താഴെ സംഖ്യകളുള്ള ലിസ്റ്റുകൾ ക്രമത്തിലാക്കാൻ ഏറ്റവും വേഗതയിൽ സാധിക്കുന്ന അൽഗൊരിതങ്ങളിലൊന്നാണിത്.

ഇതും കാണുക

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