Python Sorteren: Sorteermethoden en algoritmen in Python

Leer hoe u de Python Sort-functie kunt gebruiken voor het sorteren van lijsten, arrays, woordenboeken, enz. met behulp van verschillende sorteermethoden en algoritmen in Python:

Sorteren is een techniek die wordt gebruikt om de gegevens in een oplopende of aflopende volgorde te sorteren.

Meestal zijn de gegevens van de grote projecten niet in de juiste volgorde gerangschikt en dat levert problemen op bij het efficiënt opvragen van de vereiste gegevens.

Om dit probleem op te lossen worden sorteertechnieken gebruikt. Python biedt verschillende sorteertechnieken bijvoorbeeld, Bubble sort, Insertion sort, Merge sort, Quicksort, enz.

In deze tutorial zullen we begrijpen hoe sorteren in Python werkt met behulp van verschillende algoritmen.

Python Sorteren

Syntaxis van Python Sort

Om te sorteren biedt Python de ingebouwde functie "sort()", waarmee de gegevens van een lijst in oplopende of aflopende volgorde kunnen worden gesorteerd.

Laten we dit concept begrijpen aan de hand van een voorbeeld.

Voorbeeld 1:

 ``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( " Lijst in oplopende volgorde: ", a ) ``` 

Uitgang:

In dit voorbeeld wordt de gegeven ongeordende lijst oplopend gesorteerd met de functie " sort( ) ".

Voorbeeld 2:

 ``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( " Lijst in aflopende volgorde: ", a ) ``` 

Uitgang

In het bovenstaande voorbeeld wordt de gegeven ongeordende lijst in omgekeerde volgorde gesorteerd met de functie " sort( reverse = True ) ".

Tijdscomplexiteit van sorteeralgoritmen

Tijdscomplexiteit is de hoeveelheid tijd die de computer nodig heeft om een bepaald algoritme uit te voeren. Er zijn drie soorten gevallen van tijdscomplexiteit.

  • In het ergste geval: Maximale tijd die de computer nodig heeft om het programma uit te voeren.
  • Gemiddeld geval: De tijd die de computer nodig heeft om het programma uit te voeren.
  • Beste geval: De minimale tijd die de computer nodig heeft om het programma uit te voeren. Dit is het beste geval van tijdscomplexiteit.

Complexiteitsnotaties

Big Oh Notatie, O: De big oh-notatie is de officiële manier om de bovengrens van de looptijd van de algoritmen aan te geven. Zij wordt gebruikt om de worst-case tijdscomplexiteit te meten, ofwel de grootste hoeveelheid tijd die het algoritme nodig heeft om te voltooien.

Grote omega Notatie, : De grote omega-notatie is de officiële manier om de laagste limiet van de looptijd van algoritmen aan te geven. Zij wordt gebruikt om de best-case tijdscomplexiteit te meten oftewel de uitstekende hoeveelheid tijd die het algoritme nodig heeft.

Theta Notatie, : De theta-notatie is de officiële manier om beide grenzen aan te geven, namelijk de onder- en bovengrens van de tijd die het algoritme nodig heeft om te voltooien.

Sorteermethoden in Python

Bubbel Sorteren

Bubble sort is de eenvoudigste manier om de gegevens te sorteren, waarbij gebruik wordt gemaakt van de brute force techniek. Elk gegevenselement wordt doorlopen en vergeleken met andere elementen om de gebruiker de gesorteerde gegevens te geven.

Laten we een voorbeeld nemen om deze techniek te begrijpen:

  • We krijgen een array met de elementen " 10, 40, 7, 3, 15 ". Nu moeten we deze array rangschikken in oplopende volgorde met behulp van de Bubble sort techniek in Python.
    • De allereerste stap is het rangschikken van de array in de gegeven volgorde.
    • In de "Iteratie 1" vergelijken we het eerste element van een matrix met de andere elementen, één voor één.
    • De rode pijlen beschrijven de vergelijking van de eerste elementen met de andere elementen van een matrix.
    • Als u merkt dat " 10 " kleiner is dan " 40 " blijft het dus op dezelfde plaats, maar het volgende element " 7 " is kleiner dan " 10 ". Daarom wordt het vervangen en komt het op de eerste plaats.
    • Het bovenstaande proces wordt steeds opnieuw uitgevoerd om de elementen te sorteren.

    • In de "Iteratie 2" wordt het tweede element vergeleken met de andere elementen van een matrix.
    • Als het vergeleken element klein is, wordt het vervangen, anders blijft het op dezelfde plaats.

    • In "Iteratie 3" wordt het derde element vergeleken met de andere elementen van een matrix.

    • In de laatste " Iteratie 4 " wordt het voorlaatste element vergeleken met de andere elementen van een array.
    • In deze stap wordt de matrix oplopend gesorteerd.

