Was habe ich falsch gemacht bei diesem Quicksort- Algorithmus?

a)* Gegeben sei die Zahlenfolge:

8, 1, 7, 9, 5, 6, 3

Sortieren Sie die Zahlenfolge mit QuickSort,, wobei immer das letzte

Element einer Teilsequenz als Pivot zu verwenden ist. Eine Teilsequenz von maximal 2 Elementen soll in einem einzigen Schritt direkt ohne Pivotelement sortiert werden. Führen Sie den Algorithmus dabei von links nach rechts aus, d.h. beginnen Sie immer mit der linken Teilsequenz. Geben Sie die im Verlauf der

Sortierung genutzen Pivotelemente an.
Bei mir kommt als Ergebnis folgendes aber laut Musterlösung ist
3, 8, 5 (, 7)
richtig. Was habe ich denn da falsch gemacht?

Bild zum Beitrag

1 Antwort

Destranix

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Programmieren & Softwareentwicklung

30.09.2024, 15:09

Führen Sie den Algorithmus dabei von links nach rechts aus, d.h. beginnen Sie immer mit der linken Teilsequenz.

Hast du nicht gemacht. Womöglich liegt es daran.

Im Bild sieht man nur einen kleinen Teil des Algorithmus. Bzw. scheint mir, du hast überhaupt kein Quicksort gemacht, sondern irgendeinen anderen Algorithmus.

Konsii25

Beitragsersteller

30.09.2024, 15:21

Ja habe vergessen, die elemte währendessen zu tauschem. Danke
Habe es verstanden!

Ähnliche Beiträge

Pivotwahl bei Quicksort und Quickselect?

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

Jensek81

...zum Beitrag

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?

...zum Beitrag

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.

...zum Beitrag

wann ist quicksort langsamer als bubblesort - Beispiel?

hey ich möchte gerne mal ein Zahlenfolge-Beispiel sehen, wo man das genau sieht. habe schon viele zahlenfolgen gemacht wo die Liste bereits aufsteigend sortiert ist und wo das element das pivotelement ist ;D

Danke im voraus

...zum Beitrag

Labyrinth Algorithmus (mutierend) Tipps?

Guten Tag,

ich habe mich mal an mutierende Algorithmen als Amateur Programmierer herangewagt. Mein erstes Projekt ist ein Algorithmus, welcher den effizientesten Weg durch ein Labyrinth finden soll (Ich weiß, dass A* besser ist).

Ich bin wie folgt vorgegangen:

