സെലക്ഷൻ സോർട്ട്
സെലക്ഷൻ സോർട്ട് ഒരു ലിസ്റ്റ് ക്രമീകരിക്കുന്നു | |
കുടുംബം | സോർട്ടിങ്ങ് അൽഗൊരിതം |
---|---|
ദത്തസങ്കേതം | അറേ |
കൂടിയ സമയസങ്കീർണ്ണത | |
കുറഞ്ഞ സമയസങ്കീർണ്ണത | |
ശരാശരി സമയസങ്കീർണ്ണത | |
കൂടിയ സ്ഥലസങ്കീർണ്ണത | ആകെ , ലിസ്റ്റിനു പുറമെ |
Optimal | അല്ല |
സരളമായ ഒരു താരതമ്യ സോർട്ടിങ്ങ് അൽഗൊരിതമാണ് സെലക്ഷൻ സോർട്ട്. ഒരു ലിസ്റ്റിലെ സംഖ്യകളെയും മറ്റും ക്രമത്തിലാക്കാനാണ് ഇത് ഉപയോഗിക്കുന്നത്. ഇതിന്റെ സമയസങ്കീർണ്ണത വളരെക്കൂടുതലായതിനാൽ () വലിയ ലിസ്റ്റുകളിൽ ഇത് ഉപയോഗിക്കുക പ്രായോഗികമല്ല. ഈ in-place അൽഗൊരിതം ഉപയോഗിക്കുന്നതിനായി ലിസ്റ്റിനായുള്ള മെമ്മറിക്കു പുറമെ O(1) മെമ്മറി മാത്രമേ ആവശ്യമുള്ളൂ.
ലിസ്റ്റിലെ ഏറ്റവും ചെറിയ സംഖ്യ കണ്ടെത്തി അതിനെ ആദ്യത്തെ സംഖ്യയുമായി പരസ്പരം മാറ്റുകയും ഈ പ്രക്രിയ തുടരുകയും ചെയ്താണ് സെലക്ഷൻ സോർട്ട് സംഖ്യകളെ ക്രമീകരിക്കുന്നത്. അതായത്, ഈ അൽഗരിതത്തിൽ സോർട്ട് ചെയ്യപ്പെടേണ്ട വസ്തുക്കളുടെ ലിസ്റ്റിന്റെ ഒരറ്റത്തു നിന്നും മറ്റേ അറ്റത്തേയ്ക്ക് യാത്ര/ഐറ്ററേറ്റ് ചെയ്യുന്നു. ഐറ്ററേറ്റ് ചെയ്യുമ്പോൾ, ഒരു പ്രത്യേക സ്ഥാനത്ത് (i) ഇപ്പോൾ ഉള്ള സംഖ്യയെക്കാൾ ചെറിയ സംഖ്യകൾ (ഡിസൻഡിങ്ങ് ഓർഡർ സോർട്ടിങ്ങ് ആണെങ്കിൽ, വലിയ സംഖ്യകൾ) ആ സ്ഥാനത്തിനു(i) വലതു വശത്ത് ഉണ്ടെങ്കിൽ, വലതുവശത്തുള്ളവയിൽ ഏറ്റവും ചെറിയ (/വലിയ) സംഖ്യയുമായി, ഈ സംഖ്യ(i ഇൻഡേക്സിലുള്ള സംഖ്യ) തന്റെ സ്ഥാനം വച്ച് മാറുന്നു. ഇപ്രകാരം ലിസ്റ്റ് മുഴുവൻ ഐറ്ററേറ്റ് ചെയ്തു കഴിയു മ്പോൾ, ലിസ്റ്റ് സോർട്ട് ചെയ്യപ്പെട്ടിരിയ്ക്കും.
അൽഗൊരിതം
[തിരുത്തുക]സെലക്ഷൻ സോർട്ട് അൽഗൊരിതത്തിലെ പ്രധാന ഭാഗങ്ങൾ ഇവയാണ്:
- ലിസ്റ്റിലെ ഏറ്റവും ചെറിയ സംഖ്യ കണ്ടെത്തുക
- ഇതിനെയും ആദ്യത്തെ സംഖ്യയെയും പരസ്പരം മാറ്റുക
- ലിസ്റ്റിലെ ബാക്കിയുള്ള സംഖ്യകളുടെമേൽ ഈ പ്രക്രിയ തുടരുക
സ്യൂഡോകോഡ്
[തിരുത്തുക]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 തവണ ഐറ്ററേറ്റ് ചെയ്യണം. അതിനാൽ, സങ്കീർണ്ണത, ആണു. മോശം, ശരാശരി, നല്ല സമയസങ്കീർണ്ണതകളെല്ലാം തന്നെ ആണ്. ശരാശരി, മോശം സമയസങ്കീർണ്ണതകൾ ആയുള്ള സോർട്ടിങ്ങ് അൽഗൊരിതങ്ങൾ ഉണ്ട്. മോശം സമയസങ്കീർണ്ണത ആയുള്ള സോർട്ടിങ്ങ് അൽഗൊരിതങ്ങളിൽ ബബിൾ സോർട്ട്, ഗ്നോം സോർട്ട് എന്നിവയെക്കാൾ വേഗതയുള്ളതാണ് ഇതെങ്കിലും ഇൻസർഷൻ സോർട്ട് ഇതിനെക്കാൾ വേഗതയേറിയതാണ്. വലിയ ലിസ്റ്റുകൾ ക്രമത്തിലാക്കാൻ സെലക്ഷൻ സോർട്ട് സാധാരണ ഉപയോഗിക്കാറില്ല.