Programma voor 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 SortTechniek: ", Bubble_Sort(unsorted_list)) ``` 

Uitgang

Tijdscomplexiteit van Bubble sort

  • In het ergste geval: De slechtste tijdscomplexiteit voor bubble sort is O( n 2).
  • Gemiddeld geval: De gemiddelde tijdscomplexiteit voor bubble sort is O( n 2).
  • Beste geval: De beste tijdscomplexiteit voor bubble sort is O(n).

Voordelen

  • Het wordt meestal gebruikt en is gemakkelijk te implementeren.
  • Wij kunnen de gegevenselementen verwisselen zonder verbruik van kortetermijnopslag.
  • Het vergt minder ruimte.

Nadelen

  • Het presteerde niet goed bij de behandeling van een groot aantal grote gegevenselementen.
  • Het moet n 2 stappen voor elk "n" aantal te sorteren gegevenselementen.
  • Het is niet echt goed voor echte toepassingen.

Invoegen Sorteren

Insertion sort is een gemakkelijke en eenvoudige sorteertechniek die werkt zoals het sorteren van speelkaarten. Insertion sort sorteert de elementen door elk element één voor één te vergelijken met het andere. De elementen worden gekozen en verwisseld met het andere element als het element groter of kleiner is dan het andere.

Laten we een voorbeeld nemen

  • Wij krijgen een matrix met de elementen " 100, 50, 30, 40, 10 ".
  • Eerst ordenen we de array en beginnen we met vergelijken.
  • In de eerste stap wordt " 100 " vergeleken met het tweede element " 50 ". " 50 " wordt verwisseld met " 100 " omdat het groter is.
  • In de tweede stap wordt opnieuw het tweede element " 100 " vergeleken met het derde element " 30 " en verwisseld.
  • Nu, als u merkt dat " 30 " op de eerste plaats komt omdat het weer kleiner is dan " 50 ".
  • De vergelijking vindt plaats tot het laatste element van een array en aan het eind krijgen we de gesorteerde gegevens.

Programma voor invoegen sorteren

 ``` def InsertionSort(array): voor 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("De ongesorteerde array: ", array) InsertionSort(array) print ("De gesorteerde array met behulp van de Insertion Sort: ") voor i in range(len(array)): print (array[i]) ``` 

Uitgang

Tijdscomplexiteit van inbrengsortering

  • In het ergste geval: De slechtste tijdscomplexiteit voor Insertion sort is O( n 2).
  • Gemiddeld geval: De gemiddelde tijdscomplexiteit voor Insertion sort is O( n 2).
  • Beste geval: De beste tijdscomplexiteit voor Insertion sort is O(n).

Voordelen

  • Het is eenvoudig en gemakkelijk uit te voeren.
  • Hij presteert goed bij een klein aantal gegevenselementen.
  • Het heeft niet meer ruimte nodig voor de uitvoering ervan.

Nadelen

  • Het is niet nuttig om een groot aantal gegevenselementen te sorteren.
  • In vergelijking met andere sorteertechnieken presteert hij niet goed.

Sorteren samenvoegen

Bij deze sorteermethode wordt de verdeel-en-heersmethode gebruikt om de elementen in een bepaalde volgorde te sorteren. Bij het sorteren met behulp van merge sort worden de elementen in helften verdeeld en vervolgens gesorteerd. Na het sorteren van alle helften worden de elementen weer samengevoegd tot een perfecte volgorde.