Labyrinth als zwei dimensionales Array (0 = Frei, 1 = Mauer)
Start- und Endpunkt festgelegt
STart Population erstellt aus zufälligen Pfaden (Ein Pfad ist ein Array, welches als Elemente 0,1,2 oder 3 enthalten, welche wiederum die Bewegungsrichtung vorgeben, die anschließend abgelaufen wird. Bspw. Hoch, hoch, links, rechts, runter.
Dann score für jeden Agent aus Entfernung zum Ziel (Satz des Pythagoras) und Länge des Pfades gebastelt. Kürzere Entfernung gibt mehr Punkte, unnötiger Weg Abzug
Danach werden für die 500 neuen agents jeweils zwei Eltern mit der Wahrscheinlichkeit basierend auf dem Score ausgewählt.
Das „Kind“ wird aus den zwei Hälften der Pfade der Eltern erstellt, wobei jedes Element des neuen Pfades eine Chance hat zu mutieren (Hier sehe ich bedarf zur Verbesserung)
Dies wiederholt sich solange ich will

Mein Problem ist, dass es bei kleinen Labyrinths den weg auch findet, aber die Wege noch teilweise sehr unnötig sind, obwohl ab dem Punkt, wo die meisten agents das Ziel erreichen, ja der längere weg rausselektiert werden sollte. Hatte überlegt auch minus punkte zugeben, wenn eine wand oder der Rand berührt wird, aber das hat nicht so funktioniert.

Mich würden eure Gedanken dazu interessieren und einfach ein paar Tipps zu der Thematik.

Code: https://hastebin.skyra.pw/aboladewoc.java

...zum Beitrag

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.

...zum Beitrag

Stochastik: Ist die Musterlösung falsch?

Ganz unten,

,,Die Wahrscheinlichkeit, dass ein Heimspiel gewonnen wurde, beträgt 11/29." und das soll falsch sein aber ich denke das es richtig ist.

Sieht man doch am linken Baum

15/29*11/15 = 11/29

Und ja der Baum ist richtig!

Triggert mich gerade etwas

...zum Beitrag

Binäre Suchbäume mit Algorithmus erweitern?

Hallo liebe Community, ich will einen Algorithmus schreiben, welcher einen binären Suchbaum, mit paarweise verschiedenen Schlüsseln, automatisch erweitert. Stellen wir uns vor wir haben einen Suchbaum, diesen übergeben wir dem Algorithmus und geben ihm dem Namen T. Der Algorithmus hängt an jedes Blatt von T neue Blätter an (so viele wie möglich). Hier ein kleines Beispiel:

wird zu

Ich habe dann erstmal angefangen drauf los zu programmieren und habe auch ein bisschen was hinbekommen. Aber bei mir ist das Problem, dass wenn der Baum größer wird, dass dann kein korrekter Suchbaum mehr rauskommt. Erst habe ich einen Algorithmus geschrieben der für Bäume der Höhe 2 funktioniert, dann für die Höhe 3. Dann habe ich bemerkt, dass das aber nicht für die Höhe 4 funktioniert und dann habe ich mich gefragt ob meine Grundidee vielleicht falsch war.

Meine Idee war ansich folgende: Erstmal habe ich triviale Bäume der Höhe 0 und 1 abgedeckt. Dann kommen wir zum richtigen Algorithmus (erstmal für einen Baum mit der Höhe zwei): Man schaut sich jeden Knoten rekursiv an. Wenn das linke Kind und das rechte Kind vom Knoten beide NULL sind, dann ist der Knoten ein Blatt, nennen wir dieses Blatt y.

Dann gibt es vier Fälle für das Blatt y:

Das Blatt kann ein linkes Kind im linken Teilbaum sein: Dann muss der Schlüssel des linken Kindes kleiner sein, als der Schlüssel von y. Der Schlüssel vom rechten Blatt muss größer sein als der Schlüssel von y aber kleiner als der Vaterknoten von y.
Das Blatt kann ein rechtes Kind im linken Teilbaum sein: Dann muss der Schlüssel des linken Kindes kleiner sein, als der Schlüssel von y, aber größer sein als der Vaterknoten von y. Der Schlüssel vom rechten Kind muss größer sein als der Schlüssel von y, aber kleiner als die Wurzel vom Baum.
Das Blatt kann ein linkes Kind im rechten Teilbaum sein: Dann muss der Schlüssel des linken Kindes kleiner sein, als der Schlüssel von y aber größer als die Wurzel vom Baum. Der Schlüssel vom rechten Kind muss größer sein als der Schlüssel von y, aber kleiner sein als der Vaterknoten von y.
Das Blattt kann ein rechtes Kind im rechten Teilbaum sein: Dann muss der Schlüssel des linken Kindes kleiner sein als der Schlüssel von y, aber größer als die Wurzel des Baums. Der Schlüssel des rechten Kindes muss größer sein, als der Schlüssel von y.

Mit diesen Bedingungen, kann man dann einen Algorithmus schreiben, der funktioniert. Aber halt nur für Bäume der Höhe 2. Bei einem Baum der Höhe drei hat das dann nicht mehr funktioniert, weil es sozusagen erstmal einen linken und einen rechten Teilbaum gibt und dann davon nochmal jeweils einen linken und rechten. Meine Idee war dann einfach ob, man sich in einem rechten Teilbaum befindet oder in einem linken, aber das hat nicht geklappt. Vielleicht kann mir ja jemand eine Grundidee geben, weil meine Idee anscheinend nicht richtig funktioniert. Das implementieren mache ich selber.

...zum Beitrag

Quicksort "Code" erklären?

Hi Leute, ich habe ein Problem mit Quicksort code und zwar ich verstehe wie das irl gemacht wird aber für mich ist der Code schwer zu verstehen. Kann mir bitte jemand diesen Code erklären?

public class QuicksortSimple {

  public void sort(int[] elements) {
    quicksort(elements, 0, elements.length - 1);
  }

  private void quicksort(int[] elements, int left, int right) {
    // End of recursion reached?
    if (left >= right) return;

    int pivotPos = partition(elements, left, right);
    quicksort(elements, left, pivotPos - 1);
    quicksort(elements, pivotPos + 1, right);
  }

  public int partition(int[] elements, int left, int right) {
    int pivot = elements[right];

    int i = left;
    int j = right - 1;
    while (i < j) {
      // Find the first element >= pivot
      while (elements[i] < pivot) {
        i++;
      }

      // Find the last element < pivot
      while (j > left && elements[j] >= pivot) {
        j--;
      }

      // If the greater element is left of the lesser element, switch them
      if (i < j) {
        ArrayUtils.swap(elements, i, j);
        i++;
        j--;
      }
    }

    // i == j means we haven't checked this index yet.
    // Move i right if necessary so that i marks the start of the right array.
    if (i == j && elements[i] < pivot) {
      i++;
    }

    // Move pivot element to its final position
    if (elements[i] != pivot) {
      ArrayUtils.swap(elements, i, right);
    }
    return i;
  }

}

...zum Beitrag

Wie begründet man die Anwendung der Sortieralgorithmen auf gegebene Beispiele?

Hallo liebes Forum,
ich versuche mich gerade etwas an dem Thema Sortieralgorithmen.
Die Theorie von Insertion Sort, Quicksort, Mergesort, Heapsort, Selection Sort, Bubblesort ist mir bekannt, habe auch jeden schon mal selbst programmiert und etwas getestet, nur war mir die Anwendung nie richtig klar.
Besser gesagt, wie und wann werden die außerhalb der Theorie verwendet.

Mir ist klar, dass man Insertion Sort und Selection Sort wegen ihrer mäßigen Worst Case Laufzeit nur für geringe Datenmengen einsetzt, bzw Insertion Sort auch, wenn die Daten schon vorher stark sortiert wurden.

Quicksort, Mergesort und Heapsort, weißen für großen Datenmengen die besten Laufzeiten auf, wobei man bei Quicksort darauf achten muss, das die zu sortierenden Elemente nicht schon sortiert sind, denn sonst geht die Laufzeit im Worst Case katastrophal nach oben. Weiter ist wenn es um die Speicherkapazität des Systems geht, Heapsort und vielleicht auch Qicksort zu bevorzugen, denn dank des speicherns der Ergebnisse auf ein Hilfsarray ist Mergesort ziemlich Speicher verbrauchend.

Nun habe ich diese ehemalige Klausuraufgabe aus einer Uni gefunden wobei es natürlich keine richtige Musterlösungen gab, sondern nur ein Hinweis (steht in Klammern), ich aber gerne einmal wüsste, wie man es richtig lösen könnte.

Aufgabe:

"Wählen Sie den effizientesten Algorithmus um diese Probleme zu lösen, begründen Sie außerdem ihre Entscheidung mittels der Kriterien Laufzeit und Stabilität.
Eine kurze Begründung ist ausreichend! "

An einer Verkehrskreuzung wurde über 10 Tage hinweg die Anzahl der Autos gezählt, die links abbiegen. Die Tageswerte liegen zwischen 10 und 2000 Autos. (SelectionSort)
An hunderten Wetterstationen Weltweit werden seit 1950 Temperaturwerte gesammelt. Die Werte werden auf ganze Zahlen gerundet. Der niedrigste Wert ist -89°C und der höchste 70°C. Insgesamt sind es ca. 1 Mrd. Werte. (CountSort)
Im Sonnensystem des Sterns "Sonne" gibt es 8 Planeten. Ihr Abstand zur "Sonne" ist zwischen 58 Mio. Km und 4495 Mio. Km. Die Planeten sollen Danach sortiert werden. (BubbleSort)
Ein Online-Shop hat ein Bewertungssystem für Seine Produkte, auf der Startseite sollen alle Produkte absteigend nach der Anzahl ihrer Bewertungen angezeigt werden. Diese Anzahl liegt in einem Array von Structs als Wert vor. Die Startseite soll jede Minute aktualisiert werden, somit wird der Algorithmus 1x pro Minute laufen. Da der Shop noch sehr klein ist, kommen selten neue Bewertungen zu Produkten dazu. (InsertionSort)
Ein neuer Zufallsgenerator hat 1 Mrd. Zahlen mit max. 512 Bit generiert. Um zu prüfen, wie gleichmäßig die Zahlen verteilt sind, sollen sie sortiert werden. (MergeSort)

Über eure Hilfe wäre ich sehr Dankbar

Lara

...zum Beitrag

Welcher Sortieralgorithmus ist unter welchen Umständen der schnellste?

Nabend.

Da ich mich ja mit der Programmierung beschäftige, habe ich versucht, einige Sortieralgorithmen in C++ nachzuprogrammieren (und mir danach die schnelleren Versionen aus dem Netz raus zu suchen). Dann wollte ich anhand einer Liste von 500.000 Elementen testen, welcher Algorithmus der Schnellste ist.

Getestet habe ich bisher std::sort, Quick Sort, Insertion Sort und Timsort. std::sort war bei der unsortierten Liste zwei Millisekunden schneller als Timsort, danach folgte Insertion Sort und Quick Sort war letzter. Wenn ich aber ein neues Element zu der sortierten Liste hinzugefügt habe, war Timsort der schnellste Algorithmus mit sage und schreibe 0 Mikrosekunden. Danach folgten Insertion Sort, std::sort und zu guter letzt war mal wieder Quick Sort fertig.

Wenn ich das ganze kurz zusammenfassen sollte, würde ich sagen, dass Timsort an dieser Stelle der beste Sortieralgorithmus ist, auch wenn er zwei Millisekunden langsamer bei der Sortierung einer komplett unsortierten Liste als std::sort ist. Zwei Millisekunden sind vernachlässigbar, vor allem, wenn std::sort bei der Sortierung der bereits sortierten Liste mit einem neuen Element 9 Millisekunden braucht, während Timsort nicht mal eine Mikrosekunde benötigt.

Gibt es Sortieralgorithmen, die noch schneller sind als die vier vorhin genannten? Oder welche anderen Szenarien könnte ich testen?

Gruß

...zum Beitrag

Wie korrigiere ich meinen CountSort-Code, damit er absteigend sortiert?

Hallo!

Meine Aufgabe: Ich soll eine Count Sort implementieren, und zwar so, dass man beim Programm aufrufen im Argument auswählen kann, ob das Array aufsteigend oder absteigend sortiert werden soll.

Mein Problem: Das Aufsteigen sortieren funktioniert, aber das Absteigen sortiert ebenfalls aufsteigend, obwohl es absteigend sortieren soll.

Meine Annahmen: Eigentlich gehe ich davon aus, dass meine Funktion "count_sort_write_output_array", welche das sortierte Array basierend auf der angegebenen Sortierrichtung erstellt, korrekt ist. Schließlich ist es einfach der gleiche Code wie für ASCENDING (aufsteigend), bloß mit geringfügigen Änderungen.

Ich denke eher, dass es daran liegt, dass mein Code erst gar nicht DESCENDING (absteigend) 'auswählt', wenn "desc" als Argument gegeben wird. Ich habe als Standardverhalten ASCENDING gesetzt (also falls kein Argument gegeben wird, oder ein falsches Argument gegeben wird, wird es aufsteigend sortiert), also dachte ich vielleicht, dass entweder

if (strcmp(order, "asc") == 0)

oder

else if (strcmp(order, "desc") == 0)

(in der SortDirection Funktion) irgendwie "falsch" sind, sodass die Sortierfunktion immer das Standardverhalten auswählt. (Also ASCENDING)

Als Debug-Versuch habe ich:

printf("Sortdirection must be defined. Using default: ASCENDING\n");

eingefügt, um zu schauen ob das wirklich der Fall ist. Dennoch wird dieser printf nie gezeigt, selbst wenn ich kein Argument eingebe. Was mich ziemlich verwirrt. Bricht es vorher ab?

Meine 'Frage' an euch: Ich würde es sehr schätzen, wenn jemand einen Blick darauf werfen könnte. Eventuell kann jemand erkennen, woran mein Semantikfehler liegt.

Aber würde ich es auch schätzen, wenn mir jemand andere Debug-Ideen nennen könnte. Ich habe noch nicht viel mit 'Debugging-Methoden' beschäftigt und habe meine Probleme bisher größtenteils mit printfs gelöst. Aber vielleicht gibt es da etwas leichteres!

Vielen Dank!

...zum Beitrag

Wieso wird das Fluor Atom nicht zweimal gezählt für die molare Masse?

Hallo

Das obere Bild ist die Aufgabenstellung und das untere die Musterlösung.

Das einzige was ich an der Musterlösung nicht verstanden habe, ist gelb markiert. Ich verstehe nicht, wieso man nicht die molare Masse von zwei Fluor Atome nimmt ? Also 38g/mol ?

Weil in der Aufgabenstellung kommt das Element Fluor in zwei Verbindungen vor, so bin ich zum Schluss gekommen, dass die molare Masse von Fluor mal zwei multipliziert werden muss. Was ist falsch an meiner Behauptung?

...zum Beitrag

Gibt es einen effizienten Algorithmus um alle Wortkombination bestimmter Buchstaben zu erstellen?

Ich versuch die Frage mal ein bisschen präziser zu stellen: Man gibt einem Programm n Buchstaben, das Programm gibt jetzt alle möglichen Wortkombinationen aus diesen Buchstaben zurück, sodass für zb 6 Buchstaben 6! = 720 Wörter ausgegeben werden.

Ich habe mir bereits etwas dazu überlegt, aber der Algorithmus ist extrem ineffizient: Ich lasse alle Wörter der Länge von a bis z durch, also bei n=6 zb. aaaaaa, aaaaab, aaaaac, ... usw. und überprüfe dabei den Wert und die Anzahl eines Charakters, wenn Wert und Anzahl mit meinen eingegeben Buchstaben übereinstimmt wird das Wort zurückgegeben, ansonsten wird das nächste Wort betrachtet und dasselbe noch mal überprüft. Da nur n! Wörter gefunden werden können bricht das Programm dann ab wenn n! Wörter gefunden wurden (möglicherweise auch früher, wenn sich unter den eingegeben Buchstaben Dopplungen befinden). Das Problem ist, dass dieser Algorithmus extrem ineffizient ist, da er bis zu 26^n - n! falsche Wörter durchgehen kann bis er fertig wird, die 26 Potenz ist natürlich derbe, deshalb wollte ich fragen, ob es vielleicht einen clevereren Algorithmus gibt der das besser machen kann.

Vielleicht sowas in der Form, dass bestimmte Elemente an bestimmten Indizes auf eine bestimmte Art und Weise mit einem anderen Element vertauscht werden, sodass in jedem Schritt ein neues gesuchtes Wort entsteht und somit nur n! Rechenschritte benötigt werden, gibts sowas?

...zum Beitrag

Was möchtest Du wissen?

Deine Frage stellen