Python-Programm für Merge Sort

Als Multi-Paradigma-Programmiersprache mit einem strukturierten, objektorientierten Designansatz und einer einfachen und übersichtlichen Syntax und Grammatik entwickelt sich Python schnell zur Sprache der Wahl für Programmierer, die an Projekten unterschiedlicher Komplexität und Größe arbeiten.

Python bietet eine modulare Bibliothek vorgefertigter Algorithmen, die es seinen Benutzern ermöglicht, verschiedene Operationen durchzuführen, die ihnen helfen können, ihre Aufgabe an und für sich zu erfüllen, oder als Schritt auf dem Weg zum Erreichen eines größeren, komplexeren Ziels dienen. Einer der beliebtesten Algorithmen dieser Art ist einer, der die Merge-Sort-Funktionalität ermöglicht.

Was ist Merge Sort?

Es ist eine Allzweck-Sortiertechnik, die es Benutzern ermöglicht, einen zufälligen Datensatz jeder Art und aus jeder Quelle zu nehmen und ihn in sich wiederholende Phasen zu unterteilen, bis er schließlich in seine einzelnen Komponenten zerlegt wird – eine rekursive Technik, die allgemein als „ „Teile und herrsche“-Methode.

Der Algorithmus fügt dann die einzelnen Komponenten – wieder in sich wiederholenden Schritten – zusammen, sortiert sie aber auf jedem Schritt des Weges in eine vorher festgelegte, logische Reihenfolge, indem er den grundlegenden Vergleich und Austausch verwendet, bis die gesamte Datenreihe in der gewünschten logischen Reihenfolge wiederhergestellt ist .

Sehen Sie sich unsere anderen Data-Science-Kurse bei upGrad an.

Teile-und-herrsche-Technik

Nehmen Sie zum Beispiel einen zufälligen Datensatz von Buchstaben des Alphabets: N, H, V, B, Q, D, Z, R.

Schritt 1 : Der ursprüngliche Datensatz wird zunächst wie folgt in zwei Gruppen unterteilt:

N, H, V, B, Q, D, Z, R

Schritt 2 : Die beiden resultierenden Arrays werden wie folgt weiter unterteilt:

N, H V, B Q, D Z, R

Schritt 3 : Abschließend werden alle vier Arrays weiter ausgespuckt, bis die gesamte Datenreihe in ihre einzelnen Bestandteile zerlegt ist:

N H V B Q D Z R

Anschließend kehrt sich der Vorgang um und die einzelnen Datenpunkte beginnen nun schrittweise miteinander zu verschmelzen. Aber im Laufe dieses Zusammenführungsprozesses wird jedes Element in jedem Sub-Array bewertet und ausgetauscht, sodass sie sich in einer logischen Reihenfolge (alphabetische Reihenfolge) wie folgt sortieren:

Schritt 4 : Einzelne Elemente verschmelzen zu Paaren und tauschen nach Bedarf die Positionen, um die richtige Reihenfolge zu bilden:

H, N. B., V. D., Q. R., Z

Schritt 5 : Der rekursive Prozess des Zusammenführens und Sortierens wird mit der nächsten Iteration fortgesetzt:

B, H, N, V, D, Q, R, Z

Schritt 6 : Die gesamte Datenreihe wird schließlich in ihrer logischen alphabetischen Reihenfolge rekonstruiert:

B, D, H, N, Q, R, V, Z

Entdecken Sie unsere beliebten Data Science-Kurse

Merge-Sort-Implementierungen

Es gibt zwei Ansätze für die Implementierung von Merge Sort in Python. Der Top-Down-Ansatz und der Bottom-Up-Ansatz.

Top-Down-Ansatz:

Der häufiger verwendete Top-Down-Ansatz ist der oben beschriebene. Es dauert länger und verbraucht mehr Speicher und ist daher bei der Arbeit mit kleineren Datensätzen ineffizient. Es ist jedoch viel zuverlässiger, insbesondere wenn es auf große Datensätze angewendet wird.

Lesen Sie unsere beliebten Data Science-Artikel

Code eingeben:

def merge_sort (inp_arr):

Größe = Länge (inp_arr)

wenn Größe > 1:

Mitte = Größe // 2

left_arr = inp_arr(:middle)

right_arr = inp_arr(middle:)

merge_sort(left_arr)

merge _sort(right_arr)

ich = 0

j = 0

k = 0

(Wobei i und j die Iteratoren zum Durchlaufen der linken bzw. rechten Hälfte der Datenreihe sind und k der Iterator der gesamten Datenreihe ist).

left_size = len(left_arr)

right_size = len(right_arr)

während i < left_size und j < right size:

if left_arr(i) < right_arr (j):

inp_arr(k) – left_arr(i)

ich >= 1

anders:

inp_arr(k) = right_arr (j)

j + = 1

k+= 1

während ich < left_size:

inp_arr (k) = left_arr (i)

ich += 1

k+= 1

während j < right_size:

inp_arr (k) = rechts_arr (j)

j + = 1

k+= 1

inp_arr = (N, H, V, B, Q, D, Z, R)

print(:Eingabearray:\n”)

print(inp_arr)

merge_sort (inp_arr)

print("Sortiertes Array:\n")

