Lernu kiel uzi la funkcion Python Sort por ordigi listojn, tabelojn, vortarojn ktp uzante diversajn ordigajn metodojn kaj algoritmojn en Python:
Ordigo estas tekniko uzata por ordigo. la datumoj en sinsekvo ordo aŭ en suprena aŭ malkreska ordo.
Plej ofte la datumoj de la grandaj projektoj ne estas aranĝitaj en la ĝusta ordo kaj tio kreas problemojn dum aliro kaj alportado de la bezonataj datumoj efike.
Ordigaj teknikoj estas uzataj por solvi ĉi tiun problemon. Python provizas diversajn ordigteknikojn ekzemple, Bobel-ordigo, Enmeta ordigo, Kunfandi, Quicksort, ktp.
En ĉi tiu lernilo, ni komprenos kiel ordigo funkcias en Python uzante diversajn algoritmojn.
Python Ordigo
Sintakso de Python Ordigo
Por fari ordigon, Python disponigas la enkonstruitan funkcion t.e. la funkcion "sort()". Ĝi estas uzata por ordigi la datumelementojn de listo en suprena ordo aŭ en malkreska ordo.
Ni komprenu ĉi tiun koncepton per ekzemplo.
Ekzemplo 1:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```
Eligo:
En ĉi tiu ekzemplo, la donita neordigita listo estas ordigita en kreskanta ordo uzante la funkcion “ ordigi ( ) ” .
Ekzemplo 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```
Eligo
En la supra ekzemplo, la donita neordigita listo estas ordigita en la inversa sinsekvo uzante la funkcion “ ordigi ( inversa = Vera ) ”.
Tempoloko Bobelo O(n) O(n2) O(n2) O(1) Jes Jes Enmeta ordigo O(n) O(n2) O(n2) O(1) Jes Jes Rapida ordigo O(n log(n)) O(n log(n)) O(n2) O(N) Ne Jes Kunfandi ordigi O(n log(n)) O(n log(n)) O(n log(n)) O(N) Jes Ne Heap sort O(n log (n)) O(n log(n)) O(n log(n)) O(1) Ne Jes
En la supra kompara tabelo " O " estas la Granda Oh-notacio klarigita supre dum " n " kaj " N " signifas la grandecon de la enigo .
Oftaj Demandoj
Q #1) Kio estas ordigo () en Python?
Respondo: En Python sort() estas funkcio kiu estas uzata por ordigi la listojn aŭ tabelojn en specifa ordo. Ĉi tiu funkcio faciligas la procezon de ordigo dum laboro pri la grandaj projektoj. Ĝi estas tre helpema por la programistoj.
Q #2) Kiel vi ordigas en Python?
Respondo: Python provizas diversajn ordigajn teknikojn, kiuj estas uzataj por ordigi la elementon. Ekzemple, Rapida ordigo, Kunfana ordigo, Vezika ordigo, Enmeta ordigo ktp. Ĉiuj ordigaj teknikoj estas efikaj kaj facile kompreneblaj.
Q #3) Kiel Python funkcias ordigi () labori?
Respondo: La sorto()funkcio prenas la donitan tabelon kiel enigaĵon de la uzanto kaj ordigas ĝin en specifa sinsekvo uzante la ordigan algoritmon. La elekto de la algoritmo dependas de la elekto de la uzanto. Uzantoj povas uzi Rapidan ordigon, Kunfandi ordigon, Vezikan ordigon, Enmeta ordigon ktp depende de la bezonoj de la uzanto.
Konkludo
En la ĉi-supra lernilo, ni diskutis la ordigan teknikon en Python kune kun la ĝeneralaj ordigaj teknikoj.
- Bobla Ordigo
- Enmeta Ordigo
- Rapida Ordigo
Ni lernis pri iliaj tempokompleksaĵoj kaj avantaĝoj & malavantaĝoj. Ni ankaŭ komparis ĉiujn ĉi-suprajn teknikojn.
Komplekseco de Ordigo-AlgoritmojTempo Komplekseco estas la kvanto da tempo bezonata de la komputilo por ruli apartan algoritmon. Ĝi havas tri specojn de tempokompleksaj kazoj.
- Plej malbonaj kazoj: Maksimuma tempo okupata de la komputilo por ruli la programon.
- Averaĝa Kazo: Tempo bezonata inter la minimumo kaj maksimumo de la komputilo por ruli la programon.
- Plej bona kazo: Minimuma tempo necesa de la komputilo por ruli la programon. Ĝi estas la plej bona kazo de tempokomplekseco.
Kompleksaj notacioj
Granda Oh Notacio, O: Granda o-notacio estas la oficiala maniero transdoni la supran baron de rultempo de la algoritmoj. Ĝi estas uzata por mezuri la plej malbonan tempan kompleksecon aŭ ni diras la plej grandan kvanton da tempo bezonata de la algoritmo por kompletigi.
Granda omega notacio, : Granda omega notacio estas la oficiala maniero transdoni la plej malsupran limon de la rultempo de la algoritmoj. Ĝi estas uzata por mezuri plejbonkazan tempokompleksecon aŭ ni diras la bonegan tempon prenitan de la algoritmo.
Theta Notation, : Theta-notacio estas la oficiala maniero transdoni ambaŭ limoj t.e. malsupra kaj supera de la tempo bezonata de la algoritmo por kompletigi.
Ordigo-Metodoj en Python
Vezika ordigo
Vezika ordigo estas la plej simpla maniero por ordigi la datumojn kiu uzas la krudfortan teknikon. Ĝi ripetos al ĉiu datenelemento kaj komparos ĝin kun aliaj elementojpor provizi la uzanton per la ordigitaj datumoj.
Ni prenu ekzemplon por kompreni ĉi tiun teknikon:
- Ni estas provizitaj per tabelo havanta la elementojn “ 10, 40, 7, 3, 15”. Nun, ni devas aranĝi ĉi tiun tabelon en suprena ordo uzante la Bubble-ordigan teknikon en Python.
- La unua paŝo estas aranĝi la tabelon en la donita ordo.
- En la “ Iteracio 1 ”, ni komparas la unuan elementon de tabelo kun la aliaj elementoj unuope.
- La ruĝaj sagoj priskribas la komparon de la unuaj elementoj kun la aliaj elementoj de tabelo.
- Se vi rimarkas, ke "10" estas pli malgranda ol "40", do, ĝi restas egala. loko sed la sekva elemento " 7 " estas pli malgranda ol " 10 ". Tial ĝi estas anstataŭigita kaj venas al la unua loko.
- La ĉi-supra procezo estos farita denove kaj denove por ordigi la elementojn.
-
- En la “Iteracio 2” la dua elemento estas komparita kun la aliaj elementoj de tabelo.
- Se la komparita elemento estas malgranda tiam, ĝi estos estu anstataŭigita, alie ĝi restos en la sama loko.
-
- En “ Iteracio 3 “ la tria elemento estas komparata kun la aliaj elementoj de tabelo.
-
- En la lasta " Iteracio 4 " la dua lasta elemento estas komparita kun la aliaj elementoj de tabelo.
- Enĉi tiu paŝo la tabelo estas ordigita en la suprena ordo.
Programo por Bubble-ordigo
``` 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)) ```
Eligo
Tempokomplekseco de Vezika sorto
- Plej malbona kazo: La plej malbona tempokomplekseco por bobelspeco estas O( n 2).
- Averaĝa Kazo: La averaĝa tempokomplekseco por bobelspeco estas O( n 2).
- Plej bona kazo: La plej bona tempokomplekseco por bobelspeco estas O(n).
Avantaĝoj
- Ĝi estas plejparte uzata kaj estas facile efektivigebla.
- Ni povas interŝanĝi la datumelementojn sen konsumo de mallongdaŭra konservado.
- Ĝi postulas malpli. spaco.
Malavantaĝoj
- Ĝi ne bone funkciis dum traktado de granda nombro da grandaj datenelementoj.
- Ĝi bezonas n 2 paŝojn por ĉiu “n” nombro da datumelementoj por ordigi.
- Ĝi ne estas vere bona por realaj aplikoj.
Enmeto Ordigi
Enmeta ordigo estas facila kaj simpla ordiga tekniko, kiu funkcias simile al ordigo de la ludkartoj. Enmeta ordigo ordigas la elementojn komparante ĉiun elementon unu post alia kun la alia. La elementoj estas elektitaj kaj interŝanĝitaj kun la alia elemento se la elemento estas pli granda aŭ pli malgranda ol la alia.
Ni prenu ekzemplon
- Ni estas provizitaj per tabelo havanta la elementojn “ 100, 50, 30, 40, 10 ” .
- Unue, ni aranĝas la tabelon kaj komencas kompariĝi.
- En la unua paŝo “ 100 ” estas komparata kun la dua elemento “ 50 ”. “ 50 ” estas interŝanĝita kun “ 100 ” ĉar ĝi estas pli granda.
- En la dua paŝo, denove la dua elemento “100 ” estas komparata kun la tria elemento “30 ” kaj estas interŝanĝita.
- Nun, se vi rimarkas, ke "30" venas al la unua loko ĉar ĝi estas denove pli malgranda ol "50".
- La komparo okazos ĝis la lasta elemento de tabelo kaj fine, ni ricevos la ordigitaj datumoj.
Programo por Enmeta ordigo
``` 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]) ```
Eligo
Tempokomplekseco de Enmeta ordigo
- Plej malbona kazo: La plej malbona tempokomplekseco por Enmeta ordigo estas O( n 2).
- Averaĝa Kazo: La averaĝa tempokomplekseco por Enmeta varo estas O( n 2).
- Plej bona kazo: La plej bona tempokomplekseco por Enmeta ordigo estas O(n).
Avantaĝoj
- Ĝi estas simpla kaj facile efektivigebla.
- Ĝi funkcias bone dum traktado de malgranda nombro da datumelementoj.
- Ĝi ne bezonas pli da spaco por sia efektivigo.
Malavantaĝoj
- Ne utilas ordigi grandegan nombron da datenelementoj.
- Kompare kun aliaj ordigaj teknikoj ĝi ne funkcias bone.
Kunfandi ordi
Ĉi tiu ordiga metodo uzas la metodon dividi kaj konkeri por ordigi la elementojn en specifa ordo. Dum ordigo helpe de merge sort, laelementoj estas dividitaj en duonojn kaj poste, ili estas ordigitaj. Post ordigo de ĉiuj duonoj, denove la elementoj kuniĝas por formi perfektan ordon.
Ni prenu ekzemplon por kompreni ĉi tiun teknikon
- Ni estas provizitaj per tabelo " 7, 3, 40, 10, 20, 15, 6, 5 ". La tabelo enhavas 7 elementojn. Se ni dividas ĝin en duonon ( 0 + 7 / 2 = 3 ).
- En la dua paŝo, vi vidos, ke la elementoj estas dividitaj en du partojn. Ĉiu havante 4 elementojn en ĝi.
- Plue, la elementoj denove estas dividitaj kaj havas po 2 elementojn.
- Ĉi tiu procezo daŭros ĝis nur unu elemento ĉeestas en tabelo. Vidu al paŝo n-ro. 4 en la bildo.
- Nun ni ordigos la elementojn kaj komencos kunigi ilin kiel ni estis dividitaj.
- En la paŝo n-ro. 5 se vi rimarkas, ke 7 estas pli granda ol 3, do ni interŝanĝos ilin kaj aliĝos al ĝi en la sekva paŝo kaj inverse.
- Fine, vi rimarkos, ke nia tabelo estas ordigita en kreskanta ordo.
Programo por Kunfanda ordigo
``` 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) ```
Eligo
Tempa komplekseco de kunfanda ordigo
- Plej malbona kazo: La plej malbona tempokomplekseco por kunfanda ordigo estas O( n log( n )).
- Averaĝa Kazo: La meza tempokomplekseco por kunfanda ordigo estas O( n log( n )).
- Plej bona kazo: La plej bona tempokomplekseco por kunfanda ordigo estas O( n log( n )).
Avantaĝoj
- La dosiergrandeco ne gravas por ĉi tiu ordiga tekniko.
- Tiu ĉi tekniko estas bona por la datumoj, kiuj estas ĝenerale alireblaj en sinsekvo. Ekzemple ligitaj listoj, bendodisko, ktp.
Malavantaĝoj
- Ĝi postulas pli da spaco kompare kun aliaj ordigaj teknikoj.
- Ĝi estas kompare malpli efika ol aliaj.
Rapida ordigo
Rapida ordigo denove uzas la metodon dividi kaj konkeri por ordigi la elementojn de Listo. aŭ tabelo. Ĝi celas la pivotelementojn kaj ordigas la elementojn laŭ la elektita pivotelemento.
Ekzemple
- Ni estas provizitaj per tabelo havanta la elementojn “ 1 ,8,3,9,4,5,7 ”.
- Ni supozu “7” kiel pilota elemento.
- Nun ni dividos la tabelon tiel, ke la maldekstra flanko enhavas la elementojn kiuj estas pli malgrandaj ol la pivotelemento " 7 " kaj la dekstra flanko enhavas la elementojn pli grandajn ol la pivotelemento " 7 ".
- Ni nun havas du tabelojn " 1,3,4,5 ". ” kaj “ 8, 9 ” .
- Denove, ni devas dividi ambaŭ tabelojn same kiel ni faris supre. La nura diferenco estas, ke la pivotelementoj estas ŝanĝitaj.
- Ni devas dividi la tabelojn ĝis ni ricevos la ununuran elementon en la tabelo.
- Fine, kolektu ĉiujn pivotajn elementojn en aro. sekvenco de maldekstre dekstren kaj vi ricevos la ordigitantabelo.
Programo por Rapida ordigo
``` 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 ] ) ```
Eligo
Tempokomplekseco de Rapida ordigo
- Plej malbona kazo: La plej malbona tempokomplekseco por Rapida ordigo estas O( n 2).
- Averaĝa Kazo: La meza tempokomplekseco por Rapida ordigo estas O( n log( n ) ).
- Plej bona kazo: La plej bona tempokomplekseco por Rapida ordigo estas O( n log( n )).
Avantaĝoj
- Ĝi estas konata kiel la plej bona ordiga algoritmo en Python.
- Ĝi estas utila dum traktado de granda kvanto da datumoj.
- Ĝi ne postulas plian spacon.
Malavantaĝoj
- Ĝia plej malbona kaza komplekseco similas al la kompleksecoj de bobelspeco kaj enmeta ordigo.
- Ĉi tiu ordiga metodo ne utilas kiam ni jam havas la ordigitan liston.
Heap sort
Heap sort estas la altnivela versio de Binara serĉarbo . En amasa ordigo, la plej granda elemento de tabelo estas metita sur la radikon de la arbo ĉiam kaj poste, kompare kun la radiko kun la folinodoj.
Ekzemple:
- Ni estas provizitaj per tabelo havanta la elementojn “ 40, 100, 30, 50, 10 ” .
- En “ paŝo 1 ” ni faris arbon laŭ la ĉeesto de la elementoj en la tabelo.
- En “ paŝo 2 ” ni faras maksimuman amason t.e. por aranĝi la elementoj en la malkreskanta ordo. La plej granda elemento vololoĝas ĉe la supro (radiko) kaj la plej malgranda elemento loĝas ĉe la malsupro (folionodoj). La donita tabelo fariĝas " 100, 50, 30, 40, 10 ".
- En “ paŝo 3 ” , ni faras la minimuman amason por ke ni povu trovi la minimumajn elementojn de tabelo. Farante tion, ni ricevas la maksimumajn kaj la minimumajn elementojn.
- En “ paŝo 4 ” plenumante la samajn paŝojn. ni ricevas la ordigitan tabelon.
Programo por 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 ] ) ```
Eligo
Tempokomplekseco de Heap-speco
- Plej malbona kazo: La plej malbona tempokomplekseco por Heap-ordigo estas O( n log( n )).
- Averaĝa Kazo: La meza tempokomplekseco por Heap-ordigo estas O( n log( n )).
- Plej bona kazo: La plej bona tempokomplekseco por Heap-ordigo estasO( n log( n )).
Avantaĝoj
- Ĝi estas plejparte uzata pro sia produktiveco.
- Ĝi povas esti efektivigita kiel surloka algoritmo.
- Ĝi ne postulas grandan stokadon.
Malavantaĝoj
- Bezonas spacon por ordigante la elementojn.
- Ĝi faras la arbon por ordigi la elementojn.
Komparo Inter la Ordigaj Teknikoj
Ordmetodo | Plejbonkaza tempokomplekseco | Averaĝa kaztempokomplekseco | Malbonkaza tempokomplekseco | Spaca komplekseco | Stabileco | En - |
---|