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

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

http://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) മെമ്മറി മാത്രമേ ആവശ്യമുള്ളൂ.

ലിസ്റ്റിലെ ഏറ്റവും ചെറിയ സംഖ്യ കണ്ടെത്തി അതിനെ ആദ്യത്തെ സംഖ്യയുമായി പരസ്പരം മാറ്റുകയും ഈ പ്രക്രിയ തുടരുകയും ചെയ്താണ്‌ സെലക്ഷൻ സോർട്ട് സംഖ്യകളെ ക്രമീകരിക്കുന്നത്.

അൽഗൊരിതം

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

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 ലേക്ക് പോകുക

വിശകലനം

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

ഇതും കാണുക

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