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

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

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

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

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

ഇതും കാണുക

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