පයිතන් හි විවිධ වර්ග කිරීමේ ක්රම සහ ඇල්ගොරිතම භාවිතා කරමින් ලැයිස්තු, අරා, ශබ්දකෝෂ ආදිය වර්ග කිරීම සඳහා පයිතන් අනුපිළිවෙල ශ්රිතය භාවිතා කරන්නේ කෙසේදැයි ඉගෙන ගන්න:
වර්ග කිරීම යනු වර්ග කිරීම සඳහා භාවිතා කරන තාක්ෂණයකි. දත්ත අනුක්රමික අනුපිළිවෙලකට ආරෝහණ හෝ අවරෝහණ අනුපිළිවෙලින්.
බොහෝ විට විශාල ව්යාපෘති වල දත්ත නිවැරදි අනුපිළිවෙලට සකසා නොමැති අතර මෙය කාර්යක්ෂමව අවශ්ය දත්ත වෙත ප්රවේශ වීම සහ ලබා ගැනීමේදී ගැටළු ඇති කරයි.
මෙම ගැටළුව විසඳීම සඳහා වර්ග කිරීමේ ක්රම භාවිතා කරයි. Python විවිධ වර්ග කිරීමේ ශිල්පීය ක්රම සපයයි උදාහරණයක් ලෙස, Bubble sort, Insertion sort, Merge sort, Quicksort, යනාදිය.
මෙම නිබන්ධනයේදී, අපි විවිධ ඇල්ගොරිතම භාවිතා කරමින් Python හි ක්රියා කරන ආකාරය තේරුම් ගනිමු.
පයිතන් වර්ග කිරීම
පයිතන් වර්ගීකරණයේ වාක්ය
වර්ග කිරීම සිදු කිරීම සඳහා, Python විසින් ගොඩනඟන ලද ශ්රිතය එනම් “ sort() ” ශ්රිතය සපයයි. එය ලැයිස්තුවක දත්ත මූලද්රව්ය ආරෝහණ අනුපිළිවෙලට හෝ අවරෝහණ අනුපිළිවෙලට වර්ග කිරීමට භාවිතා කරයි.
අපි මෙම සංකල්පය උදාහරණයකින් තේරුම් ගනිමු.
උදාහරණ 1:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```
ප්රතිදානය:
මෙම උදාහරණයේ දී, ලබා දී ඇති අනුපිළිවෙලට නොදැමූ ලැයිස්තුව “ sort( ) ” ශ්රිතය භාවිතයෙන් ආරෝහණ අනුපිළිවෙලට වර්ග කර ඇත. .
උදාහරණ 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```
ප්රතිදානය
ඉහත උදාහරණයේ, ලබා දී ඇති ඇණවුම් නොකළ ලැයිස්තුව " sort( reverse = True ) " ශ්රිතය භාවිතයෙන් ප්රතිලෝම අනුපිළිවෙලට වර්ග කර ඇත.
කාලයස්ථානය බුබුලු වර්ග කිරීම 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) නැහැ ඔව් ඒකාබද්ධ කරන්න sort 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” යනු ඉහත පැහැදිලි කර ඇති Big Oh අංකනය වන අතර “ n ” සහ “ N ” යනු ආදානයේ ප්රමාණයයි. .
නිතර අසන ප්රශ්න
Q #1) Python හි sort () යනු කුමක්ද?
පිළිතුර: Python හි sort() යනු ලැයිස්තු හෝ අරා නිශ්චිත අනුපිළිවෙලකට වර්ග කිරීමට භාවිතා කරන ශ්රිතයකි. මෙම කාර්යය විශාල ව්යාපෘතිවල වැඩ කරන අතරතුර වර්ග කිරීමේ ක්රියාවලිය පහසු කරයි. එය සංවර්ධකයින්ට ඉතා ප්රයෝජනවත් වේ.
Q #2) ඔබ Python හි වර්ග කරන්නේ කෙසේද?
පිළිතුර: Python විසින් මූලද්රව්ය වර්ග කිරීමට භාවිතා කරන විවිධ වර්ග කිරීමේ ක්රම සපයයි. උදාහරණයක් ලෙස, Quick sort, Merge sort, Bubble sort, Insertion sort, etc. සියලුම වර්ග කිරීමේ ක්රම කාර්යක්ෂම සහ තේරුම් ගැනීමට පහසු වේ.
Q #3) Python කරන්නේ කෙසේද? වර්ග () වැඩ?
පිළිතුර: වර්ගය()ශ්රිතය ලබා දී ඇති අරාව පරිශීලකයාගෙන් ආදානයක් ලෙස ගෙන එය වර්ග කිරීමේ ඇල්ගොරිතම භාවිතයෙන් නිශ්චිත අනුපිළිවෙලකට වර්ග කරයි. ඇල්ගොරිතම තෝරාගැනීම පරිශීලක තේරීම මත රඳා පවතී. පරිශීලකයාගේ අවශ්යතා මත පරිශීලකයින්ට ඉක්මන් වර්ග කිරීම, ඒකාබද්ධ කිරීම, බුබුලු වර්ග කිරීම, ඇතුළත් කිරීමේ අනුපිළිවෙල යනාදිය භාවිතා කළ හැකිය.
නිගමනය
ඉහත නිබන්ධනයේදී, අපි පයිතන් හි ඇති වර්ග කිරීමේ ක්රමය පිළිබඳව සාකච්ඡා කළෙමු. සාමාන්ය වර්ග කිරීමේ ශිල්පීය ක්රම.
- බුබුලු වර්ග කිරීම
- ඇතුළත් කිරීමේ අනුපිළිවෙල
- ඉක්මන් අනුපිළිවෙල
අපි ඒවායේ කාල සංකීර්ණතා සහ වාසි & අවාසි. අපි ඉහත සියලු ශිල්පීය ක්රම සසඳා බැලුවෙමු.
වර්ග කිරීමේ ඇල්ගොරිතම වල සංකීර්ණත්වයකාල සංකීර්ණත්වය යනු පරිගණකය යම් ඇල්ගොරිතමයක් ක්රියාත්මක කිරීමට ගතවන කාලයයි. එහි කාල සංකීර්ණ අවස්ථා වර්ග තුනක් ඇත.
- නරක අවස්ථාව: වැඩසටහන ක්රියාත්මක කිරීමට පරිගණකයට ගතවන උපරිම කාලය.
- සාමාන්ය අවස්ථාව: වැඩසටහන ක්රියාත්මක කිරීමට පරිගණකයට ගතවන අවම සහ උපරිම කාලය.
- හොඳම අවස්ථාව: වැඩසටහන ක්රියාත්මක කිරීමට පරිගණකයට ගතවන අවම කාලය. එය කාල සංකීර්ණතාවයේ හොඳම අවස්ථාවයි.
සංකීර්ණතා සටහන්
Big Oh Notation, O: Big oh notation යනු ඉහළ සීමාව ප්රකාශ කිරීමේ නිල ක්රමයයි. ඇල්ගොරිතම වල ධාවන කාලය. එය නරකම කාල සංකීර්ණතාව මැනීමට භාවිතා කරයි, නැතහොත් ඇල්ගොරිතම මගින් සම්පූර්ණ කිරීමට ගතවන විශාලතම කාලය අපි කියමු.
Big omega Notation, : Big omega notation is ඇල්ගොරිතමවල ධාවන කාලයෙහි අවම සීමාව ප්රකාශ කිරීමේ නිල ක්රමය. එය හොඳම අවස්ථාවෙහි කාල සංකීර්ණතාව මැනීමට හෝ ඇල්ගොරිතමයෙන් ගතවන විශිෂ්ට කාලය අපි කියමු.
Theta Notation, : Theta notation යනු ප්රකාශ කිරීමේ නිල ක්රමයයි. මායිම් දෙකම එනම් ඇල්ගොරිතම මඟින් සම්පූර්ණ කිරීමට ගතවන කාලයට වඩා පහළ සහ ඉහළ.
Python හි වර්ග කිරීමේ ක්රම
Bubble Sort
Bubble sort යනු දත්ත වර්ග කිරීමට ඇති සරලම ක්රමයයි. බෲට් බල තාක්ෂණය භාවිතා කරන. එය එක් එක් දත්ත මූලද්රව්ය වෙත පුනරාවර්තනය කර අනෙකුත් මූලද්රව්ය සමඟ සංසන්දනය කරනු ඇතඅනුපිළිවෙළට සකසන ලද දත්ත සමඟ පරිශීලකයාට ලබා දීමට.
මෙම තාක්ෂණය තේරුම් ගැනීමට අපි උදාහරණයක් ගනිමු:
- අපිට මූලද්රව්ය සහිත අරාවක් සපයා ඇත. 10, 40, 7, 3, 15 ”. දැන්, අපි පයිතන් හි ඇති Bubble sort තාක්ෂණය භාවිතයෙන් මෙම අරාව ආරෝහණ අනුපිළිවෙලට සකස් කළ යුතුය.
- පළමු පියවර වන්නේ දී ඇති අනුපිළිවෙලට අරාව සකස් කිරීමයි.
- “ පුනරාවර්තනය 1 ” තුළ, අපි අරාවක පළමු මූලද්රව්යය අනෙක් මූලද්රව්ය සමඟ එකින් එක සංසන්දනය කරමින් සිටිමු.
- රතු ඊතල මඟින් පළමු මූලද්රව්ය අරාවක අනෙකුත් මූලද්රව්ය සමඟ සංසන්දනය කිරීම විස්තර කරයි.
- “10” “40” ට වඩා කුඩා බව ඔබ දුටුවහොත්, එය එලෙසම පවතී. ස්ථානය නමුත් ඊළඟ මූලද්රව්යය "7" "10" ට වඩා කුඩා වේ. එබැවින් එය ප්රතිස්ථාපනය වී පළමු ස්ථානයට පැමිණේ.
- මූලද්රව්ය වර්ග කිරීම සඳහා ඉහත ක්රියාවලිය නැවත නැවතත් සිදු කෙරේ. 3>
-
- “ පුනරාවර්තනය 2 ” හි දෙවන මූලද්රව්යය අරාවක අනෙකුත් මූලද්රව්ය සමඟ සංසන්දනය වෙමින් පවතී.
- සංසන්දනාත්මක මූලද්රව්යය කුඩා නම්, එය එසේ වනු ඇත. ප්රතිස්ථාපනය කරන්න, එසේ නොවුවහොත් එය එම ස්ථානයේම පවතිනු ඇත.
-
- “ පුනරාවර්තනය 3 “ හි තුන්වන මූලද්රව්යය අරාවක අනෙකුත් මූලද්රව්ය සමඟ සංසන්දනය වෙමින් පවතී. “ පුනරාවර්තනය 4 “ දෙවන අවසාන මූලද්රව්යය අරාවක අනෙකුත් මූලද්රව්ය සමඟ සංසන්දනය වෙමින් පවතී.
- මෙම පියවර අරාව ආරෝහණ අනුපිළිවෙලට අනුපිළිවෙලට සකසනු ලැබේ.
Bubble sort සඳහා වැඩසටහන
``` 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( 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]) ```
ප්රතිදානය
ඇතුළත් කිරීමේ වර්ගයෙහි කාල සංකීර්ණත්වය
- නරක අවස්ථාව: ඇතුළත් කිරීමේ වර්ග කිරීම සඳහා නරකම කාල සංකීර්ණතාව O( n 2).
- සාමාන්ය අවස්ථාව: ඇතුළත් කිරීමේ වර්ග කිරීම සඳහා සාමාන්ය කාල සංකීර්ණතාව O( n 2) වේ.
- හොඳම අවස්ථාව: ඇතුළත් කිරීමේ වර්ග කිරීම සඳහා හොඳම කාල සංකීර්ණත්වය O(n) වේ.
වාසි
- එය සරලයි. සහ ක්රියාත්මක කිරීමට පහසුය.
- දත්ත මූලද්රව්ය කුඩා සංඛ්යාවක් සමඟ කටයුතු කරන අතරතුර එය හොඳින් ක්රියා කරයි.
- එය ක්රියාත්මක කිරීම සඳහා වැඩි ඉඩක් අවශ්ය නොවේ.
අවාසි
- දත්ත මූලද්රව්ය විශාල ප්රමාණයක් වර්ග කිරීම ප්රයෝජනවත් නොවේ.
- වෙනත් වර්ග කිරීමේ ක්රම සමඟ සසඳන විට එය හොඳින් ක්රියා නොකරයි.
Merge sort
මෙම වර්ග කිරීමේ ක්රමය මූලද්රව්ය නිශ්චිත අනුපිළිවෙලකට වර්ග කිරීමට බෙදීම සහ ජය ගැනීමේ ක්රමය භාවිතා කරයි. ඒකාබද්ධ කිරීමේ අනුපිළිවෙල ආධාරයෙන් වර්ග කිරීමේදී, දමූලද්රව්ය අඩකට බෙදා ඇති අතර පසුව ඒවා වර්ග කරනු ලැබේ. සියලුම භාග වර්ග කිරීමෙන් පසු, නැවත මූලද්රව්ය පරිපූර්ණ අනුපිළිවෙලක් සෑදීමට සම්බන්ධ වේ.
මෙම තාක්ෂණය තේරුම් ගැනීමට අපි උදාහරණයක් ගනිමු
- අපට සපයා ඇත. "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 log( n )).
- සාමාන්ය අවස්ථාව: ඒකාබද්ධ කිරීමේ වර්ග කිරීම සඳහා සාමාන්ය කාල සංකීර්ණතාව O( n log(4) වේ>n )).
- හොඳම අවස්ථාව: ඒකාබද්ධ කිරීමේ වර්ග කිරීම සඳහා හොඳම කාල සංකීර්ණත්වය O( n log( n )).
වාසි
- මෙම වර්ග කිරීමේ ක්රමය සඳහා ගොනු ප්රමාණය වැදගත් නොවේ.
- මෙම තාක්ෂණය සාමාන්යයෙන් අනුපිළිවෙලකට ප්රවේශ වන දත්ත සඳහා හොඳය. උදාහරණයක් ලෙස, සම්බන්ධිත ලැයිස්තු, ටේප් ඩ්රයිව් යනාදිය.
අවාසි
- අනෙක් හා සසඳන විට එයට වැඩි ඉඩක් අවශ්ය වේ වර්ග කිරීමේ ශිල්පීය ක්රම.
- එය අනෙක් ඒවාට වඩා සාපේක්ෂව අඩු කාර්යක්ෂමතාවයකි.
ඉක්මන් වර්ග කිරීම
ඉක්මන් වර්ග කිරීම නැවතත් ලැයිස්තුවක මූලද්රව්ය වර්ග කිරීමට බෙදීම සහ ජයගැනීමේ ක්රමය භාවිතා කරයි. හෝ අරාවක්. එය විවර්තන මූලද්රව්ය ඉලක්ක කර තෝරාගත් විවර්තන මූලද්රව්ය අනුව මූලද්රව්ය වර්ග කරයි.
උදාහරණයක් ලෙස
- අපිට “ 1 මූලද්රව්ය සහිත අරාවක් සපයා ඇත. ,8,3,9,4,5,7 ”.
- අපි උපකල්පනය කරමු “7” නියමු මූලද්රව්යයක් කියා.
- දැන් අපි array එක බෙදන්නෙමු. වම් පැත්තේ " 7 " යන විවර්තන මූලද්රව්යයට වඩා කුඩා මූලද්රව්ය අඩංගු වන අතර දකුණු පැත්තේ " 7 " යන විවර්තන මූලද්රව්යයට වඩා විශාල මූලද්රව්ය අඩංගු වේ.
- දැන් අපට අරා දෙකක් ඇත " 1,3,4,5 ” සහ “ 8, 9 ”.
- නැවතත්, අපි ඉහත කළ ආකාරයටම අරා දෙකම බෙදිය යුතුයි. එකම වෙනස වන්නේ pivot මූලද්රව්ය වෙනස් වීමයි.
- අපි array එකේ තනි මූලද්රව්යය ලැබෙන තුරු අපි arrays බෙදිය යුතුයි.
- අවසානයේ, a තුළ ඇති සියලුම pivot element එකතු කරන්න. වමේ සිට දකුණට අනුක්රමණය කරන්න, එවිට ඔබට පිළිවෙලට ලැබෙනු ඇතarray.
ඉක්මන් වර්ග කිරීම සඳහා වැඩසටහන
``` def Array_Partition( arr, lowest, highest ): i = ( lowest-1 ) pivot_element = arr[ highest ] for j in range( lowest, highest ): if arr[ j ] = pivot_element: i = i+1 arr[ i ], arr[ j ] = arr[ j ], arr[ i ] arr[ i+1 ], arr[ highest ] = arr[ highest ], arr[ i+1 ] return ( i+1 ) def QuickSort( arr, lowest, highest ): if len( arr ) == 1: return arr if lowest highest: pi = Array_Partition( arr, lowest, highest ) QuickSort( arr, lowest, pi-1 ) QuickSort( arr, pi+1, highest ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Unsorted array: ", arr ) QuickSort( arr, 0, n-1 ) print( " Sorted array using Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ```
ප්රතිදානය
ඉක්මන් වර්ගීකරණයේ කාල සංකීර්ණත්වය
- නරක අවස්ථාව: ඉක්මන් වර්ග කිරීම සඳහා නරකම කාල සංකීර්ණතාව O( n 2).
- සාමාන්ය අවස්ථාව: ඉක්මන් වර්ග කිරීම සඳහා සාමාන්ය කාල සංකීර්ණතාව O( n log( n ) ).
- හොඳම අවස්ථාව: ඉක්මන් වර්ග කිරීම සඳහා හොඳම කාල සංකීර්ණත්වය O( n log( n )) 16>
- එය Python හි හොඳම වර්ග කිරීමේ ඇල්ගොරිතම ලෙස හැඳින්වේ.
- එය විශාල දත්ත ප්රමාණයක් හසුරුවන විට ප්රයෝජනවත් වේ.
- එයට අමතර ඉඩක් අවශ්ය නොවේ.
- එහි නරකම සංකීර්ණත්වය බුබුලු වර්ගීකරණයේ සංකීර්ණතා හා සමාන වේ. ඇතුළත් කිරීමේ අනුපිළිවෙල.
- අපි දැනටමත් වර්ග කළ ලැයිස්තුව ඇති විට මෙම වර්ග කිරීමේ ක්රමය ප්රයෝජනවත් නොවේ.
- අපිට “ 40, 100, 30, 50, 10 ” මූලද්රව්ය සහිත අරාවක් සපයා ඇත.
- “ පියවර 1 ” හිදී අපි ගසක් සෑදුවේ අරාව තුළ මූලද්රව්ය පැවතීම.
වාසි
අවාසි
Heap sort
Heap sort යනු ද්විමය සෙවුම් ගසෙහි උසස් අනුවාදයයි. . ගොඩ වර්ග කිරීමේදී, අරාවක ශ්රේෂ්ඨතම මූලද්රව්යය සෑම විටම ගසේ මුල මත තබනු ලබන අතර, මුල හා කොළ නෝඩ් සමඟ සසඳන විට.
උදාහරණයක් ලෙස:
13>- “ පියවර 2 ” හි අපි උපරිම ගොඩවල් සාදන්නෙමු, එනම් සැකසීමට අවරෝහණ අනුපිළිවෙලෙහි මූලද්රව්ය. ශ්රේෂ්ඨතම අංගය වනු ඇතමුදුනේ (මූල) වාසය කරන අතර කුඩාම මූලද්රව්යය පහළින් (කොළ නෝඩ්) වාසය කරයි. ලබා දී ඇති අරාව " 100, 50, 30, 40, 10 " බවට පත් වේ අරාවක අවම මූලද්රව්ය සොයා ගැනීමට හැකි වන පරිදි අවම ගොඩවල් සාදමින් සිටී. මෙය සිදු කිරීමෙන්, අපි උපරිම සහ අවම මූලද්රව්ය ලබා ගනිමු.
- “ පියවර 4 ” හි එකම පියවරයන් සිදු කිරීමෙන් අපි වර්ග කළ අරාව ලබා ගනිමු.
Heap sort සඳහා වැඩසටහන
``` 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 ] ) ```
ප්රතිදානය
Heap වර්ගීකරණයේ කාල සංකීර්ණතාව
- නරක අවස්ථාව: Heap වර්ග කිරීම සඳහා ඇති නරකම කාල සංකීර්ණය වේ O( n log( n )).
- සාමාන්ය අවස්ථාව: Heap වර්ග කිරීම සඳහා සාමාන්ය කාල සංකීර්ණතාව O( n log( n )).
- හොඳම අවස්ථාව: Heap sort සඳහා හොඳම කාල සංකීර්ණතාව isO( n log(4)>n )).
වාසි
- එය බොහෝ දුරට භාවිතා වන්නේ එහි ඵලදායිතාව නිසාය.
- එය හැක. ස්ථානගත ඇල්ගොරිතමයක් ලෙස ක්රියාවට නැංවිය යුතුය.
- එයට විශාල ගබඩාවක් අවශ්ය නොවේ.
අවාසි
- ඉඩ අවශ්ය වේ මූලිකාංග වර්ග කිරීම
හොඳම අවස්ථා කාල සංකීර්ණතාව සාමාන්ය අවස්ථා කාල සංකීර්ණතාව නරක අවස්ථාව කාල සංකීර්ණත්වය අභ්යවකාශ සංකීර්ණතාව ස්ථාවරත්වය තුළ -
-