Hey, also folgende Aufgabe ist gegeben. Ich habe nun als Ergebnis: Divide and Conquer QuickSort QuickSort mit zufälliger pivotwahl was sagt ihr? Gruß

Welcher Sortieralgorithmus wurde verwendet?

Bild zum Beitrag

Hey, also folgende Aufgabe ist gegeben. Ich habe nun als Ergebnis:

Divide and Conquer
QuickSort
QuickSort mit zufälliger pivotwahl

was sagt ihr?

Gruß

1 Antwort

daCypher

06.12.2023, 08:38

Divide and Conquer ist kein Sortieralgorithmus, sondern nur eine Strategie, die von verschiedenen Algorithmen (inklusive Quicksort) genutzt wird. Ich schätze mal, das erste ist ein Mergesort.

Deine anderen beiden Lösungen würde ich eher umdrehen. Beim rechten Algorithmus sieht man, dass der Pivot immer die letzte unsortierte Zahl ist (3, 4 , 7 , 6 , 2). Beim mittleren Algorithmus sehe ich keine Strategie zur Pivotwahl (3, 2, 4, 7, 5).

Wie kommt man darauf, was man in die Knoten schreiben muss?

Also warum ist bei Quicksort z. B. als erstes 1:3, dann drunter bei den Kinderknoten 2:3 und 2:3, also woher weiß ich, welche Sachen ich in die Knoten zu schreiben habe, also warum z. B. bei der Wurzel gerade 1:3 und nicht z. B. 1:2 oder so?

...zur Frage

Sortieralgorithmus Flussdiagramm?

Hallo,

ich habe versucht folgende Aufgabe mittels einem Flussdiagramm darzustellen und wollte mal nachfragen ob das so funktioniert:

"Nach Eingabe einer Liste[n], welche n Zahlen enthält, soll das Programm die Zahlen der Liste von Position 1 bis Position n aufsteigend sortieren und anschließend die sortierte Liste wieder ausgeben."

Ich habe den Bubble-Sort Algorithmus verwendet.

MMN kommt die Liste korrekt sortiert heraus. Liege ich da richtig oder ist mir bei zeichnen des Diagramms ein Fehler unterlaufen?

MFG

...zur Frage

Quicksort Pivotelement?

Der Quicksort wählt ja als erstes ein Pivotelement aus. Wie wählt er das Pivotelement aus? Ist das zufällig oder hat das irgendeinen Sinn?

Danke schonmal.

...zur Frage

quicksort knapp daneben?

ich hab dieses quicksort programmiert:

def quicksort2(a): # hoare
    
    if len(a) < 2:
        return a
    
    r1, r2 = 0, len(a)-1
    pivot = a[random.randint(0,r2)]
    
    while r1 < r2:
        while a[r1] < pivot and r1 < r2:
            r1 += 1
        
        while a[r2] > pivot and r1 < r2:
            r2 -= 1
        
        a[r1], a[r2] = a[r2], a[r1]
        r1,r2 = r1+1,r2-1
    
    return quicksort2(a[:r1]) + quicksort2(a[r1:])

und das Ergebnis ist fast richtig, lediglich werden manchmal Zahlen im Ergebnis vertauscht. Ich hab schon mehrere gefragt, was das Problem ist, aber nicht mal ein Informatiklehrer konnte mir helfen. Auch chatgpt hat nur Schmutz geliefert, und deswegen frag ich hier. Und falls ihr denkt, ihr habt es, probiert es erst aus, weil das jeder bisher meinte.

Danke im vorraus.

...zur Frage

Quicksort am effizientesten?

Warum ist Quicksort im Gegensatz zu Bubblesort und Minsort am effizientesten?

...zur Frage

C++ Umrechner ohne if, case Operatoren)?

Folgende Aufgabe: Gegeben seien 3 Berechnungsformeln für unterschiedliche Werte. Diese können z.B. ein Wechselkursrechner oder ein Rechner von Celcius zu Fahrenheit sein. Der Benutzer macht 2 Eingaben. 1. Eingabe ist der Wert der umgerechnet werden soll und der 2. Wert ist quasi der Auswahlwert (welcher auf bei if, else oder case verwendet werden könnte). Je nachdem ob ich 1, 2 oder 3, als Auswahlwert nehme, soll das Programm eine andere Umrechnungsformel nehmen.

Ich habe Tipps bekommen, mit denen man die Aufgabe eigentlich einfach lösen kann aber ich schaffe es einfach nicht und hänge hier seit Stunden rum. Ich bin froh Informatik bald abwählen zu können. Ich bitte um Hilfe. Es dürfen nur die Grundrechenart Operatoren verwendet werden.