Laten we een voorbeeld nemen om deze techniek te begrijpen

  • We krijgen een matrix " 7, 3, 40, 10, 20, 15, 6, 5 ". De matrix bevat 7 elementen. Als we hem in tweeën delen ( 0 + 7 / 2 = 3 ).
  • In de tweede stap ziet u dat de elementen in twee delen zijn verdeeld, elk met 4 elementen erin.
  • Verder zijn de elementen opnieuw verdeeld en hebben ze elk 2 elementen.
  • Dit proces gaat door totdat er slechts één element in een array aanwezig is. Zie stap nr. 4 in de afbeelding.
  • Nu gaan we de elementen sorteren en beginnen ze samen te voegen zoals we verdeeld waren.
  • Als u in stap nr. 5 ziet dat 7 groter is dan 3, zullen we ze omwisselen en in de volgende stap samenvoegen en omgekeerd.
  • Aan het eind zul je zien dat onze matrix in oplopende volgorde wordt gesorteerd.

Programma voor samenvoegen

 ``` 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("Gegeven array is", end="\n") PrintSortedList(arr) MergeSort(arr) print("Gesorteerde array is: ", end="\n") PrintSortedList(arr) ``` 

Uitgang

Tijdscomplexiteit van samenvoegen

  • In het ergste geval: De slechtste tijdscomplexiteit voor merge sort is O( n log( n )).
  • Gemiddeld geval: De gemiddelde tijdscomplexiteit voor merge sort is O( n log( n )).
  • Het beste geval: De beste tijdscomplexiteit voor merge sort is O( n log( n )).

Voordelen

  • De bestandsgrootte doet er bij deze sorteertechniek niet toe.
  • Deze techniek is goed voor de gegevens die in het algemeen in volgorde worden opgevraagd. Bijvoorbeeld, linked lists, tape drive, etc.

Nadelen

  • Het vereist meer ruimte in vergelijking met andere sorteertechnieken.
  • Het is relatief minder efficiënt dan andere.

Snel sorteren

Snel sorteren gebruikt opnieuw de verdeel-en-heersmethode om de elementen van een Lijst of een matrix te sorteren. Het richt zich op de spilelementen en sorteert de elementen volgens het geselecteerde spilelement.

Bijvoorbeeld

  • We krijgen een matrix met de elementen " 1,8,3,9,4,5,7 ".
  • Laten we aannemen dat " 7 " een pilootelement is.
  • Nu zullen we de matrix zo verdelen dat de linkerkant de elementen bevat die kleiner zijn dan het spilelement " 7 " en de rechterkant de elementen die groter zijn dan het spilelement " 7 ".
  • We hebben nu twee matrices " 1,3,4,5 " en " 8, 9 ".
  • Opnieuw moeten we beide arrays op dezelfde manier verdelen als hierboven. Het enige verschil is dat de spilelementen worden gewijzigd.
  • We moeten de arrays verdelen tot we een enkel element in de array hebben.
  • Verzamel aan het eind alle spilelementen in een volgorde van links naar rechts en u krijgt de gesorteerde matrix.

