• Erledigen Sie die Anwendungssicherheit auf die richtige Weise! Erkennen, schützen, überwachen, beschleunigen und mehr…
  • Das Sortieren ist eine der am häufigsten verwendeten Funktionen in der Programmierung. Und es wird einige Zeit dauern, bis die Sortierung abgeschlossen ist, wenn wir nicht den richtigen Algorithmus verwendet haben.

    In diesem Artikel werden wir verschiedene Sortieralgorithmen diskutieren.

    Wir werden Sie bei jedem Schritt der Implementierung durch die verschiedenen Sortieralgorithmen führen. Der Implementierungsteil wird in sein Python. Sie können es einfach in eine beliebige Sprache konvertieren, sobald Sie den Algorithmus erhalten haben. Das ist die Frage der Sprachsyntax.

    In diesem Tutorial werden wir verschiedene Algorithmen vom schlechtesten zum besten sehen. Also mach dir keine Sorgen. Folgen Sie dem Artikel und implementieren Sie sie.

    Lassen Sie uns in die Sortieralgorithmen eintauchen.

    Sortieren durch Einfügen

    Die Einfügesortierung ist einer der einfachen Sortieralgorithmen. Es ist einfach zu implementieren. Das Sortieren eines Arrays kostet Sie mehr Zeit. In den meisten Fällen wird es nicht zum Sortieren nach größeren Arrays verwendet.

    Der Sortieren durch Einfügen Der Algorithmus verwaltet sortierte und unsortierte Unterteile im angegebenen Array.

    Der sortiert Der Unterteil enthält nur das erste Element zu Beginn des Sortiervorgangs. Wir werden ein Element aus dem unsortierten Array nehmen und es an der richtigen Position im sortierten Unterarray platzieren.

    Schauen wir uns die visuellen Illustrationen von an Sortieren durch Einfügen Schritt für Schritt mit einem Beispiel.

    Sehen wir uns die Schritte zur Implementierung des Sortieren durch Einfügen.

    • Initialisieren Sie das Array mit Dummy-Daten (Ganzzahlen).
    • Durchlaufen Sie das angegebene Array vom zweiten Element aus.
      • Nehmen Sie die aktuelle Position und das aktuelle Element in zwei Variablen.
      • Schreiben Sie eine Schleife, die iteriert, bis das erste Element des Arrays oder das Element auftritt, das kleiner als das aktuelle Element ist.
        • Aktualisieren Sie das aktuelle Element mit dem vorherigen Element.
        • Dekrement der aktuellen Position.
      • Hier muss die Schleife entweder den Anfang des Arrays erreichen oder ein kleineres Element als das aktuelle Element finden. Ersetzen Sie das aktuelle Positionselement durch das aktuelle Element.

    Die zeitliche Komplexität der Sortieren durch Einfügen is O (n ^ 2), und die Raumkomplexität wenn O (1).

    Das ist es; Wir haben das angegebene Array sortiert. Lassen Sie uns den folgenden Code ausführen. Ich hoffe du hast Python installiert, wenn nicht, schau dir das an Installationsanleitung. Alternativ können Sie eine verwenden Online-Python-Compiler.

    def insertion_sort(arr, n):
    	for i in range(1, n):
    
    		## current position and element
    		current_position = i
    		current_element = arr[i]
    
    		## iteratin until
    		### it reaches the first element or
    		### the current element is smaller than the previous element
    		while current_position > 0 and current_element <
    		 arr[current_position - 1]:
    			## updating the current element with previous element
    			arr[current_position] = arr[current_position - 1]
    
    			## moving to the previous position
    			current_position -= 1
    
    		## updating the current position element
    		arr[current_position] = current_element
    
    if __name__ == '__main__':
    	## array initialization
    	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
    	insertion_sort(arr, 9)
    
    	## printing the array
    	print(str(arr))

    Auswahl Sortieren

    Die Auswahlsortierung ähnelt der Einfügungssortierung mit einem geringfügigen Unterschied. Dieser Algorithmus unterteilt das Array auch in sortierte und unsortierte Unterteile. Und dann nehmen wir bei jeder Iteration das minimale Element aus dem unsortierter Unterteil und platzieren Sie es in der letzten Position des sortierter Unterteil.

    Lassen Sie uns Illustrationen von Auswahl sortieren zum besseren verständnis.

    Sehen wir uns die Schritte zur Implementierung des Auswahl sortieren.

    • Initialisieren Sie das Array mit Dummy-Daten (Ganzzahlen).
    • Iterieren Sie über das angegebene Array.
      • Behalten Sie den Index des minimalen Elements bei.
      • Schreiben Sie eine Schleife, die vom aktuellen Element zum letzten Element iteriert.
        • Überprüfen Sie, ob das aktuelle Element kleiner als das Mindestelement ist oder nicht.
        • Wenn das aktuelle Element kleiner als das minimale Element ist, ersetzen Sie den Index.
      • Wir haben den minimalen Elementindex bei uns. Tauschen Sie das aktuelle Element mithilfe der Indizes gegen das minimale Element aus.

    Die zeitliche Komplexität der Auswahl sortieren is O (n ^ 2), und die Raumkomplexität wenn O (1).

    Versuchen Sie, den Algorithmus zu implementieren, da er dem ähnlich ist Sortieren durch Einfügen. Sie können den Code unten sehen.

    def selection_sort(arr, n):
    	for i in range(n):
    
    		## to store the index of the minimum element
    		min_element_index = i
    		for j in range(i + 1, n):
    			## checking and replacing the minimum element index
    			if arr[j] < arr[min_element_index]:
    				min_element_index = j
    
    		## swaping the current element with minimum element
    		arr[i], arr[min_element_index] = arr[min_element_index], arr[i]
    
    if __name__ == '__main__':
    	## array initialization
    	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
    	selection_sort(arr, 9)
    
    	## printing the array
    	print(str(arr))

    Blasensortierung

    Die Blasensortierung ist ein einfacher Algorithmus. Es tauscht die benachbarten Elemente bei jeder Iteration wiederholt aus, bis das angegebene Array sortiert ist.

    Es iteriert über das Array und verschiebt das aktuelle Element an die nächste Position, bis es kleiner als das nächste Element ist.

    Abbildungen helfen uns das zu verstehen Blase sortieren visuell. Mal sehen.

    Sehen wir uns die Schritte zur Implementierung des Blase sortieren.

    1. Initialisieren Sie das Array mit Dummy-Daten (Ganzzahlen).
    2. Iterieren Sie über das angegebene Array.
      1. Iterieren von zu ni-1. Das Letzte i Elemente sind bereits sortiert.
        1. Überprüfen Sie, ob das aktuelle Element größer als das nächste Element ist oder nicht.
        2. Wenn das aktuelle Element größer als das nächste Element ist, tauschen Sie die beiden Elemente aus.

    Die zeitliche Komplexität der Blase sortieren is O (n ^ 2), und die Raumkomplexität wenn O (1).

    Sie können die Blasensortierung jetzt problemlos implementieren. Mal sehen, den Code.

    def bubble_sort(arr, n):
    	for i in range(n):
    		## iterating from 0 to n-i-1 as last i elements are already sorted
    		for j in range(n - i - 1):
    			## checking the next element
    			if arr[j] > arr[j + 1]:
    				## swapping the adjucent elements
    				arr[j], arr[j + 1] = arr[j + 1], arr[j]
    
    if __name__ == '__main__':
    	## array initialization
    	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
    	bubble_sort(arr, 9)
    
    	## printing the array
    	print(str(arr))

    Zusammenführen, sortieren

    Merge Sort ist ein rekursiver Algorithmus zum Sortieren des angegebenen Arrays. Es ist hinsichtlich der Zeitkomplexität effizienter als die zuvor diskutierten Algorithmen. Es folgt dem Divide and Conquers-Ansatz.

    Der Merge-Sortieralgorithmus unterteilt das Array in zwei Hälften und sortiert sie separat. Nachdem die beiden Hälften des Arrays sortiert wurden, werden sie zu einem einzigen sortierten Array zusammengeführt.

    Da es sich um einen rekursiven Algorithmus handelt, wird das Array so lange geteilt, bis das Array am einfachsten (Array mit einem Element) zu sortieren ist.

    Es ist Zeit für Illustration. Mal sehen.

    Sehen wir uns die Schritte zur Implementierung des Zusammenführen, sortieren.

    • Initialisieren Sie das Array mit Dummy-Daten (Ganzzahlen).
    • Schreiben Sie eine Funktion namens fusionieren um Unterarrays zu einem einzigen sortierten Array zusammenzuführen. Es akzeptiert die Argumente Array, linker, mittlerer und rechter Index.
      • Ermitteln Sie die Längen der Längen der linken und rechten Unterarrays anhand der angegebenen Indizes.
      • Kopieren Sie die Elemente aus dem Array in die entsprechenden linken und rechten Arrays.
      • Iterieren Sie über die beiden Sub-Arrays.
        • Vergleichen Sie die beiden Unterarray-Elemente.
        • Ersetzen Sie das Array-Element zum Sortieren durch das kleinere Element aus den beiden Unter-Arrays.
      • Überprüfen Sie, ob in beiden Sub-Arrays noch Elemente vorhanden sind.
      • Fügen Sie sie dem Array hinzu.
    • Schreiben Sie eine Funktion namens Zusammenführen, sortieren mit Parameterarray, linkem und rechtem Index.
      • Wenn der linke Index größer oder gleich dem rechten Index ist, kehren Sie zurück.
      • Suchen Sie den Mittelpunkt des Arrays, um das Array in zwei Hälften zu teilen.
      • Rufen Sie rekursiv die Zusammenführen, sortieren Verwenden Sie den linken, rechten und mittleren Index.
      • Führen Sie nach den rekursiven Aufrufen das Array mit dem zusammen fusionieren Funktion.

    Die zeitliche Komplexität der Zusammenführen, sortieren is O (nlogn), und die Raumkomplexität wenn O (1).

    Das war's für die Implementierung des Merge-Sort-Algorithmus. Überprüfen Sie den folgenden Code.

    def merge(arr, left_index, mid_index, right_index):
    	## left and right arrays
    	left_array = arr[left_index:mid_index+1]
    	right_array = arr[mid_index+1:right_index+1]
    
    	## getting the left and right array lengths
    	left_array_length = mid_index - left_index + 1
    	right_array_length = right_index - mid_index
    
    	## indexes for merging two arrays
    	i = j = 0
    
    	## index for array elements replacement
    	k = left_index
    
    	## iterating over the two sub-arrays
    	while i < left_array_length and j < right_array_length:
    
    		## comapring the elements from left and right arrays
    		if left_array[i] < right_array[j]:
    			arr[k] = left_array[i]
    			i += 1
    		else:
    			arr[k] = right_array[j]
    			j += 1
    		k += 1
    
    	## adding remaining elements from the left and right arrays
    	while i < left_array_length:
    		arr[k] = left_array[i]
    		i += 1
    		k += 1
    
    	while j < right_array_length:
    		j += 1
    		k += 1
    
    def merge_sort(arr, left_index, right_index):
    	## base case for recursive function
    	if left_index >= right_index:
    		return
    
    	## finding the middle index
    	mid_index = (left_index + right_index) // 2
    
    	## recursive calls
    	merge_sort(arr, left_index, mid_index)
    	merge_sort(arr, mid_index + 1, right_index)
    
    	## merging the two sub-arrays
    	merge(arr, left_index, mid_index, right_index)
    
    if __name__ == '__main__':
    	## array initialization
    	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
    	merge_sort(arr, 0, 8)
    
    	## printing the array
    	print(str(arr))

    Fazit

    Es gibt viele andere Sortieralgorithmen, aber oben sind einige der häufig verwendeten. Ich hoffe, Sie haben das Sortieren genossen.

    Als nächstes erfahren Sie mehr über Suchalgorithmen.

    Viel Spaß beim Programmieren 🙂 👨‍💻