Implementierungen von Sortieralgorithmen in Python

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 Unterteil enthält nur das erste Element zu Beginn der Sortierung process. Wir nehmen ein Element aus dem unsortierten Array und platzieren es an der richtigen Position im sortierten Unterarray.

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).
• iterate über das angegebene Array vom zweiten Element.
  • Nehmen Sie die aktuelle Position und das aktuelle Element in zwei Variablen.
  • Schreiben Sie eine Schleife, die iteriertates, bis das erste Element des Arrays oder das Element auftritt, das kleiner als das aktuelle Element ist.
    • Update das aktuelle Element mit dem previous 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ändnisanding.

Sehen wir uns die Schritte zur Implementierung des Auswahl sortieren.

• Initialisieren Sie das Array mit Dummy-Daten (Ganzzahlen).
• iterate über das angegebene Array.
  • Behalten Sie den Index des minimalen Elements bei.
  • Schreiben Sie eine Schleife, die iteriertates vom aktuellen Element bis zum letzten Element.
    • Ü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))

Bubble Sortieren

Bubble sort ist ein einfacher Algorithmus. Es tauscht die benachbarten Elemente bei jeder Iterationswiederholung ausatedly, bis das angegebene Array sortiert ist.

Es iteriertates ü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 bubble sortieren visuellally. Sehen wir sie uns an.

Sehen wir uns die Schritte zur Implementierung des bubble sortieren.

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

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

Sie können das ganz einfach umsetzen bubble Jetzt sortieren. Schauen wir uns den Code an.

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 effizienter als das prevAlgorithmen werden im Hinblick auf die Zeitkomplexität vielfach diskutiert. Es folgt dem Divide-and-Conquers-Ansatz.

Der Merge-Sort-Algorithmus teilt das Array in zwei Hälften und sortiert sie getrenntately. Nach dem Sortieren der beiden Hälften des Arrays 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.
  • iterate ü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 gre istater größer oder gleich dem rechten Index, dann zurückgeben.
  • 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))

Schlussfolgerung

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 🙂 👨‍💻