Der Tipp bzw. Ansatz aus dem Internet:

Sei X die Auswahl den Benutzers und Y der umzurechnende Wert. Dann musst du in deinem Programm etwas haben, das ungefähr folgende Form hat:

ergebnis = f1(X)*Formel1(Y) + f2(X)*Formel2(Y) + f3(X)*Formel3(Y)

Jetzt musst du dir eine Funktion f1 ausdenken, die genau dann 1 ist, wenn X=1 ist, und 0 sonst. Ebenso muss f2 immer 0 sein außer bei X=2, usw.

...zur Frage

Quicksort oder Mergesort?

Wann würde man Quicksort oder Mergesort in der Praxis einsetzen?

...zur Frage

Optimaler Suchbaum Eigenschaften prüfen?

Hallo, ich habe folgende Aufgabe:

Gegeben sei der folgende Suchbaum, in dem die Elemente A;B;C;D;E

lexikographisch geordnet sind. Beweisen oder widerlegen Sie:

Der Baum kann ein optimaler Suchbaum mit 2,1 erwarteten Vergleichen sein.

Da kommen ich und viele andere nicht weiter, die meisten neigen zur Meinung, dass die Aussage falsch ist. Wir haben dazu sehr viele Gleichungen aufgestellt, die aber kompliziert zu lösen scheinen: (a bis e sind die jew. Zugriffswahrscheinlichkeiten)

a+b+c+d+e=1

a+2b+4c+3d+4e=2,1

Durch die e_ij Tabellen (erwartete Anzahl Vergleiche im Unterbaum von i bis j):

b<=a, e<=d<=c

Aber ich stecke jetzt fest wie ich hier wirklich weiterkomme. Muss ich etwa noch mehr Ungleichungen/Gleichungen aufstellen?

Vielen Dank im Voraus!

...zur Frage

Quicksort Algorithmus, Hilfe?

Irgendwie machen das alle anders. An meiner Uni wird das so gemacht:

Ich verstehe das nicht. Wenn die Zeiger übereinander laufen, dann kommt bei mir eine andere Zahlenfolge raus, als auf dem Bild. Außerdem weiß ich nicht, wie das Pivot in der Mitte platziert wurde.

Kann mir jemand bitte Schritt für Schritt erklären, wie hier gearbeitet wurde? Ich wäre so dankbar.

...zur Frage

Quicksort vs mergesort laufzeit?

Quicksort : worst case (n^2) , average case/best case (n log n) Mergesort : immer n log n

Ich versteh nicht wieso man sagt dass quicksort besser sein soll, wenn mergesort immer mindestens genau so schnell ist wie der best case von quicksort. Hat da jemand eine ahnung wann es sinn macht quicksort zu benutzen ?

...zur Frage

Kann man als Data-Scientist arbeiten, obwohl man diese Kenntnisse nicht hat?

Graphalgorithmen; Random access Maschine; Laufzeitermittlung; Breitenund Tiefensuche; Optimierung; Kürzeste Wege; Divide-and-conquer; Exponentielle Grundlegendes Verstehen der Problematik der Effizienz und Korrektheit von Algorithmen und darauf basierender Programme sowie ihrer Bedeutung in der Praxis

Automaten, Grammatiken, Chomsky Hierarchie, Turing Maschinen, NichtEntscheidbarkeit, NP-Vollständigkeit

...zur Frage

Hezadezimal in Dezimal umwandeln?

Hallo ,

ich bin bisschen am verzweifeln.
im Modul Informatik lernen wir die Zahlensysteme. Allerdings kann ich mir das ,,h“ nicht erklären.

folgende Aufgabe ist gegeben .

wandeln Sie folgende Zahlen vom hexadezimal in das Dezimalsystem um :

a) A1h

b) 34Ch

wofür steht das h ??

Danke schonmal

...zur Frage

Chemie: Siedetemperaturen?

Gegeben sind folgende Stoffe:

• 1,4-Dihydroxybenzol

• Methylbenzol/Toluol

• Phenol

Diese soll man nun nach Höhe der Siedetemperatur ordnen.

Wie gehe ich an die Aufgabe ran?

Wie lässt sich das Ergebnis erklären?

...zur Frage

Quicksort mit median pivotisierung?

Hey, ich habe den Quicksort Algorithmus folgendermaßen beschrieben bekommen:

Nun habe ich eine Methode lowerMedian(), die den Median einer Liste bestimmt. Wie genau muss ich diese Methode nun im Quicksort algorithmus einsetzen, damit dieser als Pivot Element immer den Median nimmt, die Laufzeit also O(log(n)) ist?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen