സെലക്ഷൻ സോർട്ട്

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

സെലക്ഷൻ സോർട്ട് ഒരു ലിസ്റ്റ് ക്രമീകരിക്കുന്നു
കുടുംബം സോർട്ടിങ്ങ് അൽഗൊരിതം
ഡാറ്റാ സ്ട്രക്‌ചർ അറേ
മോശം സമയസങ്കീർണ്ണത O(N^2)
നല്ല സമയസങ്കീർണ്ണത O(N^2)
ശരാശരി സമയസങ്കീർണ്ണത O(N^2)
മോശം മെമ്മറി സങ്കീർണ്ണത ആകെ O(N), ലിസ്റ്റിനു പുറമെ O(1)
Optimal അല്ല

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

ലിസ്റ്റിലെ ഏറ്റവും ചെറിയ സംഖ്യ കണ്ടെത്തി അതിനെ ആദ്യത്തെ സംഖ്യയുമായി പരസ്പരം മാറ്റുകയും ഈ പ്രക്രിയ തുടരുകയും ചെയ്താണ്‌ സെലക്ഷൻ സോർട്ട് സംഖ്യകളെ ക്രമീകരിക്കുന്നത്. അതായത്, ഈ അൽഗരിതത്തിൽ സോർട്ട് ചെയ്യപ്പെടേണ്ട വസ്തുക്കളുടെ ലിസ്റ്റിന്റെ ഒരറ്റത്തു നിന്നും മറ്റേ അറ്റത്തേയ്ക്ക് യാത്ര/ഐറ്ററേറ്റ് ചെയ്യുന്നു. ഐറ്ററേറ്റ് ചെയ്യുംബോൾ, ഒരു പ്രത്യേക സ്ഥാനത്ത് (i) ഇപ്പോൾ ഉള്ള സംഖ്യയെക്കാൾ ചെറിയ സംഖ്യകൾ (ഡിസൻഡിങ്ങ് ഓർഡർ സോർട്ടിങ്ങ് ആണെങ്കിൽ, വലിയ സംഖ്യകൾ) ആ സ്ഥാനത്തിനു(i) വലതു വശത്ത് ഉണ്ടെങ്കിൽ, വലതുവശത്തുള്ളവയിൽ ഏറ്റവും ചെറിയ(/വലിയ) സംഖ്യയുമായി, ഈ സംഖ്യ(i ഇൻഡേക്സിലുള്ള സംഖ്യ) തന്റെ സ്ഥാനം വച്ച് മാറുന്നു. ഇപ്രകാരം ലിസ്റ്റ് മുഴുവൻ ഐറ്ററേറ്റ് ചെയ്തു കഴിയുംബോൾ, ലിസ്റ്റ് സോർട്ട് ചെയ്യപ്പെട്ടിരിയ്ക്കും.

അൽഗൊരിതം[തിരുത്തുക]

സെലക്ഷൻ സോർട്ട് അൽഗൊരിതത്തിലെ പ്രധാന ഭാഗങ്ങൾ ഇവയാണ്‌:

  1. ലിസ്റ്റിലെ ഏറ്റവും ചെറിയ സംഖ്യ കണ്ടെത്തുക
  2. ഇതിനെയും ആദ്യത്തെ സംഖ്യയെയും പരസ്പരം മാറ്റുക
  3. ലിസ്റ്റിലെ ബാക്കിയുള്ള സംഖ്യകളുടെമേൽ ഈ പ്രക്രിയ തുടരുക

സ്യൂഡോകോഡ്[തിരുത്തുക]

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

1. start <- 1
2. start = N ആണെങ്കിൽ നിർത്തുക
3. minpos <-start
4. i <- start+1 മുതൽ N വരെ പടി 5 ചെയ്യുക
5. array[i] > array[minpos] ആണെങ്കിൽ minpos <- i
6. array[start], array[minpos] എന്നിവയെ പരസ്പരം മാറ്റുക
7. start <- start + 1
8. പടി 2 ലേക്ക് പോകുക

വിശകലനം[തിരുത്തുക]

ഏത് കേസിലും, ഈ അൽഗരിതം പ്രകാരം സോർട്ട് ചെയ്യാൻ ലിസ്റ്റിൽ കൂടെ മുഴുവനും യാത്ര ചെയ്യേണ്ടതുണ്ട്, അതിനു പുറമേ, ഓരോ സ്ഥാനത്തും യോജിച്ച അക്കം തന്നെയാണു നിൽക്കുന്നതെന്ന് സംഖ്യകൾ, താരതമ്യപ്പെടുത്തി ഉറപ്പ് വരുത്തേണ്ടതും ഉണ്ട്. അതായത് (n-1) + (n-2) + n-3 + …… 1 + 0 തവണ താരതമ്യപ്പെടുത്തേണ്ടതുണ്ട്. (n-2) + n-3 + …… 1 + 0 = (n-1)(n)/2 തവണ ഐറ്ററേറ്റ് ചെയ്യണം. അതിനാൽ, സങ്കീർണ്ണത, O(N^2) ആണു. മോശം, ശരാശരി, നല്ല സമയസങ്കീർണ്ണതകളെല്ലാം തന്നെ O(N^2) ആണ്‌. ശരാശരി, മോശം സമയസങ്കീർണ്ണതകൾ O(N\;\log \;N) ആയുള്ള സോർട്ടിങ്ങ് അൽഗൊരിതങ്ങൾ ഉണ്ട്. മോശം സമയസങ്കീർണ്ണത O(N^2) ആയുള്ള സോർട്ടിങ്ങ് അൽഗൊരിതങ്ങളിൽ ബബിൾ സോർട്ട്, ഗ്നോം സോർട്ട് എന്നിവയെക്കാൾ വേഗതയുള്ളതാണ്‌ ഇതെങ്കിലും ഇൻസർഷൻ സോർട്ട് ഇതിനെക്കാൾ വേഗതയേറിയതാണ്‌. വലിയ ലിസ്റ്റുകൾ ക്രമത്തിലാക്കാൻ സെലക്ഷൻ സോർട്ട് സാധാരണ ഉപയോഗിക്കാറില്ല.

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

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