drucken (inp_arr)

Ausgabe:

Eingangsarray: N, H, V, B, Q, D, Z, R

Ausgangsarray: B, D, H, N, Q, R, V, Z

Bottom-Up-Ansatz:

Der Bottom-up-Ansatz ist schneller, verbraucht weniger Speicher und arbeitet effizient mit kleineren Datasets, kann aber bei der Arbeit mit großen Datasets auf Probleme stoßen. Es wird daher seltener verwendet.

Code eingeben:

def merge(links, rechts):

Ergebnis = [] x, y = 0, 0

für k in range(0, len(links) + len(rechts)):

if i == len(left): # if am Ende der 1. Hälfte,

result.append(right[j]) # Addiere alle Werte der 2. Hälfte

j + = 1

elif j == len(right): # if am Ende der 2. Hälfte,

result.append(left[x]) # addiere alle Werte der 1. Hälfte

ich += 1

elif rechts[j] < links[i]:

result.append(right[j])

j + = 1

anders:

result.append(links[i])

ich += 1

Ergebnis zurückgeben

def mergesort(ar_list):

Länge = Länge (ar_list)

Größe = 1

während Größe < Länge:

size+=size # wird wie beschrieben bei 2 initialisiert

für pos in range(0, length, size):

Start = Pos

mid = pos + int (Größe / 2)

Ende = Position + Größe

left = ar_list[ start : mid ] right = ar_list[ mid : end ]

ar_list[start:end] = merge(links, rechts)

gib ar_list zurück

ar_list = [N, H, V, B, Q, D, Z, R] print(mergesort(ar_list))

Ausgabe:

Eingangsarray: N, H, V, B, Q, D, Z, R

Ausgangsarray: B, D, H, N, Q, R, V, Z

Die Merge-Sort-Implementierung wird auf komplexere, reale Datensätze angewendet

Wenden wir den Top-Down-Ansatz auf vier zufällige Geländewagen in Indien an:

Code eingeben:

Klasse Auto:

def __init__(selbst, Marke, Modell, Preis):

self.marke = Marke

self.model = Modell

self.price = Preis

def __str__(selbst):

return str.format("Marke: {}, Modell: {}, Preis: {}", self.brand,

selbst.Modell, selbst.Preis)

def merge(list1, i, j, k, comp_fun):

left_copy = list1[i:k + 1]

r_sublist = list1[k+1:r+1]

left_copy_index = 0

j_sublist_index = 0

sortierter_index = i

while left_copy_index < len(left_copy) undj_sublist_index <

len(j_sublist):

if comp_fun(left_copy[left_copy_index], j_sublist[j_sublist_index]):

list1[sortierter_index] = linke_kopie[linke_kopie_index]

left_copy_index = left_copy_index + 1

sonst :

list1[sortierter_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

Sortierindex = Sortierindex + 1

while left_copy_index < len(left_copy):

list1[sortierter_index] = linke_kopie[linke_kopie_index]

left_copy_index = left_copy_index + 1

Sortierindex = Sortierindex + 1

while j_sublist_index < len(j_sublist):

list1[sortierter_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

Sortierindex = Sortierindex + 1

def merge_sort(list1, i, j, comp_fun):

wenn i >= j:

Rückkehr

k = (i + j)//2

merge_sort(list1, i, k, comp_fun)

merge_sort(list1, k + 1, j, comp_fun)

merge(list1,i,j,k,comp_fun)

Auto1 = Auto("Jeep", "Wrangler", 0,58)

auto2 = Auto („Ford“, „Endeavour“, 0,35)

auto3 = Auto („Jaguar Land Rover“, „Range Rover Sport“, 1,76)

car4 = Auto („Mercedes Benz“, „G-Klasse“, 2.42)

list1 = [auto1, auto2, auto3, auto4]

merge_sort(list1, 0, len(list1) -1, lambda autoA, autoB: autoA.marke < autoB.marke)

drucken („Autos sortiert nach Marke:“)

für Auto inListe1:

Druck (Auto)

drucken ()

merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.price< carB.price)

print („Autos sortiert nach Preis:“)

für Auto inListe1:

Druck (Auto)

Ausgabe:

Autos sortiert nach Marke:

Ford Endeavor

Jaguar Land Rover Range Rover Sport

Jeep Wrangler

Mercedes Benz G-Klasse

Autos sortiert nach Preis:

Ford Endeavor

Jeep Wrangler

Jaguar Landrover Range Rover

Mercedes Benz G-Klasse

Mit dem Professional Certificate in Data Science and Business Analytics von upGrad der University of Maryland können Sie sowohl theoretische als auch praktische Aspekte von Python erlernen. Dieser Kurs hilft Ihnen, Python von Grund auf neu zu lernen. Auch wenn Sie neu im Programmieren und Programmieren sind, bietet Ihnen upGrad einen zweiwöchigen Vorbereitungskurs, damit Sie sich die Grundlagen des Programmierens aneignen können. Sie lernen verschiedene Tools wie Python, SQL kennen, während Sie an mehreren Branchenprojekten arbeiten.

Planen Sie jetzt Ihre Karriere als Softwareentwickler!

Bewerben Sie sich für das Professional Certificate Program in Data Science und Business Analytics