Programma voor snelle sortering

 `` 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, laagste, hoogste ) QuickSort( arr, laagste, pi-1 ) QuickSort( arr, pi+1, hoogste ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Ongesorteerde array: ", arr ) QuickSort( arr, 0, n-1 ) print( " Gesorteerde array met behulp van Quick Sort: " ) voor i in range( n ): print( " %d " % arr[ i ] ) ```` 

Uitgang

Tijdscomplexiteit van Quick sort

  • In het ergste geval: De slechtste tijdscomplexiteit voor Quick sort is O( n 2).
  • Gemiddeld geval: De gemiddelde tijdscomplexiteit voor Quick sort is O( n log( n )).
  • Beste geval: De beste tijdscomplexiteit voor Quick sort is O( n log( n )).

Voordelen

  • Het staat bekend als het beste sorteeralgoritme in Python.
  • Het is nuttig bij het verwerken van grote hoeveelheden gegevens.
  • Het vereist geen extra ruimte.

Nadelen

  • De worst-case complexiteit is vergelijkbaar met die van bubble sort en insertion sort.
  • Deze sorteermethode is niet nuttig wanneer we de gesorteerde lijst al hebben.

Sorteren op hoop

Heap sort is de geavanceerde versie van Binary search tree. Bij heap sort wordt het grootste element van een array altijd op de wortel van de boom geplaatst en vervolgens vergeleken met de wortel met de bladknopen.

Bijvoorbeeld:

  • Wij krijgen een matrix met de elementen " 40, 100, 30, 50, 10 ".
  • In " stap 1 " maakten we een boom volgens de aanwezigheid van de elementen in de array.

  • In " stap 2 " We maken een maximale hoop, dat wil zeggen dat we de elementen in aflopende volgorde rangschikken. Het grootste element komt bovenaan (root) en het kleinste element onderaan (leaf nodes). De gegeven array wordt " 100, 50, 30, 40, 10 ".

  • In " stap 3 " maken we de minimale hoop zodat we de minimale elementen van een array kunnen vinden. Door dit te doen, krijgen we de maximale en minimale elementen.

  • In " stap 4 " door dezelfde stappen uit te voeren krijgen we de gesorteerde matrix.

Programma voor hoopsortering

 `` 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( " De ongesorteerde array is: ", arr ) HeapSort( arr ) n = len( arr ) print( " De gesorteerde array gesorteerd door de Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ``` 

Uitgang

Tijdscomplexiteit van Heap sort

  • In het ergste geval: De slechtste tijdscomplexiteit voor Heap sort is O( n log( n )).
  • Gemiddeld geval: De gemiddelde tijdscomplexiteit voor Heap sort is O( n log( n )).
  • Het beste geval: De beste tijdscomplexiteit voor Heap sort isO( n log( n )).

Voordelen

  • Het wordt meestal gebruikt vanwege zijn productiviteit.
  • Het kan worden uitgevoerd als een in-place algoritme.
  • Het vereist geen grote opslagruimte.

Nadelen

  • Heeft ruimte nodig om de elementen te sorteren.
  • Het maakt de boom voor het sorteren van de elementen.

Vergelijking tussen de sorteertechnieken

Sorteermethode Best case tijdscomplexiteit Gemiddelde tijd complexiteit zaak Worst case tijdscomplexiteit Complexiteit van de ruimte Stabiliteit In - plaats
Bellen sorteren O(n) O(n2) O(n2) O(1) Ja Ja
Invoegen sorteren O(n) O(n2) O(n2) O(1) Ja Ja
Snel sorteren O(n log(n)) O(n log(n)) O(n2) O(N) Geen Ja
Sorteren samenvoegen O(n log(n)) O(n log(n)) O(n log(n)) O(N) Ja Geen
Sorteren op hoop O(n log(n)) O(n log(n)) O(n log(n)) O(1) Geen Ja

In de bovenstaande vergelijkingstabel is "O" de Big Oh-notatie die hierboven is uitgelegd, terwijl "n" en "N" de grootte van de invoer betekenen.

Vaak gestelde vragen

Vraag 1) Wat is sort () in Python?

Antwoord: In Python is sort() een functie die wordt gebruikt om lijsten of arrays in een bepaalde volgorde te sorteren. Deze functie vergemakkelijkt het sorteren tijdens het werken aan grote projecten en is zeer nuttig voor ontwikkelaars.

Vraag 2) Hoe sorteer je in Python?

Antwoord: Python biedt verschillende sorteertechnieken die worden gebruikt om het element te sorteren. Bijvoorbeeld, Quick sort, Merge sort, Bubble sort, Insertion sort, enz. Alle sorteertechnieken zijn efficiënt en gemakkelijk te begrijpen.

V #3) Hoe werkt Python sort ()?

Antwoord: De functie sort() neemt de gegeven array als invoer van de gebruiker en sorteert deze in een specifieke volgorde met behulp van het sorteeralgoritme. De keuze van het algoritme hangt af van de keuze van de gebruiker. Gebruikers kunnen Quick sort, Merge sort, Bubble sort, Insertion sort, enz. gebruiken, afhankelijk van de behoeften van de gebruiker.

Conclusie

In de bovenstaande handleiding hebben we de sorteertechniek in Python besproken, samen met de algemene sorteertechnieken.

  • Bubbel Sorteren
  • Invoegen Sorteren
  • Snel sorteren

Wij leerden over hun tijdscomplexiteit en voordelen & nadelen. Wij vergeleken ook alle bovengenoemde technieken.

Scroll naar boven