Python Sort: Sorteringsmetoder och algoritmer i Python

Python Sort
Sorteringsmetoder i Python
Ofta ställda frågor
Slutsats

Lär dig hur du använder Pythons funktion Sort för att sortera listor, matriser, ordlistor osv. med hjälp av olika sorteringsmetoder och algoritmer i Python:

Sortering är en teknik som används för att sortera data i en ordningsföljd, antingen i stigande eller fallande ordning.

Oftast är uppgifterna i stora projekt inte ordnade i rätt ordning, vilket skapar problem när man ska få tillgång till och hämta de nödvändiga uppgifterna på ett effektivt sätt.

Sorteringstekniker används för att lösa detta problem. Python tillhandahåller olika sorteringstekniker. till exempel, Bubbelsortering, insättningssortering, sammanslagningssortering, kvicksortering osv.

I den här handledningen kommer vi att förstå hur sortering fungerar i Python med hjälp av olika algoritmer.

Python Sort

Syntax för Python Sort

För att utföra sortering tillhandahåller Python en inbyggd funktion, dvs. funktionen " sort() ". Den används för att sortera dataelementen i en lista i stigande eller fallande ordning.

Låt oss förstå detta koncept med ett exempel.

Exempel 1:

 ```` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( " Lista i stigande ordning: ", a ) ````

Utgång:

I det här exemplet sorteras den oordnade listan i stigande ordning med hjälp av funktionen " sort( ) ".

Exempel 2:

 ```` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( " Lista i fallande ordning: ", a ) ````

Utgång

I exemplet ovan sorteras den oordnade listan i omvänd ordning med hjälp av funktionen " sort( reverse = True ) ".

Tidskomplexitet för sorteringsalgoritmer

Tidskomplexitet är den tid som datorn behöver för att köra en viss algoritm. Det finns tre typer av tidskomplexitetsfall.

Det värsta fallet: Maximal tid som datorn behöver för att köra programmet.
Genomsnittligt fall: Den tid som datorn behöver för att köra programmet mellan minimum och maximum.
Bästa fall: Minsta tid som datorn behöver för att köra programmet. Det är det bästa fallet av tidskomplexitet.

Notationer för komplexitet

Big Oh Notation, O: Big oh-notationen är det officiella sättet att ange den övre gränsen för algoritmernas körtid. Den används för att mäta den värsta tidskomplexiteten, dvs. den längsta tid det tar för algoritmen att slutföra.

Big omega Notation, : Big omega-notationen är det officiella sättet att förmedla den lägsta gränsen för algoritmernas körtid. Den används för att mäta tidskomplexiteten i bästa fall, dvs. den utmärkta tid som algoritmen tar i anspråk.

Theta-notation, : Theta-notationen är det officiella sättet att uttrycka båda gränserna, dvs. den nedre och övre gränsen för den tid som algoritmen tar för att slutföra.

Sorteringsmetoder i Python

Sortering av bubblor

Bubbelsortering är det enklaste sättet att sortera data med hjälp av brute force-teknik. Den itererar varje dataelement och jämför det med andra element för att ge användaren sorterade data.

Låt oss ta ett exempel för att förstå denna teknik:

Vi får en matris med elementen " 10, 40, 7, 3, 15 ". Nu måste vi ordna matrisen i stigande ordning med hjälp av bubbelsorteringstekniken i Python.
- Det allra första steget är att ordna matrisen i den givna ordningen.
- I " Iteration 1 " jämför vi det första elementet i en array med de andra elementen ett efter ett.
- De röda pilarna beskriver jämförelsen av de första elementen med de andra elementen i en matris.
- Om du märker att "10" är mindre än "40" så förblir det på samma plats, men nästa element "7" är mindre än "10", vilket innebär att det ersätts och hamnar på första plats.
- Ovanstående process kommer att utföras om och om igen för att sortera elementen.

- I " Iteration 2 " jämförs det andra elementet med de andra elementen i en array.
- Om det jämförda elementet är litet kommer det att bytas ut, annars kommer det att vara kvar på samma plats.

- I " Iteration 3 " jämförs det tredje elementet med de andra elementen i en array.

- I den sista " Iteration 4 " jämförs det näst sista elementet med de andra elementen i en array.
- I detta steg sorteras matrisen i stigande ordning.

Program för bubbelsortering

 ```` 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 unsorted_list = [5, 3, 8, 6, 7, 2] print("Osorterad lista: ", unsorted_list) print("Sorterad lista med hjälp av Bubble SortTeknik: ", Bubble_Sort(unsorted_list)) ````

Utgång

Tidskomplexitet för bubbelsortering

Det värsta fallet: Den värsta tidskomplexiteten för bubbelsortering är O( n 2).
Genomsnittligt fall: Den genomsnittliga tidskomplexiteten för bubbelsortering är O( n 2).
Bästa fall: Den bästa tidskomplexiteten för bubbelsortering är O(n).

Fördelar

Den används oftast och är lätt att genomföra.
Vi kan byta ut dataelement utan att använda korttidslager.
Det kräver mindre utrymme.

