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

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.
ഇൻസർഷൻ സോർട്ട്
ഇൻസർഷൻ സോർട്ട് ഒരു ലിസ്റ്റ് ക്രമീകരിക്കുന്നു

ഇൻസർഷൻ സോർട്ട് ഒരു ലിസ്റ്റ് ക്രമീകരിക്കുന്നു
കുടുംബം സോർട്ടിങ്ങ് അൽഗൊരിതം
ഡാറ്റാ സ്ട്രക്‌ചർ അറേ
മോശം സമയസങ്കീർണ്ണത 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) ആയുള്ള സോർട്ടിങ്ങ് അൽഗൊരിതങ്ങളിൽ ബബിൾ സോർട്ട്, സെലക്ഷൻ സോർട്ട്, ഗ്നോം സോർട്ട് മുതലായവയെക്കാൾ വേഗതയേറിയതാണിത്.

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

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

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