په Python کې د مختلف ترتیب کولو میتودونو او الګوریتمونو په کارولو سره د لیستونو ، اریونو ، لغتونو او نورو ترتیب کولو لپاره د Python Sort فنکشن کارولو څرنګوالي زده کړئ:
ترتیب کول یو تخنیک دی چې د ترتیب کولو لپاره کارول کیږي ډیټا په یو ترتیب ترتیب کې یا په نزول یا ښکته کې.
اکثره وخت د لویو پروژو ډاټا په سم ترتیب کې نه تنظیمیږي او دا د اړتیا وړ معلوماتو ته د لاسرسي او ترلاسه کولو په وخت کې ستونزې رامینځته کوي.د دې ستونزې د حل لپاره د ترتیب کولو تخنیکونه کارول کیږي. Python د ترتیب کولو مختلف تخنیکونه وړاندې کوي د مثال په توګه، د بلبل ترتیب، داخلولو ترتیب، یوځای کولو ترتیب، Quicksort، او داسې نور.
په دې ټیوټوریل کې، موږ به پوه شو چې څنګه په Python کې د مختلف الګوریتمونو په کارولو سره ترتیب کول کار کوي.
د پایتون ترتیب
د پایتون ترتیب
د ترتیب کولو ترسره کولو لپاره، Python جوړ شوی فنکشن چمتو کوي د بیلګې په توګه د "sort()" فنکشن. دا د لیست د ډیټا عناصرو د ترتیب کولو لپاره کارول کیږي په پورته ترتیب یا په ښکته ترتیب کې.
راځئ چې دا مفهوم د مثال په توګه پوه کړو.
0>1>مثال 1:``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```
آؤټ پوټ:
په دې مثال کې، ورکړل شوی بې ترتیب شوی لیست د "srt()" فنکشن په کارولو سره په پورته ترتیب کې ترتیب شوی. .
مثال 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```
آؤټ پټ
12>
په پورتني مثال کې، ورکړل شوی بې ترتیب شوی لیست د " sort( reverse = True )" فنکشن په کارولو سره په برعکس ترتیب کې ترتیب شوی.
وختځای د بلبل ترتیب O(n) O(n2) O(n2) O(1) هو هو د داخلولو ترتیب 42 O(n) O(n2) O(n2) O(1) هو 41 هو چټ ترتیب 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) نه هو
په پورتني پرتله کولو جدول کې "O" د لوی اوه نښه ده چې پورته تشریح شوي پداسې حال کې چې "n" او "N" د ان پټ اندازه معنی لري. .
مکرر پوښتل شوي پوښتنې
پوښتنه # 1) په Python کې ترتیب () څه شی دی؟
ځواب: په پایتون کې sort() یو فنکشن دی چې په یو ځانګړي ترتیب کې د لیستونو یا صفونو ترتیبولو لپاره کارول کیږي. دا فعالیت په لویو پروژو کې د کار کولو پرمهال د ترتیب کولو پروسه اسانه کوي. دا د پراختیا کونکو لپاره خورا ګټور دی.
پوښتنه # 2) تاسو په Python کې څنګه ترتیب کوئ؟
0> ځواب: Python د ترتیب کولو مختلف تخنیکونه وړاندې کوي چې د عنصر ترتیب کولو لپاره کارول کیږي. د مثال په توګه، چټک ترتیب، د یوځای کولو ترتیب، د بلبل ترتیب، د داخلولو ترتیب، او داسې نور. د ترتیب کولو ټول تخنیکونه اغیزمن او د پوهیدو لپاره اسانه دي.پوښتنه #3) پایتون څنګه sort () کار؟
0> ځواب: ترتیب()فنکشن د کارونکي څخه د ننوتلو په توګه ورکړل شوی سري اخلي او د ترتیب کولو الګوریتم په کارولو سره په ځانګړي ترتیب کې ترتیبوي. د الګوریتم انتخاب د کارونکي انتخاب پورې اړه لري. کاروونکي کولی شي د کارونکي اړتیاو پراساس Quick sort, Merge sort, Bubble sort, Insertion sort او داسې نور استعمال کړي.پایله
په پورتني ټیوټوریل کې مو د Python سره د ترتیب کولو تخنیک په اړه بحث وکړ. د ترتیب کولو عمومي تخنیکونه.
- د بلبل ترتیب
- د داخلولو ترتیب
- چټک ترتیب
موږ د دوی د وخت پیچلتیاو او ګټو په اړه زده کړل & زیانونه موږ پورته ټول تخنیکونه هم پرتله کړل.
د ترتیب کولو الګوریتم پیچلتیاد وخت پیچلتیا هغه وخت دی چې کمپیوټر د یو ځانګړي الګوریتم چلولو لپاره اخلي. دا د وخت پیچلتیا درې ډوله قضیې لري.
- تر ټولو بد حالت: د کمپیوټر لخوا د برنامه چلولو لپاره اعظمي وخت نیول شوی.
- اوسط قضیه: د کمپیوټر لخوا د پروګرام د چلولو لپاره د لږترلږه او اعظمي تر مینځ وخت.
- غوره قضیه: د پروګرام چلولو لپاره د کمپیوټر لخوا لږ تر لږه وخت. دا د وخت د پیچلتیا غوره قضیه ده.
د پیچلتیا یادونه
لوی اوه نوټیشن، O: لوی اوه نوټیشن د پورتنۍ حد د رسولو رسمي لاره ده د الګوریتم چلولو وخت. دا د بدترین حالت د وخت پیچلتیا اندازه کولو لپاره کارول کیږي یا موږ ووایو چې د الګوریتم لخوا د بشپړولو لپاره ترټولو لوی وخت اخیستل کیږي.
Big omega Notation, : Big omega notation is د الګوریتم چلولو وخت ترټولو ټیټ حد ته رسولو رسمي لاره. دا د غوره قضیې د وخت پیچلتیا اندازه کولو لپاره کارول کیږي یا موږ د الګوریتم لخوا اخیستل شوي خورا ښه وخت وايو.
Theta Notation, : Theta Notation د رسولو رسمي لاره ده دواړه حدود لکه د الګوریتم لخوا د بشپړولو لپاره د وخت ښکته او پورته.
په Python کې د ترتیب کولو میتودونه
د ببل ترتیب
د ببل ترتیب د ډیټا ترتیب کولو ترټولو ساده لاره ده کوم چې د وحشي ځواک تخنیک کاروي. دا به د هر ډیټا عنصر ته تکرار کړي او د نورو عناصرو سره یې پرتله کړيد دې لپاره چې کارونکي ته ترتیب شوي ډاټا چمتو کړي.
راځئ چې د دې تخنیک د پوهیدو لپاره یو مثال واخلو: 3>
- موږ ته یو داسې سرې چمتو شوي چې عناصر لري " ۱۰، ۴۰، ۷، ۳، ۱۵”. اوس، موږ اړتیا لرو چې دا سرې په Python کې د بلبل ډول ډول تخنیک په کارولو سره په پورته ترتیب کې تنظیم کړو.
- لومړی ګام دا دی چې په ورکړل شوي ترتیب کې سرې ترتیب کړئ.
- په "Iteration 1" کې، موږ د سرې لومړی عنصر د نورو عناصرو سره یو په یو پرتله کوو.
- سرخ تیر د یو صف له نورو عناصرو سره د لومړي عناصرو پرتله کول بیانوي.
- که تاسو ګورئ چې "10" د "40" څخه کوچنی دی نو دا په ورته پاتې کیږي ځای مګر راتلونکی عنصر "7" د "10" څخه کوچنی دی. له دې امله دا ځای په ځای کیږي او لومړی ځای ته راځي.
- پورتنۍ پروسه به بیا بیا د عناصرو د ترتیب کولو لپاره ترسره کیږي.
-
- په "Iteration 2" کې دوهم عنصر د سري د نورو عناصرو سره پرتله کیږي.
- که پرتله شوي عنصر کوچنی وي نو دا به بدل کړئ، که نه نو دا به په ورته ځای کې پاتې شي.
-
- دریم عنصر د سري د نورو عناصرو سره پرتله کیږي.
-
- په اخر کې "Iteration 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)) ```
آؤټپټ
0>23>د بلبل ترتیب د وخت پیچلتیا
- تر ټولو بد حالت: د بلبل ترتیب لپاره د خراب وخت پیچلتیا O( n 2) ده.
- اوسط قضیه: د بلبل ترتیب لپاره د اوسط وخت پیچلتیا O(4) ده>n 2).
- غوره قضیه: د بلبل ترتیب لپاره غوره وخت پیچلتیا O(n) ده.
ګټې
- دا اکثرا کارول کیږي او پلي کول یې اسانه دي.
- موږ کولی شو د لنډ مهاله ذخیره کولو مصرف پرته د ډیټا عناصر بدل کړو.
- دا لږ اړتیا لري ځای.
نقصانات
- دا د ډیری لوی ډیټا عناصرو سره معامله کولو په وخت کې ښه کار نه دی کړی.
- دا د ترتیب کولو لپاره د هر "n" شمیرې عناصرو لپاره n 2 مرحلو ته اړتیا لري.
- دا د ریښتیني نړۍ غوښتنلیکونو لپاره واقعیا ښه ندي.
داخلول ترتیب
د داخلولو ترتیب یو اسانه او ساده ترتیب کولو تخنیک دی چې د لوبې کارتونو ترتیب کولو ته ورته کار کوي. د داخلولو ترتیب د هر عنصر یو له بل سره د پرتله کولو له لارې عناصر ترتیبوي. عناصر د بل عنصر سره غوره شوي او تبادله کیږي که چیرې عنصر له بل څخه لوی یا کوچنی وي.
راځئ یو مثال واخلو
13>14>موږ ته چمتو شوي یو سري چې عناصر لري " 100, 50, 30, 40, 10".
د داخلولو ترتیب لپاره برنامه
``` 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>![](/wp-content/uploads/guides/fn0zxgkuva-10.png)
د وخت پیچلتیا د داخلولو ترتیب
- تر ټولو بد حالت: د داخلولو ترتیب لپاره ترټولو خراب وخت پیچلتیا O( n 2).
- اوسط قضیه: د داخلولو ترتیب لپاره د اوسط وخت پیچلتیا O( n 2) ده.
- غوره قضیه: د داخلولو ترتیب لپاره غوره وخت پیچلتیا O(n) ده.
ګټې
13>نیمګړتیاوې
- دا ګټوره نه ده چې د ډیټا عناصرو لوی شمیر ترتیب کړئ.
- کله چې د نورو ترتیب کولو تخنیکونو سره پرتله کیږي دا ښه کار نه کوي. 16>
- موږ ته چمتو شوي. یو صف "7، 3، 40، 10، 20، 15، 6، 5" صف 7 عناصر لري. که موږ دا په نیمایي کې وویشو ( 0 + 7 / 2 = 3 ).
- په دویم ګام کې، تاسو به وګورئ چې عناصر په دوه برخو ویشل شوي. هر یو په کې 4 عناصر لري.
- بیا، عناصر بیا ویشل شوي او هر یو دوه عناصر لري.
- دا پروسه به تر هغه دوام وکړي تر څو چې یوازې یو عنصر په صف کې شتون ولري. ګام نمبر ته مراجعه وکړئ. 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) ```
آؤټ پټ 3>
د ادغام ترتیب د وخت پیچلتیا
- تر ټولو بد حالت: د ادغام ترتیب لپاره ترټولو خراب وخت پیچلتیا O( n log( n )).
- اوسط قضیه: د ادغام ترتیب لپاره د اوسط وخت پیچلتیا O( n log(4)>n )).
- غوره قضیه: د ادغام ترتیب لپاره غوره وخت پیچلتیا O( n log( n )).
ګټې
- د دې ترتیب کولو تخنیک لپاره د فایل اندازه مهمه نده. 14 د مثال په توګه، تړل شوي لیستونه، ټیپ ډرایو، او داسې نور.
نقصانات
- دا د نورو په پرتله ډیر ځای ته اړتیا لري د ترتیب کولو تخنیکونه.
- دا د نورو په پرتله نسبتا لږ اغیزمن دی.
چټک ترتیب
چټک ترتیب بیا د ویشلو او فتح کولو طریقه کاروي ترڅو د لیست عناصر ترتیب کړي. یا یو لړ. دا د محور عناصر په نښه کوي او عناصر د ټاکل شوي محور عنصر سره سم ترتیبوي.
د مثال په توګه
- موږ ته د عناصرو سره یو سرې چمتو شوي دي "1 ,8,3,9,4,5,7”.
- راځئ چې "7" د پیلوټ عنصر په توګه فرض کړو.
- اوس به موږ سرې په داسې ډول ویشو چې کیڼ اړخ هغه عناصر لري کوم چې د محور عنصر "7" څخه کوچني دي او ښي اړخ کې د محور عنصر "7" څخه لوی عناصر لري.
- موږ اوس دوه صفونه لرو " 1,3,4,5 "او" 8, 9".
- بیا، موږ باید دواړه صفونه په هماغه ډول وویشو لکه څنګه چې موږ پورته کړي. یوازینی توپیر دا دی چې د محور عناصر بدلیږي.
- موږ اړتیا لرو چې سرې ویشو تر هغه چې موږ په صف کې واحد عنصر ترلاسه کړو.
- په پای کې، ټول محور عناصر په یوه کې راټول کړو له کیڼ څخه ښي ته ترتیب او تاسو به ترتیب شوي ترلاسه کړئصف.
د چټک ترتیب لپاره برنامه
``` 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(4) ده>n 2).
- اوسط قضیه: د چټک ترتیب لپاره د اوسط وخت پیچلتیا O( n log( n ) ).
- غوره قضیه: د چټک ترتیب لپاره غوره وخت پیچلتیا O( n log( n )).
ګټې
- دا په Python کې د غوره ترتیب کولو الګوریتم په توګه پیژندل کیږي.
- دا د ډیټا لوی مقدار اداره کولو پرمهال ګټور دی.15
- دا اضافي ځای ته اړتیا نلري.
ضررونه 3>
- د دې تر ټولو بد حالت پیچلتیا د بلبل ډول پیچلتیاو سره ورته ده او د داخلولو ترتیب.
- د ترتیب کولو دا طریقه ګټوره نه ده کله چې موږ مخکې له مخکې ترتیب شوی لیست لرو.
هیپ سورټ
هیپ سورټ د بائنری لټون ونې پرمختللې نسخه ده . د هپ په ترتیب کې، د سرې ترټولو لوی عنصر د ونې په ریښه کې تل او بیا ځای پرځای کیږي، د ریښې سره د پاڼی نوډونو سره پرتله کیږي.
د مثال په توګه:
- مونږ ته د "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 ] ) ```
آؤټ پوټ
د هپ ترتیب د وخت پیچلتیا
- تر ټولو بد حالت: د هپ ترتیب لپاره ترټولو خراب وخت پیچلتیا ده O( n log( n )).
- اوسط قضیه: د هپ ترتیب لپاره د اوسط وخت پیچلتیا O( n) ده log( n )).
- غوره قضیه: د هپ ترتیب لپاره غوره وخت پیچلتیا دهO( n log( n ))).
ګټې
13>زیانونه
13>د ترتیب کولو تخنیکونو ترمنځ پرتله کول
د ترتیب کولو طریقه | د قضیې د وخت غوره پیچلتیا | د قضیې اوسط وخت پیچلتیا | د قضیې ترټولو خراب وخت پیچلتیا | د ځای پیچلتیا | ثبات | په - |
---|