Nackdelar

Det fungerade inte bra när det gällde ett stort antal stora dataelement.
Den behöver n 2 steg för varje "n" antal dataelement som ska sorteras.
Den är inte riktigt bra för verkliga tillämpningar.

Insättning Sortering

Insättningssortering är en lätt och enkel sorteringsteknik som fungerar på samma sätt som att sortera spelkort. Insättningssortering sorterar elementen genom att jämföra varje element ett och ett med det andra. Elementen plockas och byts ut mot det andra elementet om elementet är större eller mindre än det andra.

Låt oss ta ett exempel

Vi har en matris med elementen " 100, 50, 30, 40, 10 ".
Först ordnar vi arrayen och börjar jämföra den.
I det första steget jämförs " 100 " med det andra elementet " 50 ". " 50 " byts ut mot " 100 " eftersom det är större.
I det andra steget jämförs återigen det andra elementet " 100 " med det tredje elementet " 30 " och byts ut.
Om du ser att "30" kommer på första plats eftersom det är mindre än "50".
Jämförelsen sker fram till det sista elementet i en array och i slutet får vi de sorterade uppgifterna.

Program för sortering av inlagor

 ```` 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("Den osorterade matrisen: ", array) InsertionSort(array) print ("Den sorterade matrisen med hjälp av Insertion Sort: ") for i in range(len(array)): print (array[i]) ````

Utgång

Tidskomplexitet för insättningssortering

Det värsta fallet: Den värsta tidskomplexiteten för Insertion sort är O( n 2).
Genomsnittligt fall: Den genomsnittliga tidskomplexiteten för Insertion sort är O( n 2).
Bästa fall: Den bästa tidskomplexiteten för Insertion sort är O(n).

Fördelar

Det är enkelt och lätt att genomföra.
Det fungerar bra när det gäller ett litet antal dataelement.
Den behöver inte mer utrymme för sitt genomförande.

Nackdelar

Det hjälper inte att sortera ett stort antal dataelement.
Jämfört med andra sorteringsmetoder är den inte särskilt effektiv.

Sammanslagning av sortering

Den här sorteringsmetoden använder metoden dela och härska för att sortera elementen i en viss ordning. Vid sortering med hjälp av sammanslagningssortering delas elementen upp i halvor och sorteras sedan. När alla halvor har sorterats sammanfogas elementen igen för att bilda en perfekt ordning.

Låt oss ta ett exempel för att förstå denna teknik

Vi har en matris med 7, 3, 40, 10, 20, 15, 6, 5. Matrisen innehåller 7 element. Om vi delar den till hälften ( 0 + 7 / 2 = 3 ).
I det andra steget ser du att elementen är uppdelade i två delar som vardera har fyra element.
Elementen är återigen uppdelade och har två element vardera.
Denna process fortsätter tills det bara finns ett element i matrisen. Se steg 4 i bilden.
Nu ska vi sortera elementen och börja sammanfoga dem på samma sätt som vi delade upp dem.
I steg 5 märker du att 7 är större än 3, så vi byter ut dem och lägger ihop dem i nästa steg och vice versa.
I slutet kommer du att märka att vår array sorteras i stigande ordning.

Program för sammanslagningssortering

 ```` 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 inrange(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Givet array är", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sorterat array är: ", end="\n") PrintSortedList(arr) ````

Utgång

Tidskomplexitet för sammanslagningssortering

Det värsta fallet: Den värsta tidskomplexiteten för sammanslagningssortering är O( n log( n )).
Genomsnittligt fall: Den genomsnittliga tidskomplexiteten för sammanslagningssortering är O( n log( n )).
Bästa fall: Den bästa tidskomplexiteten för sammanslagningssortering är O( n log( n )).

Fördelar

Filstorleken spelar ingen roll för denna sorteringsteknik.
Den här tekniken är bra för data som i allmänhet hämtas i en ordningsföljd. Till exempel, länkade listor, bandspelare osv.

Nackdelar

Den kräver mer utrymme jämfört med andra sorteringsmetoder.
Den är relativt sett mindre effektiv än andra.

Snabbsortering

Snabbsortering använder återigen metoden dela och härska för att sortera elementen i en lista eller en matris. Den riktar in sig på pivotelementen och sorterar elementen i enlighet med det valda pivotelementet.

Till exempel

Vi får en matris med elementen " 1,8,3,9,4,5,7 ".
Låt oss anta att " 7 " är ett pilotelement.
Nu ska vi dela upp matrisen så att den vänstra sidan innehåller de element som är mindre än pivotelementet " 7 " och den högra sidan innehåller de element som är större än pivotelementet " 7 ".
Vi har nu två matriser " 1,3,4,5 " och " 8, 9 ".
Återigen måste vi dela upp de båda matriserna på samma sätt som vi gjorde ovan. Den enda skillnaden är att pivotelementen ändras.
Vi måste dela upp matriserna tills vi får ett enda element i matrisen.
Samla i slutet alla pivotelement i en sekvens från vänster till höger och du får en sorterad matris.

