Ionnsaich mar a chleachdas tu an gnìomh Python Sort airson liostaichean, arrays, faclairean is eile a sheòrsachadh a’ cleachdadh diofar dhòighean seòrsachaidh agus algairim ann am Python:
’S e innleachd a th’ ann an seòrsachadh a thathas a’ cleachdadh airson a sheòrsachadh an dàta ann an òrdugh sreath an dara cuid ann an òrdugh dìreadh no teàrnadh.
A’ mhòr-chuid den ùine chan eil dàta nam pròiseactan mòra air an rèiteachadh san òrdugh cheart agus cruthaichidh seo duilgheadasan fhad ‘s a thathar a’ faighinn cothrom air agus a’ faighinn an dàta a tha a dhìth gu h-èifeachdach.
Tha dòighean seòrsachaidh gan cleachdadh gus an duilgheadas seo fhuasgladh. Tha Python a' toirt seachad diofar dhòighean seòrsachaidh mar eisimpleir, Bubble sort, Insertion sort, Merge sort, Quicksort, etc.
San oideachadh seo, tuigidh sinn mar a dh'obraicheas rèiteachadh ann am Python le bhith a' cleachdadh diofar algorithms.
Python Sort
Syntax of Python Sort
> Gus rèiteachadh a dhèanamh, tha Python a’ toirt seachad an gnìomh togte ie an gnìomh “seòrsa ()”. Tha e air a chleachdadh gus eileamaidean dàta liosta a sheòrsachadh ann an òrdugh dìreadh no ann an òrdugh teàrnaidh.
Tuigidh sinn am bun-bheachd seo le eisimpleir.
Eisimpleir 1:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```
Cur a-mach:
San eisimpleir seo, tha an liosta neo-òrdaichte a chaidh a thoirt seachad air a rèiteachadh ann an òrdugh dìreadh le bhith a’ cleachdadh a’ ghnìomh “seòrsa()” .
Eisimpleir 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```
Toradh
San eisimpleir gu h-àrd, tha an liosta neo-òrdaichte a chaidh a thoirt seachad air a sheòrsachadh san òrdugh cùil a’ cleachdadh a’ ghnìomh “ sort ( reverse = True ) ”.
Ùineàite Bubble sort O(n) O(n2) O(n2) O(1) Tha Tha Seòrsa cuir a-steach O(n) O(n2) O(n2) O(1) Tha Tha > Sgrìobhadh sgiobalta O(n log(n)) O(n log(n)) O(n2) O(N) Chan eil Tha Ceangail seòrsa O(n log(n)) O(n log(n)) O(n log(n)) O(N) Tha Chan eil Heap sort O(n log (n)) O(n log(n)) O(n log(n)) O(1) Chan eil Tha
Anns a’ chlàr coimeas gu h-àrd tha “O” an comharradh Big Oh air a mhìneachadh gu h-àrd ach tha “n” agus “N” a’ ciallachadh meud an in-chur .
Ceistean Bitheanta
Q #1) Dè a th’ ann an sort () ann am Python?
Freagair: Ann am Python sort () na ghnìomh a thathas a’ cleachdadh gus na liostaichean no na rèilichean a sheòrsachadh ann an òrdugh sònraichte. Bidh an gnìomh seo a’ comasachadh a’ phròiseas rèiteach fhad ‘s a tha thu ag obair air pròiseactan mòra. Tha e gu math cuideachail dhan luchd-leasachaidh.
Q #2) Ciamar a nì thu rèiteachadh ann am Python?
Freagra: Tha Python a’ toirt seachad diofar dhòighean seòrsachaidh a thathas a’ cleachdadh airson an eileamaid a sheòrsachadh. Mar eisimpleir, Seòrsachadh sgiobalta, seòrsachadh Co-aonadh, Bubble sort, Insert sort, etc. Tha na dòighean seòrsachaidh uile èifeachdach agus furasta a thuigsinn.
Q #3) Ciamar a tha Python seòrsa () obair?
Freagair: An seòrsa()Bidh gnìomh a’ gabhail an raon a chaidh a thoirt seachad mar chuir a-steach bhon neach-cleachdaidh agus ga sheòrsachadh ann an òrdugh sònraichte a’ cleachdadh an algairim seòrsachaidh. Tha taghadh an algairim an urra ri roghainn an neach-cleachdaidh. Faodaidh luchd-cleachdaidh a chleachdadh Quick sort, Merge sort, Bubble sort, Insertion sort, etc a rèir feumalachdan an neach-cleachdaidh.
Co-dhùnadh
San oideachadh gu h-àrd, bheachdaich sinn air an dòigh seòrsachaidh ann am Python còmhla ris an dòighean seòrsachaidh coitcheann.
- Deasaich builgean
- Cuir a-steach Deasaich
- Deasachadh Luath
Dh’ionnsaich sinn mun ùine aca iom-fhillteachd agus buannachdan & eas-bhuannachdan. Rinn sinn coimeas cuideachd eadar na dòighean gu h-àrd.
Iom-fhillteachd nan Algorithms DeasachaidhÙine Is e iom-fhillteachd an ùine a bheir an coimpiutair gus algairim sònraichte a ruith. Tha trì seòrsaichean de chùisean iom-fhillteachd ùine ann.
- An Cùis as Miosa: An ùine as motha a bheir an coimpiutair airson am prògram a ruith.
- Cuibheasach: An ùine a bheir a' choimpiutair eadar an ìre as lugha agus as motha airson am prògram a ruith.
- A' chùis as fheàrr: An ùine as lugha a bheir a' choimpiutair dhan phrògram a ruith. 'S e seo a' chùis as fheàrr a thaobh iom-fhillteachd ùine.
Comharraidhean Iom-fhillteachd
Big Oh Notation, O: 'S e comharrachadh mòr oh an dòigh oifigeil air a' chrìoch àrd a chur an cèill ùine ruith nan algorithms. Tha e air a chleachdadh gus iom-fhillteachd na h-ùine as miosa a thomhas no canaidh sinn an ùine as motha a bheir an algairim airson a chrìochnachadh.
Big omega Notation, : Tha comharradh omega mòr ann an dòigh oifigeil air a’ chrìoch as ìsle de ùine ruith nan algorithms a thoirt seachad. Tha e air a chleachdadh gus iom-fhillteachd ùine sa chùis as fheàrr a thomhas no canaidh sinn an deagh ùine a bheir an algairim seachad.
Theta Notation, : 'S e comharradh Theta an dòigh oifigeil air a chur an cèill. an dà chrìoch, i.e. nas ìsle agus gu h-àrd den ùine a bheir an algairim airson a chrìochnachadh.
Dòighean Deasachaidh ann am Python
Deasachadh Bubble
'S e seòrsa builgean an dòigh as sìmplidh air an dàta a rèiteachadh a tha a’ cleachdadh innleachd feachd brute. Bidh e ag ath-aithris gu gach eileamaid dàta agus ga choimeas ri eileamaidean eilegus an dàta a chaidh a sheòrsachadh a thoirt don neach-cleachdaidh.
Gabhamaid eisimpleir airson an dòigh seo a thuigsinn:
- Tha sinn a’ faighinn raon anns a bheil na h-eileamaidean “ 10, 40, 7, 3, 15 ”. A-nis, feumaidh sinn an t-sreath seo a chuir air dòigh ann an òrdugh dìreadh a’ cleachdadh an dòigh seòrsachadh Bubble ann am Python.
- Is e a’ chiad cheum an t-sreath a chur air dòigh san òrdugh a chaidh a thoirt seachad.
- Ann an “Iris 1”, tha sinn a’ dèanamh coimeas eadar a’ chiad eileamaid de rèite agus na h-eileamaidean eile aon às deidh aon.
- Tha na saighdean dearga a’ toirt cunntas air coimeas a’ chiad eileamaidean leis na h-eileamaidean eile ann an sreath.
- Ma bheir thu fa-near gu bheil “10” nas lugha na “40” mar sin, bidh e aig an aon àm. àite ach tha an ath eileamaid “7” nas lugha na “10”. Mar sin thèid a chur na àite agus thig e sa chiad àite.
- Thèid am pròiseas gu h-àrd a dhèanamh a-rithist is a-rithist gus na h-eileamaidean a rèiteachadh.
-
- Ann an “Iter 2” tha an dàrna eileamaid ga choimeas ri eileamaidean eile ann an sreath.
- Ma tha an eileamaid coimeasach beag an uairsin, nì e faigh fear ùr, air neo mairidh e san aon àite.
-
- Ann an “ Iteration 3 ” tha an treas eileamaid ga choimeas ri eileamaidean eile ann an sreath.
-
- San fhear mu dheireadh “ Iteration 4 ” tha an dàrna eileamaid mu dheireadh a’ faighinn coimeas ris na h-eileamaidean eile ann an sreath.
- Ann anan ceum seo tha an t-sreath air a rèiteachadh san òrdugh dìreadh.
Program airson 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)) ```
Cur a-mach
Trice iom-fhillteachd seòrsa builgean
- A’ chùis as miosa: 'S e O( n 2) an iom-fhillteachd ùine as miosa airson seòrsa builgean).
- Cùis Chuibheasach: 'S e O(4) an iom-fhillteachd ùine chuibheasach airson seòrsa builgean> n 2).
- Cùis as Fheàrr: 'S e O(n) an iom-fhillteachd ùine as fheàrr airson seòrsa builgean.
Buannachdan
- Tha e air a chleachdadh sa mhòr-chuid agus tha e furasta a chur an gnìomh.
- Is urrainn dhuinn na h-eileamaidean dàta atharrachadh gun a bhith a' cleachdadh stòras geàrr-ùine.
- Tha feum air nas lugha space.
Ana-bhuannachdan
- Cha do dh'obraich e gu math fhad 's a bha e a' dèiligeadh ri àireamh mhòr de dh'eileamaidean dàta mòra.
- It feumach air n 2 cheum airson gach “n” de dh’ eileamaidean dàta airson an rèiteachadh.
- Chan eil e uabhasach math airson prògraman san t-saoghal fhìor.
Cuir a-steach Deasaich
’S e dòigh seòrsachaidh furasta is sìmplidh a th’ ann an cuir a-steach a tha ag obair coltach ri bhith a’ rèiteach nan cairtean cluiche. Bidh cuir a-steach a’ seòrsachadh nan eileamaidean le bhith a’ dèanamh coimeas eadar gach eileamaid aon ri aon leis an fhear eile. Thèid na h-eileamaidean a thaghadh agus an atharrachadh leis an eileamaid eile ma tha an eileamaid nas motha no nas lugha na an eileamaid eile.
Gabhaidh sinn eisimpleir
- Tha sinn sreath anns a bheil na h-eileamaidean “100, 50, 30, 40, 10”.
- An toiseach, bidh sinn a’ rèiteachadh an t-sreath agus a’ tòiseachadh a’ dèanamh coimease.
- Sa chiad cheum tha “100” air a choimeas ris an dàrna eileamaid “50”. Tha “ 50 ” air a mhalairteachadh le “ 100 ” mar a tha e nas motha.
- San dàrna ceum, a-rithist tha an dàrna eileamaid “100” ga choimeas ris an treas eileamaid “30” agus thèid a h-iomlaid.
- > A-nis, ma bheir thu an aire gu bheil “30” a’ tighinn chun chiad àite leis gu bheil e a-rithist nas lugha na “50”.
- Tachraidh an coimeas gus an eileamaid mu dheireadh de raon agus aig an deireadh, gheibh sinn an dàta air a sheòrsachadh.
Prògram airson cuir a-steach seòrsachadh
``` 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]) ```
Toradh
Tiom-fhillteachd ùine an t-seòrsa cuir a-steach
- A’ chùis as miosa: Is e an iom-fhillteachd ùine as miosa airson seòrsa cuir a-steach O( n 2).
- Cùis Chuibheasach: 'S e O( n 2) an iom-fhillteachd ùine chuibheasach airson seòrsa Insertion. Cùis as Fheàrr: Is e an iom-fhillteachd ùine as fheàrr airson seòrsa cuir a-steach O(n).
Buannachdan
- Tha e sìmplidh agus furasta a chur an gnìomh.
- Tha e a' coileanadh gu math fhad 's a thathar a' dèiligeadh ri àireamh bheag de eileamaidean dàta.
- Chan fheum e barrachd rùm airson a chur an gnìomh.
Ana-cothroman
- Chan eil e cuideachail àireamh mhòr de eileamaidean dàta a sheòrsachadh.
- An coimeas ri dòighean seòrsachaidh eile chan eil e a’ coileanadh gu math.
Co-sheòrsachadh
Tha an dòigh seòrsachaidh seo a’ cleachdadh an dòigh roinneadh is ceannsachadh gus na h-eileamaidean a sheòrsachadh ann an òrdugh sònraichte. Fhad ‘s a tha thu a’ rèiteachadh le cuideachadh bho sheòrsachadh aonaidh, tha antha eileamaidean air an roinn ann an leth agus an uairsin, bidh iad air an rèiteachadh. An dèidh a h-uile leth a rèiteachadh, a-rithist thèid na h-eileamaidean a cheangal gus òrdugh foirfe a chruthachadh.
Gabhaidh sinn eisimpleir gus an dòigh seo a thuigsinn
- Tha sinn a’ faighinn sreath “7, 3, 40, 10, 20, 15, 6, 5”. Tha 7 eileamaidean anns an t-sreath. Ma tha sinn ga roinn na leth ( 0 + 7 / 2 = 3 ).
- Anns an dàrna ceum, chì thu gu bheil na h-eileamaidean air an roinn ann an dà phàirt. Gach fear le 4 eileamaidean innte.
- A bharrachd, tha na h-eileamaidean air an roinn a-rithist agus tha 2 eileamaid an urra.
- Leanaidh am pròiseas seo air adhart gus nach bi ach aon eileamaid an làthair ann an sreath. Thoir sùil air ceum no. 4 san dealbh.
- A-nis, rèitichidh sinn na h-eileamaidean agus tòisichidh sinn gan ceangal mar a bha sinn air ar roinn.
- Ann an ceum n. 5 ma bheir thu an aire gu bheil 7 nas motha na 3, mar sin atharraichidh sinn iad agus thèid sinn còmhla ris san ath cheum agus a chaochladh.
- Aig an deireadh, chì thu gu bheil an t-sreath againn air a rèiteachadh ann an òrdugh dìreadh.
Program airson aonadh seòrsa
``` 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) ```
Toradh
Iom-fhillteachd ùine an t-seòrsa aonaidh
- A’ chùis as miosa: ’S e O( n
log ( n )). - Cùis Chuibheasach: 'S e O( n log(4) an iom-fhillteachd ùine chuibheasach airson seòrsa aonaidh> n )).
- Cùis as Fheàrr: 'S e O( n an iom-fhillteachd ùine as fheàrr airson seòrsa aonadhlog( n )).
Buannachdan
- Chan eil meud an fhaidhle gu diofar a thaobh an dòigh seo de sheòrsachadh.15
- Tha an dòigh seo math airson an dàta a gheibhear sa chumantas ann an òrdugh sreath. Mar eisimpleir, liostaichean ceangailte, draibh teip, is msaa. dòighean seòrsachaidh.
- Tha e an ìre mhath nas èifeachdaich na feadhainn eile.
Seòrsachadh luath
Cleachdaidh seòrsachadh sgiobalta a-rithist am modh roinneadh is ceannsachadh gus na h-eileamaidean de Liosta a sheòrsachadh no sreath. Bidh e ag amas air na h-eileamaidean pivot agus a’ rèiteach nan eileamaidean a-rèir an eileamaid pivot taghte.
Mar eisimpleir
- Tha sinn a’ faighinn raon anns a bheil na h-eileamaidean “ 1 ,8,3,9,4,5,7 ”.
- Gabhamaid ris gur e eileamaid phìleat a th’ ann an “7”.
- A-nis roinnidh sinn an t-sreath ann an dòigh is gun air an taobh chlì tha na h-eileamaidean a tha nas lugha na an eileamaid pivot “7” agus air an taobh cheart tha na h-eileamaidean nas motha na an eileamaid pivot “7”.
- Tha dà raon againn a-nis “ 1,3,4,5 ” agus “ 8, 9 ”.
- A rithist, feumaidh sinn an dà sreath a roinn mar a rinn sinn gu h-àrd. Is e an aon diofar gu bheil na h-eileamaidean pivot air an atharrachadh.
- Feumaidh sinn na h-àirighean a roinn gus am faigh sinn an aon eileamaid san t-sreath.
- Aig an deireadh, cruinnich na h-eileamaidean pivot gu lèir ann an a sreath bho chlì gu deas agus gheibh thu an rèiteachadhsreath.
Prògram airson seòrsa luath
``` 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 ] ) ```
Toradh
Iom-fhillteachd ùine de sheòrsa luath
- A’ chùis as miosa: ’S e O(4) an iom-fhillteachd ùine as miosa airson Quick sort> n 2).
- Cùis Chuibheasach: 'S e an iom-fhillteachd ùine chuibheasach airson Quick sort O( n log( n ) ).
- Cùis as Fheàrr: Is e an iom-fhillteachd ùine as fheàrr airson seòrsa Quick O( n log( n )).
Buannachdan
- Tha e aithnichte mar an algairim seòrsachaidh as fheàrr ann am Python.
- Tha e feumail fhad ‘s a thathar a’ làimhseachadh tòrr dàta.15
- Chan eil feum air àite a bharrachd.
Ana-bhuannachdan
- Tha an toinnteachd as miosa aige coltach ri iom-fhillteachd seòrsa builgean agus seòrsa cuir a-steach.
- Chan eil an dòigh seòrsachaidh seo feumail nuair a tha an liosta a chaidh a sheòrsachadh againn mu thràth.
Seòrsa cruachan
Seòrsa cruachan an tionndadh adhartach de chraobh rannsachaidh dhàna . Ann an seòrsachadh tiùrr, tha an eileamaid as motha de rèite air a chur air freumh na craoibhe an-còmhnaidh agus an uairsin, an taca ris a’ fhreumh le nodan na duilleige.
Mar eisimpleir:
- Tha sinn a’ faighinn sreath anns a bheil na h-eileamaidean “40, 100, 30, 50, 10”.
- Ann an “ ceum 1 ” rinn sinn craobh a rèir an làthaireachd nan eileamaidean san raon.
- Ann an “ ceum 2” tha sinn a’ dèanamh a’ char as àirde, i.e. an eileamaidean ann an òrdugh teàrnadh. Bidh an eileamaid as mothafuireach aig a’ mhullach (freumh) agus tha an eileamaid as lugha a’ fuireach aig a’ bhonn (nodan duille). Bidh an raon a chaidh a thoirt seachad gu bhith “100, 50, 30, 40, 10”.
- Ann an “ ceum 3 ” , bidh sinn a’ dèanamh a’ charn as lugha gus an lorg sinn na h-eileamaidean as lugha ann an sreath. Le bhith a' dèanamh seo, gheibh sinn na h-eileamaidean as àirde agus as ìsle.
- Ann an "ceum 4" le bhith a' coileanadh nan aon cheuman gheibh sinn an t-sreath a chaidh a sheòrsachadh.
Program for 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 ] ) ```
Toradh
Tom-iom-fhillteachd ùine de sheòrsa cruachan
- A’ chùis as miosa: Is e an iom-fhillteachd ùine as miosa airson seòrsa Heap O( n log( n ))).
- Cùis Chuibheasach: Is e an iom-fhillteachd ùine chuibheasach airson seòrsa Heap O( n log( n ))).
- Cùis as Fheàrr: An iom-fhillteachd ùine as fheàrr airson seòrsa Heap isO( n log(4)>n )).
Buannachdan
- Tha e air a chleachdadh sa mhòr-chuid air sgàth a chinneasachd.
- Faodaidh e a chur an gnìomh mar algairim in-àite.
- Chan eil feum air stòradh mòr.
Anacothrom
- Tha feum air àite airson a' rèiteach nan eileamaidean.
- Tha e a' dèanamh na craoibhe airson na h-eileamaidean a sheòrsachadh.
Coimeas eadar na dòighean seòrsachaidh
Dòigh Deasachaidh | Iom-fhillteachd ùine cùise as fheàrr | Tiom-fhillteachd cuibheasach ùine cùise | An iom-fhillteachd ùine cùise as miosa | Iom-fhillteachd àite | Seasmhachd | San - |
---|