പൈത്തണിലെ വിവിധ സോർട്ടിംഗ് രീതികളും അൽഗോരിതങ്ങളും ഉപയോഗിച്ച് ലിസ്റ്റുകൾ, അറേകൾ, നിഘണ്ടുക്കൾ മുതലായവ അടുക്കുന്നതിന് പൈത്തൺ സോർട്ട് ഫംഗ്ഷൻ എങ്ങനെ ഉപയോഗിക്കാമെന്ന് മനസിലാക്കുക:
സോർട്ടിംഗ് എന്നത് അടുക്കുന്നതിന് ഉപയോഗിക്കുന്ന ഒരു സാങ്കേതികതയാണ്. ആരോഹണ ക്രമത്തിലോ അവരോഹണ ക്രമത്തിലോ ഉള്ള ഡാറ്റ.
മിക്കപ്പോഴും വലിയ പ്രോജക്റ്റുകളുടെ ഡാറ്റ ശരിയായ ക്രമത്തിൽ ക്രമീകരിച്ചിട്ടില്ല, ഇത് ആവശ്യമായ ഡാറ്റ കാര്യക്ഷമമായി ആക്സസ് ചെയ്യുമ്പോഴും ലഭ്യമാക്കുമ്പോഴും പ്രശ്നങ്ങൾ സൃഷ്ടിക്കുന്നു.
ഈ പ്രശ്നം പരിഹരിക്കാൻ സോർട്ടിംഗ് ടെക്നിക്കുകൾ ഉപയോഗിക്കുന്നു. പൈത്തൺ വിവിധ സോർട്ടിംഗ് ടെക്നിക്കുകൾ നൽകുന്നു ഉദാഹരണത്തിന്, ബബിൾ സോർട്ട്, ഇൻസെർഷൻ സോർട്ട്, മെർജ് സോർട്ട്, ക്വിക്ക്സോർട്ട് മുതലായവ.
ഈ ട്യൂട്ടോറിയലിൽ, വിവിധ അൽഗോരിതങ്ങൾ ഉപയോഗിച്ച് പൈത്തണിൽ സോർട്ടിംഗ് എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് ഞങ്ങൾ മനസ്സിലാക്കും.
പൈത്തൺ സോർട്ട്
പൈത്തൺ സോർട്ടിന്റെ വാക്യഘടന
സോർട്ടിംഗ് നടത്താൻ, പൈത്തൺ ബിൽറ്റ്-ഇൻ ഫംഗ്ഷൻ നൽകുന്നു, അതായത് "സോർട്ട്()" ഫംഗ്ഷൻ. ഒരു ലിസ്റ്റിന്റെ ഡാറ്റാ ഘടകങ്ങളെ ആരോഹണ ക്രമത്തിലോ അവരോഹണ ക്രമത്തിലോ അടുക്കാൻ ഇത് ഉപയോഗിക്കുന്നു.
ഒരു ഉദാഹരണത്തിലൂടെ നമുക്ക് ഈ ആശയം മനസ്സിലാക്കാം.
ഉദാഹരണം 1:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```
ഔട്ട്പുട്ട്:
ഈ ഉദാഹരണത്തിൽ, നൽകിയിരിക്കുന്ന ക്രമമില്ലാത്ത ലിസ്റ്റ് “സോർട്ട്( )” ഫംഗ്ഷൻ ഉപയോഗിച്ച് ആരോഹണ ക്രമത്തിൽ അടുക്കുന്നു .
ഉദാഹരണം 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```
ഔട്ട്പുട്ട്
മുകളിലുള്ള ഉദാഹരണത്തിൽ, നൽകിയിരിക്കുന്ന ക്രമപ്പെടുത്താത്ത ലിസ്റ്റ് " അടുക്കുക( റിവേഴ്സ് = ട്രൂ ) " എന്ന ഫംഗ്ഷൻ ഉപയോഗിച്ച് വിപരീത ക്രമത്തിൽ അടുക്കിയിരിക്കുന്നു.
സമയംസ്ഥലം ബബിൾ അടുക്കുക O(n) O(n2) O(n2) O(1) അതെ അതെ ഇൻസേർഷൻ സോർട്ട് O(n) O(n2) O(n2) O(1) അതെ അതെ വേഗത്തിലുള്ള അടുക്കുക O(n log(n)) O(n log(n)) O(n2) O(N) ഇല്ല അതെ ലയിപ്പിക്കുക അടുക്കുക O(n log(n)) O(n log(n)) O(n log(n)) O(N) അതെ ഇല്ല ഹീപ്പ് സോർട്ട് O(n log (n)) O(n log(n)) O(n log(n)) O(1) No അതെ
മുകളിലുള്ള താരതമ്യ പട്ടികയിൽ “O” എന്നത് മുകളിൽ വിശദീകരിച്ചിരിക്കുന്ന ബിഗ് ഓ നൊട്ടേഷനാണ്, അതേസമയം “n”, “N” എന്നിവ ഇൻപുട്ടിന്റെ വലുപ്പത്തെ അർത്ഥമാക്കുന്നു .
പതിവായി ചോദിക്കുന്ന ചോദ്യങ്ങൾ
Q #1) പൈത്തണിൽ എന്താണ് അടുക്കുക ()?
ഉത്തരം: പൈത്തണിൽ ലിസ്റ്റുകളോ അറേകളോ ഒരു പ്രത്യേക ക്രമത്തിൽ അടുക്കാൻ ഉപയോഗിക്കുന്ന ഒരു ഫംഗ്ഷനാണ് sort(). വലിയ പ്രോജക്റ്റുകളിൽ പ്രവർത്തിക്കുമ്പോൾ ഈ ഫംഗ്ഷൻ അടുക്കുന്ന പ്രക്രിയ എളുപ്പമാക്കുന്നു. ഡെവലപ്പർമാർക്ക് ഇത് വളരെ സഹായകരമാണ്.
Q #2) നിങ്ങൾ എങ്ങനെയാണ് പൈത്തണിൽ അടുക്കുന്നത്?
ഉത്തരം: മൂലകത്തെ അടുക്കാൻ ഉപയോഗിക്കുന്ന വിവിധ സോർട്ടിംഗ് ടെക്നിക്കുകൾ പൈത്തൺ നൽകുന്നു. ഉദാഹരണത്തിന്, ദ്രുത അടുക്കൽ, ലയിപ്പിക്കൽ, ബബിൾ അടുക്കൽ, തിരുകൽ അടുക്കൽ, മുതലായവ. എല്ലാ സോർട്ടിംഗ് ടെക്നിക്കുകളും കാര്യക്ഷമവും മനസ്സിലാക്കാൻ എളുപ്പവുമാണ്.
Q #3) പൈത്തൺ എങ്ങനെ പ്രവർത്തിക്കുന്നു അടുക്കുക () ജോലി?
ഉത്തരം: തരം()ഫംഗ്ഷൻ നൽകിയിരിക്കുന്ന അറേയെ ഉപയോക്താവിൽ നിന്നുള്ള ഇൻപുട്ടായി എടുക്കുകയും സോർട്ടിംഗ് അൽഗോരിതം ഉപയോഗിച്ച് ഒരു നിർദ്ദിഷ്ട ക്രമത്തിൽ അടുക്കുകയും ചെയ്യുന്നു. അൽഗോരിതം തിരഞ്ഞെടുക്കുന്നത് ഉപയോക്താവിന്റെ തിരഞ്ഞെടുപ്പിനെ ആശ്രയിച്ചിരിക്കുന്നു. ഉപയോക്താവിന്റെ ആവശ്യങ്ങൾക്കനുസരിച്ച് ഉപയോക്താക്കൾക്ക് ദ്രുത അടുക്കൽ, ലയിപ്പിക്കൽ, ബബിൾ അടുക്കൽ, തിരുകൽ അടുക്കൽ, മുതലായവ ഉപയോഗിക്കാം.
ഉപസംഹാരം
മുകളിലുള്ള ട്യൂട്ടോറിയലിൽ, ഞങ്ങൾ പൈത്തണിലെ സോർട്ട് ടെക്നിക്കിനെക്കുറിച്ച് ചർച്ചചെയ്തു. പൊതുവായ സോർട്ടിംഗ് വിദ്യകൾ ദോഷങ്ങൾ. മുകളിലുള്ള എല്ലാ സാങ്കേതിക വിദ്യകളും ഞങ്ങൾ താരതമ്യം ചെയ്തു.
സോർട്ടിംഗ് അൽഗോരിതങ്ങളുടെ സങ്കീർണ്ണതസമയ സങ്കീർണ്ണത എന്നത് ഒരു പ്രത്യേക അൽഗോരിതം പ്രവർത്തിപ്പിക്കുന്നതിന് കമ്പ്യൂട്ടർ എടുക്കുന്ന സമയമാണ്. ഇതിന് മൂന്ന് തരത്തിലുള്ള സമയ സങ്കീർണ്ണത കേസുകളുണ്ട്.
- മോശം കേസ്: പ്രോഗ്രാം പ്രവർത്തിപ്പിക്കാൻ കമ്പ്യൂട്ടർ എടുക്കുന്ന പരമാവധി സമയം.
- ശരാശരി കേസ്: പ്രോഗ്രാം റൺ ചെയ്യാൻ കമ്പ്യൂട്ടർ എടുക്കുന്ന ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ സമയം.
- മികച്ച കേസ്: പ്രോഗ്രാം പ്രവർത്തിപ്പിക്കുന്നതിന് കമ്പ്യൂട്ടർ എടുക്കുന്ന ഏറ്റവും കുറഞ്ഞ സമയം. സമയ സങ്കീർണ്ണതയുടെ ഏറ്റവും മികച്ച കേസാണിത്.
സങ്കീർണ്ണത നൊട്ടേഷനുകൾ
ബിഗ് ഓ നൊട്ടേഷൻ, ഒ: ബിഗ് ഓ നൊട്ടേഷൻ ആണ് അപ്പർ ബൗണ്ടിനെ അറിയിക്കാനുള്ള ഔദ്യോഗിക മാർഗം അൽഗോരിതങ്ങളുടെ പ്രവർത്തന സമയം. ഏറ്റവും മോശം സമയ സങ്കീർണ്ണത അളക്കാൻ ഇത് ഉപയോഗിക്കുന്നു അല്ലെങ്കിൽ അൽഗോരിതം പൂർത്തിയാക്കാൻ എടുക്കുന്ന ഏറ്റവും വലിയ സമയം ഞങ്ങൾ പറയുന്നു.
വലിയ ഒമേഗ നോട്ടേഷൻ, : വലിയ ഒമേഗ നൊട്ടേഷൻ അൽഗോരിതങ്ങളുടെ പ്രവർത്തന സമയത്തിന്റെ ഏറ്റവും താഴ്ന്ന പരിധി അറിയിക്കുന്നതിനുള്ള ഔദ്യോഗിക മാർഗം. മികച്ച സമയ സങ്കീർണ്ണത അളക്കാൻ ഇത് ഉപയോഗിക്കുന്നു അല്ലെങ്കിൽ അൽഗോരിതം എടുത്ത സമയത്തിന്റെ മികച്ച അളവ് ഞങ്ങൾ പറയുന്നു.
തീറ്റ നോട്ടേഷൻ, : തീറ്റ നൊട്ടേഷൻ അറിയിക്കാനുള്ള ഔദ്യോഗിക മാർഗമാണ് രണ്ട് അതിരുകളും അതായത് അൽഗോരിതം പൂർത്തിയാക്കാൻ എടുക്കുന്ന സമയത്തിന്റെ താഴെയും മുകളിലും.
പൈത്തണിലെ സോർട്ടിംഗ് രീതികൾ
ബബിൾ സോർട്ട്
ഡാറ്റ അടുക്കുന്നതിനുള്ള ഏറ്റവും ലളിതമായ മാർഗമാണ് ബബിൾ സോർട്ട് ബ്രൂട്ട് ഫോഴ്സ് ടെക്നിക് ഉപയോഗിക്കുന്നു. ഇത് ഓരോ ഡാറ്റ ഘടകത്തിലേക്കും ആവർത്തിക്കുകയും മറ്റ് ഘടകങ്ങളുമായി താരതമ്യം ചെയ്യുകയും ചെയ്യുംക്രമീകരിച്ച ഡാറ്റ ഉപയോക്താവിന് നൽകുന്നതിന്.
ഈ സാങ്കേതികത മനസ്സിലാക്കാൻ നമുക്ക് ഒരു ഉദാഹരണം എടുക്കാം:
- ഞങ്ങൾക്ക് ഘടകങ്ങൾ ഉള്ള ഒരു അറേ നൽകിയിരിക്കുന്നു. 10, 40, 7, 3, 15 ”. ഇപ്പോൾ, പൈത്തണിലെ ബബിൾ സോർട്ട് ടെക്നിക് ഉപയോഗിച്ച് നമുക്ക് ഈ അറേ ആരോഹണ ക്രമത്തിൽ ക്രമീകരിക്കേണ്ടതുണ്ട്.
- ആദ്യത്തെ ഘട്ടം തന്നിരിക്കുന്ന ക്രമത്തിൽ അറേ ക്രമീകരിക്കുക എന്നതാണ്.
- “ആവർത്തനം 1” ൽ, ഞങ്ങൾ ഒരു അറേയുടെ ആദ്യ ഘടകത്തെ മറ്റ് ഘടകങ്ങളുമായി ഒന്നൊന്നായി താരതമ്യം ചെയ്യുന്നു.
- ചുവപ്പ് അമ്പടയാളങ്ങൾ ആദ്യ മൂലകങ്ങളെ ഒരു അറേയിലെ മറ്റ് ഘടകങ്ങളുമായി താരതമ്യപ്പെടുത്തുന്നത് വിവരിക്കുന്നു.
- “10” എന്നത് “40” നേക്കാൾ ചെറുതാണെന്ന് നിങ്ങൾ ശ്രദ്ധിച്ചാൽ, അത് അതേപടി തുടരും. സ്ഥലം എന്നാൽ അടുത്ത ഘടകം "7" "10" നേക്കാൾ ചെറുതാണ്. അതിനാൽ അത് മാറ്റിസ്ഥാപിക്കുകയും ഒന്നാം സ്ഥാനത്തെത്തുകയും ചെയ്യുന്നു.
- മൂലകങ്ങൾ അടുക്കുന്നതിന് മുകളിലുള്ള പ്രക്രിയ വീണ്ടും വീണ്ടും നടത്തും. 3>
-
- “ആവർത്തനം 2” ൽ രണ്ടാമത്തെ ഘടകം ഒരു അറേയുടെ മറ്റ് ഘടകങ്ങളുമായി താരതമ്യം ചെയ്യുന്നു.
- താരതമ്യപ്പെടുത്തിയ ഘടകം ചെറുതാണെങ്കിൽ, അത് മാറ്റിസ്ഥാപിക്കുക, അല്ലാത്തപക്ഷം അത് അതേ സ്ഥലത്ത് തന്നെ തുടരും മൂന്നാമത്തെ ഘടകം ഒരു അറേയുടെ മറ്റ് ഘടകങ്ങളുമായി താരതമ്യം ചെയ്യപ്പെടുന്നു. " ആവർത്തനം 4 " ഒരു അറേയുടെ മറ്റ് ഘടകങ്ങളുമായി താരതമ്യം ചെയ്യുമ്പോൾ അവസാനത്തെ രണ്ടാമത്തെ ഘടകം ലഭിക്കുന്നു.
- ഇൻഈ ഘട്ടം അറേ ആരോഹണ ക്രമത്തിൽ അടുക്കിയിരിക്കുന്നു.
ബബിൾ സോർട്ടിനായുള്ള പ്രോഗ്രാം
``` def Bubble_Sort(unsorted_list): for i in range(0,len(unsorted_list)-1): for j in range(len(unsorted_list)-1): if(unsorted_list[j]>unsorted_list[j+1]): temp_storage = unsorted_list[j] unsorted_list[j] = unsorted_list[j+1] unsorted_list[j+1] = temp_storage return unsorted_list unsorted_list = [5, 3, 8, 6, 7, 2] print("Unsorted List: ", unsorted_list) print("Sorted List using Bubble Sort Technique: ", Bubble_Sort(unsorted_list)) ```
ഔട്ട്പുട്ട്
ബബിൾ സോർട്ടിന്റെ സമയ സങ്കീർണ്ണത
- മോശം കേസ്: ബബിൾ അടുക്കുന്നതിനുള്ള ഏറ്റവും മോശം സമയ സങ്കീർണ്ണത O( n 2) ആണ്.
- ശരാശരി കേസ്: ബബിൾ സോർട്ടിന്റെ ശരാശരി സമയ സങ്കീർണ്ണത O(4) ആണ്>n 2).
- മികച്ച കേസ്: ബബിൾ അടുക്കുന്നതിനുള്ള ഏറ്റവും മികച്ച സമയ സങ്കീർണ്ണത O(n) ആണ്.
നേട്ടങ്ങൾ
- ഇത് കൂടുതലും ഉപയോഗിക്കുന്നതും നടപ്പിലാക്കാൻ എളുപ്പവുമാണ്.
- ഹ്രസ്വകാല സംഭരണം ഉപയോഗിക്കാതെ തന്നെ ഞങ്ങൾക്ക് ഡാറ്റ ഘടകങ്ങൾ സ്വാപ്പ് ചെയ്യാം.
- ഇതിന് കുറച്ച് മാത്രമേ ആവശ്യമുള്ളൂ. സ്പേസ്.
ദോഷങ്ങൾ
- ഒരു വലിയ സംഖ്യ വലിയ ഡാറ്റാ ഘടകങ്ങളുമായി ഇടപെടുമ്പോൾ അത് നന്നായി പ്രവർത്തിച്ചില്ല.
- ഇത് ഓരോ "n" ഡാറ്റ എലമെന്റുകൾക്കും അടുക്കാൻ n 2 ഘട്ടങ്ങൾ ആവശ്യമാണ്.
- യഥാർത്ഥ ലോക ആപ്ലിക്കേഷനുകൾക്ക് ഇത് ശരിക്കും നല്ലതല്ല.
ഉൾപ്പെടുത്തൽ അടുക്കുക
ഇൻസേർഷൻ സോർട്ട് എന്നത് പ്ലേയിംഗ് കാർഡുകൾ അടുക്കുന്നതിന് സമാനമായി പ്രവർത്തിക്കുന്ന ലളിതവും ലളിതവുമായ സോർട്ടിംഗ് ടെക്നിക്കാണ്. ഇൻസെർഷൻ അടുക്കുക, ഓരോ മൂലകവും ഒന്നിനുപുറകെ ഒന്നായി താരതമ്യം ചെയ്തുകൊണ്ട് ഘടകങ്ങളെ അടുക്കുന്നു. മൂലകം മറ്റൊന്നിനേക്കാൾ വലുതോ ചെറുതോ ആണെങ്കിൽ മൂലകങ്ങൾ തിരഞ്ഞെടുത്ത് മറ്റേ മൂലകവുമായി മാറ്റുന്നു.
നമുക്ക് ഒരു ഉദാഹരണം എടുക്കാം
- നമുക്ക് നൽകിയിരിക്കുന്നത് “ 100, 50, 30, 40, 10 ” മൂലകങ്ങളുള്ള ഒരു അറേ.
- ആദ്യം, ഞങ്ങൾ അറേ ക്രമീകരിച്ച് താരതമ്യം ചെയ്യാൻ തുടങ്ങുന്നുഅത്.
- ആദ്യ ഘട്ടത്തിൽ " 100 " രണ്ടാമത്തെ ഘടകമായ " 50 " മായി താരതമ്യം ചെയ്യുന്നു. “ 50 ” എന്നത് “ 100 ” എന്നതുമായി മാറ്റുന്നു.
- രണ്ടാം ഘട്ടത്തിൽ, രണ്ടാമത്തെ ഘടകമായ “ 100 ” വീണ്ടും മൂന്നാം ഘടകമായ “ 30 ” മായി താരതമ്യം ചെയ്യുകയും സ്വാപ്പ് ചെയ്യുകയും ചെയ്യുന്നു.
- ഇപ്പോൾ, "30" ഒന്നാം സ്ഥാനത്തേക്ക് വരുന്നത് നിങ്ങൾ ശ്രദ്ധിച്ചാൽ, അത് വീണ്ടും "50" നേക്കാൾ ചെറുതാണ്.
- ഒരു അറേയുടെ അവസാന ഘടകം വരെ താരതമ്യം സംഭവിക്കും, അവസാനം നമുക്ക് ലഭിക്കും അടുക്കിയ ഡാറ്റ.
ഇൻസേർഷൻ സോർട്ടിനുള്ള പ്രോഗ്രാം
``` def InsertionSort(array): for i in range(1, len(array)): key_value = array[i] j = i-1 while j >= 0 and key_value array[j] : array[j + 1] = array[j] j -= 1 array[j + 1] = key_value array = [11, 10, 12, 4, 5] print("The unsorted array: ", array) InsertionSort(array) print ("The sorted array using the Insertion Sort: ") for i in range(len(array)): print (array[i]) ```
ഔട്ട്പുട്ട്
0ഇൻസേർഷൻ സോർട്ടിന്റെ സമയ സങ്കീർണ്ണത
- മോശം കേസ്: ഇൻസേർഷൻ സോർട്ടിന്റെ ഏറ്റവും മോശം സമയ സങ്കീർണ്ണത O( n 2).
- ശരാശരി കേസ്: ഇൻസേർഷൻ സോർട്ടിന്റെ ശരാശരി സമയ സങ്കീർണ്ണത O( n 2) ആണ്.
- മികച്ച കേസ്: ഇൻസേർഷൻ സോർട്ടിനുള്ള ഏറ്റവും മികച്ച സമയ സങ്കീർണ്ണത O(n) ആണ്.
പ്രയോജനങ്ങൾ
- ഇത് ലളിതമാണ്. നടപ്പിലാക്കാൻ എളുപ്പവും.
- ചെറിയ എണ്ണം ഡാറ്റാ ഘടകങ്ങളുമായി ഇടപെടുമ്പോൾ ഇത് നന്നായി പ്രവർത്തിക്കുന്നു.
- ഇത് നടപ്പിലാക്കുന്നതിന് കൂടുതൽ ഇടം ആവശ്യമില്ല.
അനുകൂലങ്ങൾ
- ഒരു വലിയ അളവിലുള്ള ഡാറ്റാ ഘടകങ്ങളെ അടുക്കുന്നത് സഹായകരമല്ല.
- മറ്റ് സോർട്ടിംഗ് ടെക്നിക്കുകളുമായി താരതമ്യം ചെയ്യുമ്പോൾ അത് നന്നായി പ്രവർത്തിക്കുന്നില്ല.
ലയിപ്പിക്കുക അടുക്കുക
ഈ സോർട്ടിംഗ് രീതി ഒരു പ്രത്യേക ക്രമത്തിൽ മൂലകങ്ങളെ അടുക്കുന്നതിന് വിഭജിച്ച് കീഴടക്കുന്ന രീതി ഉപയോഗിക്കുന്നു. മെർജ് സോർട്ടിന്റെ സഹായത്തോടെ അടുക്കുമ്പോൾ, ദിമൂലകങ്ങളെ പകുതികളായി തിരിച്ചിരിക്കുന്നു, തുടർന്ന് അവ അടുക്കുന്നു. എല്ലാ ഭാഗങ്ങളും അടുക്കിയ ശേഷം, ഘടകങ്ങൾ വീണ്ടും ചേർന്ന് ഒരു പൂർണ്ണമായ ക്രമം ഉണ്ടാക്കുന്നു.
ഈ സാങ്കേതികത മനസ്സിലാക്കാൻ നമുക്ക് ഒരു ഉദാഹരണം എടുക്കാം
- നമുക്ക് നൽകിയിരിക്കുന്നത് ഒരു അറേ "7, 3, 40, 10, 20, 15, 6, 5". ശ്രേണിയിൽ 7 ഘടകങ്ങൾ അടങ്ങിയിരിക്കുന്നു. നമ്മൾ അതിനെ പകുതിയായി വിഭജിച്ചാൽ ( 0 + 7 / 2 = 3 ).
- രണ്ടാം ഘട്ടത്തിൽ, ഘടകങ്ങൾ രണ്ട് ഭാഗങ്ങളായി വിഭജിക്കപ്പെട്ടിരിക്കുന്നത് നിങ്ങൾ കാണും. ഓരോന്നിനും അതിൽ 4 ഘടകങ്ങൾ ഉണ്ട്.
- കൂടാതെ, മൂലകങ്ങളെ വീണ്ടും വിഭജിക്കുകയും ഓരോന്നിനും 2 ഘടകങ്ങൾ ഉണ്ടായിരിക്കുകയും ചെയ്യുന്നു.
- ഒരു അറേയിൽ ഒരു ഘടകം മാത്രം ഉള്ളത് വരെ ഈ പ്രക്രിയ തുടരും. സ്റ്റെപ്പ് നമ്പർ റഫർ ചെയ്യുക. ചിത്രത്തിൽ 4.
- ഇപ്പോൾ, ഞങ്ങൾ ഘടകങ്ങൾ അടുക്കി വിഭജിച്ചതുപോലെ അവയുമായി ചേരാൻ തുടങ്ങും.
- ഘട്ടം നമ്പർ. 5, 7 എന്നത് 3-നേക്കാൾ വലുതാണെന്ന് നിങ്ങൾ ശ്രദ്ധിച്ചാൽ, ഞങ്ങൾ അത് കൈമാറുകയും അടുത്ത ഘട്ടത്തിലും തിരിച്ചും ചേരുകയും ചെയ്യും.
- അവസാനം, ഞങ്ങളുടെ ശ്രേണി ആരോഹണ ക്രമത്തിൽ അടുക്കുന്നത് നിങ്ങൾ ശ്രദ്ധിക്കും.
സംയോജിപ്പിക്കുന്നതിനുള്ള പ്രോഗ്രാം
``` def MergeSort(arr): if len(arr) > 1: middle = len(arr)//2 L = arr[:middle] R = arr[middle:] MergeSort(L) MergeSort(R) i = j = k = 0 while i len(L) and j len(R): if L[i] R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i len(L): arr[k] = L[i] i += 1 k += 1 while j len(R): arr[k] = R[j] j += 1 k += 1 def PrintSortedList(arr): for i in range(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Given array is", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sorted array is: ", end="\n") PrintSortedList(arr) ```
ഔട്ട്പുട്ട്
ലയന രീതിയുടെ സമയ സങ്കീർണ്ണത
- മോശം കേസ്: ലയന ക്രമത്തിന്റെ ഏറ്റവും മോശം സമയ സങ്കീർണ്ണത O( n ലോഗ്( n )).
- ശരാശരി കേസ്: ലയന ക്രമത്തിന്റെ ശരാശരി സമയ സങ്കീർണ്ണത O( n ലോഗ്(4) ആണ്>n )).
- മികച്ച കേസ്: ലയിപ്പിക്കുന്നതിനുള്ള മികച്ച സമയ സങ്കീർണ്ണത O( n ആണ്.log( n )).
പ്രയോജനങ്ങൾ
- ഈ സോർട്ടിംഗ് ടെക്നിക്കിന് ഫയൽ വലുപ്പം പ്രശ്നമല്ല.15
- സാധാരണ ക്രമത്തിൽ ആക്സസ് ചെയ്യപ്പെടുന്ന ഡാറ്റയ്ക്ക് ഈ സാങ്കേതികത നല്ലതാണ്. ഉദാഹരണത്തിന്, ലിങ്ക് ചെയ്ത ലിസ്റ്റുകൾ, ടേപ്പ് ഡ്രൈവ് മുതലായവ.
-
അനുകൂലങ്ങൾ
- മറ്റുള്ളവയുമായി താരതമ്യപ്പെടുത്തുമ്പോൾ ഇതിന് കൂടുതൽ ഇടം ആവശ്യമാണ് സോർട്ടിംഗ് ടെക്നിക്കുകൾ.
- ഇത് മറ്റുള്ളവയെ അപേക്ഷിച്ച് താരതമ്യേന കാര്യക്ഷമത കുറവാണ്.
ദ്രുത അടുക്കൽ
ക്വിക്ക് സോർട്ട് വീണ്ടും ഒരു ലിസ്റ്റിലെ ഘടകങ്ങളെ തരംതിരിക്കാൻ ഡിവിഡ് ആൻഡ് കൺക്വയർ രീതി ഉപയോഗിക്കുന്നു അല്ലെങ്കിൽ ഒരു അറേ. ഇത് പിവറ്റ് ഘടകങ്ങളെ ടാർഗെറ്റുചെയ്യുകയും തിരഞ്ഞെടുത്ത പിവറ്റ് ഘടകത്തിനനുസരിച്ച് ഘടകങ്ങളെ അടുക്കുകയും ചെയ്യുന്നു.
ഉദാഹരണത്തിന്
- ഞങ്ങൾക്ക് “ 1 ഘടകങ്ങൾ ഉള്ള ഒരു അറേ നൽകിയിരിക്കുന്നു. ,8,3,9,4,5,7 ”.
- “7” ഒരു പൈലറ്റ് എലമെന്റ് ആണെന്ന് നമുക്ക് അനുമാനിക്കാം.
- ഇനി നമ്മൾ അറേയെ വിഭജിക്കും. ഇടതുവശത്ത് പിവറ്റ് മൂലകമായ " 7 "നേക്കാൾ ചെറിയ മൂലകങ്ങളും വലതുവശത്ത് " 7 " എന്ന പിവറ്റ് മൂലകത്തേക്കാൾ വലിയ മൂലകങ്ങളും അടങ്ങിയിരിക്കുന്നു.
- നമുക്ക് ഇപ്പോൾ രണ്ട് അറേകളുണ്ട് " 1,3,4,5 ” കൂടാതെ “ 8, 9 ”.
- വീണ്ടും, നമ്മൾ മുകളിൽ ചെയ്തതുപോലെ തന്നെ രണ്ട് അറേകളെയും വിഭജിക്കേണ്ടതുണ്ട്. ഒരേയൊരു വ്യത്യാസം പിവറ്റ് ഘടകങ്ങൾ മാറുന്നു എന്നതാണ്.
- അറേയിൽ ഒരൊറ്റ ഘടകം ലഭിക്കുന്നതുവരെ നമുക്ക് അറേകൾ വിഭജിക്കേണ്ടതുണ്ട്.
- അവസാനം, a-യിലെ എല്ലാ പിവറ്റ് ഘടകങ്ങളും ശേഖരിക്കുക. ഇടത്തുനിന്ന് വലത്തോട്ട് ക്രമീകരിച്ച് ക്രമീകരിച്ചത് നിങ്ങൾക്ക് ലഭിക്കുംനിര
ക്വിക്ക് സോർട്ടിന്റെ സമയ സങ്കീർണ്ണത
- മോശം കേസ്: ക്വിക്ക് സോർട്ടിന്റെ ഏറ്റവും മോശം സമയ സങ്കീർണ്ണത O(4)>n 2).
- ശരാശരി കേസ്: ദ്രുത ക്രമത്തിന്റെ ശരാശരി സമയ സങ്കീർണ്ണത O( n log( n ) ആണ് ).
- മികച്ച കേസ്: വേഗത്തിലുള്ള അടുക്കുന്നതിനുള്ള ഏറ്റവും മികച്ച സമയ സങ്കീർണ്ണത O( n log( n )) 16>
- പൈത്തണിലെ മികച്ച സോർട്ടിംഗ് അൽഗോരിതം എന്നാണ് ഇത് അറിയപ്പെടുന്നത്.
- വലിയ അളവിലുള്ള ഡാറ്റ കൈകാര്യം ചെയ്യുമ്പോൾ ഇത് ഉപയോഗപ്രദമാണ്.
- ഇതിന് അധിക സ്ഥലം ആവശ്യമില്ല.
- അതിന്റെ ഏറ്റവും മോശമായ സങ്കീർണ്ണത ബബിൾ സോർട്ടിന്റെ സങ്കീർണ്ണതകൾക്ക് സമാനമാണ് തിരുകൽ അടുക്കുക.
- ഞങ്ങൾക്ക് ഇതിനകം അടുക്കിയ ലിസ്റ്റ് ഉള്ളപ്പോൾ ഈ സോർട്ടിംഗ് രീതി ഉപയോഗപ്രദമല്ല.
- ഞങ്ങൾക്ക് “ 40, 100, 30, 50, 10 ” ഘടകങ്ങൾ ഉള്ള ഒരു അറേ നൽകിയിരിക്കുന്നു.
- “ ഘട്ടം 1 ” -ൽ ഞങ്ങൾ ഒരു മരം ഉണ്ടാക്കി അറേയിലെ മൂലകങ്ങളുടെ സാന്നിധ്യം.
- “ ഘട്ടം 2 ” ൽ ഞങ്ങൾ പരമാവധി കൂമ്പാരം ഉണ്ടാക്കുന്നു, അതായത് ക്രമീകരിക്കാൻ അവരോഹണ ക്രമത്തിലുള്ള ഘടകങ്ങൾ. ഏറ്റവും വലിയ ഘടകം ചെയ്യുംമുകളിലും (റൂട്ട്) ഏറ്റവും ചെറിയ മൂലകം താഴെയും (ഇല നോഡുകൾ) വസിക്കുന്നു. നൽകിയിരിക്കുന്ന ശ്രേണി “ 100, 50, 30, 40, 10 ” ആയി മാറുന്നു.
- “ ഘട്ടം 3 ” ൽ, ഞങ്ങൾ ഒരു അറേയുടെ ഏറ്റവും കുറഞ്ഞ മൂലകങ്ങൾ കണ്ടെത്തുന്നതിന് ഏറ്റവും കുറഞ്ഞ കൂമ്പാരം ഉണ്ടാക്കുന്നു. ഇത് ചെയ്യുന്നതിലൂടെ, ഞങ്ങൾക്ക് കൂടിയതും കുറഞ്ഞതുമായ ഘടകങ്ങൾ ലഭിക്കും.
- “ ഘട്ടം 4 ” ൽ സമാന ഘട്ടങ്ങൾ നടപ്പിലാക്കുക നമുക്ക് അടുക്കിയ അറേ ലഭിക്കും.
പ്രയോജനങ്ങൾ
അനുകൂലങ്ങൾ
ഹീപ്പ് സോർട്ട്
ബൈനറി സെർച്ച് ട്രീയുടെ വിപുലമായ പതിപ്പാണ് ഹീപ്പ് സോർട്ട്. . കൂമ്പാരത്തിൽ, ഇല നോഡുകളുമായുള്ള റൂട്ടുമായി താരതമ്യപ്പെടുത്തുമ്പോൾ, ഒരു ശ്രേണിയുടെ ഏറ്റവും വലിയ ഘടകം എല്ലായ്പ്പോഴും മരത്തിന്റെ വേരിൽ സ്ഥാപിക്കുന്നു.
ഉദാഹരണത്തിന്:
ഹീപ്പ് സോർട്ടിനുള്ള പ്രോഗ്രാം
``` def HeapSortify( arr, n, i ): larger_element = i left = 2 * i + 1 right = 2 * i + 2 if left n and arr[ larger_element ] arr[ left ]: larger_element = left if right n and arr[ larger_element ] arr[ right ]: larger_element = right if larger_element != i: arr[ i ], arr[ larger_element ] = arr[ larger_element ], arr[ i ] HeapSortify( arr, n, larger_element ) def HeapSort( arr ): n = len( arr ) for i in range( n//2 - 1, -1, -1 ): HeapSortify( arr, n, i ) for i in range( n-1, 0, -1 ): arr[ i ], arr[ 0 ] = arr[ 0 ], arr[ i ] HeapSortify( arr, i, 0 ) arr = [ 11, 10, 12, 4, 5, 6 ] print( " The unsorted array is: ", arr ) HeapSort( arr ) n = len( arr ) print( " The sorted array sorted by the Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ```
ഔട്ട്പുട്ട് 3
ഹീപ്പ് സോർട്ടിന്റെ സമയ സങ്കീർണ്ണത
- മോശം കേസ്: ഹീപ്പ് സോർട്ടിന്റെ ഏറ്റവും മോശം സമയ സങ്കീർണ്ണത O( n log( n )).
- ശരാശരി കേസ്: Heap sort-ന്റെ ശരാശരി സമയ സങ്കീർണ്ണത O( n ആണ് ലോഗ്( n )).
- മികച്ച കേസ്: ഹീപ്പ് സോർട്ടിനുള്ള ഏറ്റവും മികച്ച സമയ സങ്കീർണ്ണത isO( n log(4)>n )).
പ്രയോജനങ്ങൾ
- അതിന്റെ ഉൽപ്പാദനക്ഷമത കാരണം ഇത് കൂടുതലായി ഉപയോഗിക്കുന്നു.
- ഇതിന് കഴിയും. ഇൻ-പ്ലേസ് അൽഗോരിതം ആയി നടപ്പിലാക്കും.
- ഇതിന് വലിയ സംഭരണം ആവശ്യമില്ല.
അനുകൂലങ്ങൾ
- ഇതിനായി സ്ഥലം ആവശ്യമാണ് മൂലകങ്ങളെ അടുക്കുന്നു.
- അത് മൂലകങ്ങളെ തരംതിരിക്കാൻ ട്രീ ഉണ്ടാക്കുന്നു.
സോർട്ടിംഗ് ടെക്നിക്കുകൾ തമ്മിലുള്ള താരതമ്യം
സോർട്ടിംഗ് രീതി മികച്ച കേസ് സമയ സങ്കീർണ്ണത ശരാശരി കേസ് സമയ സങ്കീർണ്ണത മോസ്റ്റ് കേസ് സമയ സങ്കീർണ്ണത സ്പേസ് സങ്കീർണ്ണത സ്ഥിരത ഇൻ -