Program för snabbsortering

 ```` 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 ] 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, lägsta, högsta ) QuickSort( arr, lägsta, pi-1 ) QuickSort( arr, pi+1, högsta ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Osorterad matris: ", arr ) QuickSort( arr, 0, n-1 ) print( " Sorterad matris med hjälp av Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ````

Utgång

Tidskomplexitet för snabbsortering

Det värsta fallet: Den värsta tidskomplexiteten för Quick sort är O( n 2).
Genomsnittligt fall: Den genomsnittliga tidskomplexiteten för Quick sort är O( n log( n )).
Bästa fall: Den bästa tidskomplexiteten för Quick sort är O( n log( n )).

Fördelar

Den är känd som den bästa sorteringsalgoritmen i Python.
Det är användbart när du hanterar stora mängder data.
Den kräver inget extra utrymme.

Nackdelar

Dess komplexitet i värsta fall liknar komplexiteten hos bubbelsortering och insättningssortering.
Den här sorteringsmetoden är inte användbar när vi redan har en sorterad lista.

Sortering i högar

Heap sort är en avancerad version av binärt sökträd. I heap sort placeras det största elementet i en matris alltid vid roten av trädet och sedan jämförs roten med bladnoderna.

Till exempel:

Vi har en matris med elementen " 40, 100, 30, 50, 10 ".
På " steg 1 " Vi skapade ett träd enligt närvaron av elementen i matrisen.

I " steg 2 " Vi gör en maximal hög, dvs. vi ordnar elementen i fallande ordning. Det största elementet kommer att ligga högst upp (roten) och det minsta elementet ligger längst ner (bladnoder). Den givna matrisen blir " 100, 50, 30, 40, 10 ".

På " steg 3 " Vi gör en minsta hög för att hitta de minsta elementen i en array. På så sätt får vi fram de största och minsta elementen.

På " steg 4 " Genom att utföra samma steg får vi den sorterade matrisen.

Program för sortering i högar

 ```` 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[ 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( " Den osorterade matrisen är: ", arr ) HeapSort( arr ) n = len( arr ) print( " Den sorterade matrisen som sorterats med hjälp av Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ````

Utgång

Tidskomplexitet för sortering av högar

Det värsta fallet: Den värsta tidskomplexiteten för Heap-sortering är O( n log( n )).
Genomsnittligt fall: Den genomsnittliga tidskomplexiteten för Heap-sortering är O( n log( n )).
Bästa fall: Den bästa tidskomplexiteten för Heap-sortering ärO( n log( n )).

Fördelar

Den används främst på grund av sin produktivitet.
Den kan implementeras som en algoritm som sker på plats.
Den kräver ingen stor lagringsutrymme.

Nackdelar

Behöver utrymme för att sortera elementen.
Den gör trädet för att sortera elementen.

Jämförelse mellan sorteringsmetoderna

Sorteringsmetod	Tidskomplexitet i bästa fall	Genomsnittlig tidskomplexitet för ett ärende	Tidskomplexitet i värsta fall	Rymdkomplexitet	Stabilitet	På - plats
Bubbelsortering	O(n)	O(n2)	O(n2)	O(1)	Ja	Ja
Sortering genom inskjutning	O(n)	O(n2)	O(n2)	O(1)	Ja	Ja
Snabbsortering	O(n log(n))	O(n log(n))	O(n2)	O(N)	Ingen	Ja
Sammanslagning av sortering	O(n log(n))	O(n log(n))	O(n log(n))	O(N)	Ja	Ingen
Sortering i högar	O(n log(n))	O(n log(n))	O(n log(n))	O(1)	Ingen	Ja

I jämförelsetabellen ovan är "O" den Big Oh-notation som förklaras ovan, medan "n" och "N" står för storleken på inmatningen.

Ofta ställda frågor

Fråga 1) Vad är sort () i Python?

Svar: I Python är sort() en funktion som används för att sortera listor eller matriser i en viss ordning. Den här funktionen underlättar sorteringen när man arbetar med stora projekt och är till stor hjälp för utvecklare.

F #2) Hur sorterar man i Python?

Svar: Python erbjuder olika sorteringstekniker som används för att sortera elementet. Till exempel, Snabbsortering, sammanslagningssortering, bubbelsortering, insättningssortering etc. Alla sorteringstekniker är effektiva och lätta att förstå.

F #3) Hur fungerar Python sort ()?

Svar: Funktionen sort() tar den givna matrisen som indata från användaren och sorterar den i en viss ordning med hjälp av sorteringsalgoritmen. Valet av algoritm beror på användarens val. Användaren kan använda snabbsortering, sammanslagningssortering, bubbelsortering, insättningssortering osv. beroende på användarens behov.

Slutsats

I ovanstående handledning diskuterade vi sorteringstekniken i Python tillsammans med allmänna sorteringstekniker.

Sortering av bubblor
Insättning Sortering
Snabbsortering

Vi lärde oss om deras tidskomplexitet, fördelar och nackdelar och jämförde alla dessa tekniker.