Quicksort darstellen?

Sortieren Sie das Array [4, 7, 1, 0, 0, 5, 11, 42, 43, 2] mittels Quicksort. Schreiben Sie dabei jeden Schritt als separate Zeile auf! (Das Durchzählen der Indizes müssen Sie nicht einzeln aufschreiben). Geben Sie an, nach welcher Regel Sie das Pivotelement wählen und welches im jeweiligen Schritt Ihr Pivotelement ist.

Ich blicke es nicht. Angeommen, ich nehme Pivot 2. Dann habe ich doch

1, 0, 0, 2, 4, 7, 5, 11, 42, 43

Bing AI oder ChatGPT spucken mir etwas anderes aus. Z.B.:

1. Schritt: [1, 0, 0, 2, 5, 4, 11, 42, 43, 7]

Wieso ist die 7 hinten und 5, 4 anstatt 4, 5? Auch in den Unterrichtsfolien werden Elemente vertauscht.

Aber wann macht man das?

1 Antwort

J0T4T4

04.02.2024, 02:34

Die Reihenfolge ist komplett egal.

Es ergibt aber Sinn, den Buffer jeweils vom Rand aufzufüllen, da man ja nicht weiß, wie viele Elemente noch kommen werden.

Viel Erfolg bei der Klausur :D

Woher ich das weiß:Studium / Ausbildung – Trust me, I'm an engineer

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

...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 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

Erstelle ein Polybios-Quadrat ohne Schlüssel?

Erstelle ein Polybios-Quadrat ohne Schlüssel:

a) Verschlüssele den Klartext:

CODIERUNGISTLUSTIG

b) Entschlüssele den Text:

35 24 55 55 11 45 33 14 15 24 43 13 42 15 32 15

c) Entschlüssele den Text:

24 13 23 32 45 43 43 32 24 13 22 25 34 33 55 15 33 44 42 24 15 42 15 33

...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

Kann mir wer die Green Line 1 Lösung sagen?

Kann mir vielleicht jemand diese lösungen sagen? :

(im green line 1)

Seite: 42 nummer 11 und auf Seite 43 nummer 14

Das wäre lieb.

LG candyXY123

...zur Frage

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!

...zur Frage

Was bedeuten diese Zahlen?

Hi,

ich habe im Informatikunterricht als Zusatzaufgabe eine Aufgabe bekommen, die ein Text ergeben soll. Allerdings sind es nur Pärchenzahlen, mit denen ich nichts anfangen kann. Gegoogelt habe ich auch schon, bin aber auf keine Lösung gekommen. Hat jemand von euch eine Idee wie dieser Text übersetzt heißt ?

14 11 43 55 24 15 31 12 15 21 24 33 14 15 44 43 24 13 23 24 32 32 15 42 51 34 33 11 13 23 44 12 24 43 55 15 23 33 45 23 42 14 42 11 45 43 43 15 33 51 34 42 14 15 32 23 11 45 43 ... 43 13 23 31 11 22 15 14 11 33 33 55 45 45 33 14 43 13 23 33 11 35 35 14 24 15 43 15 33 42 15 53 ! 33 24 32 32 11 33 43 13 23 31 24 15 15 33 14 14 15 33 12 45 43 24 33 42 24 13 23 44 45 33 22 24 33 33 15 33 43 44 11 14 44 . 14 11 33 33 33 24 32 32 14 15 33 13 34 32 35 45 44 15 42 23 24 33 44 15 33 31 24 33 25 43 24 32 24 33 44 15 42 33 15 44 13 11 21 15 … 14 45 21 24 33 14 15 43 44 14 34 42 44 52 15 24 44 15 42 15 11 33 52 15 24 43 45 33 22 15 33 31 34 15 43 13 23 15 14 11 33 11 13 23 14 24 15 11 33 52 15 24 43 45 33 22 15 33 !

...zur Frage

Kommt mein DHL Paket morgen oder übermorgen?

Status: Die Sendung wurde vom Absender in der Filiale eingeliefert. Do, 05.03.2015 11:43 Uhr Nächster Schritt: Die Sendung wird ins Start-Paketzentrum transportiert.

...zur Frage

Was bedeutet Stabilität bei Algorithmen?

Hallo zusammen,

ich stehe kurz vor meiner ersten Klausur "Grundlagen der Wirtschaftsinformatik 1" und beschäftige mich momentan mit Sortieralgorithmen.

Wir haben eine Aufgabe bekommen, die lautet: "Analysieren Sie, welche der erarbeiteten Sortieralgorithmen (Bubble-, Insertion-, Selection-, Quick-, Merge- und Shell-Sort) stabil sind."

Was bedeutet in diesem Kontext "stabil". Ich kann mir leider nicht wirklich etwas drunter vorstellen. Ich vermute, es hat vielleicht etwas mit der vorliegenden Reihenfolge zu run?!

Vielen Dank schonmal und liebe Grüße :-)

...zur Frage

Aufgabe: Minimum ermitteln?

Hallo Leute, könnt ihr mal kurz kontrollieren ob ich die folgende Aufgabe richtig gemacht habe?

/*
Aufgabe 1: Minimum ermitteln
Gegeben sind drei String Variablen mit beliebigen ganzzahligen Werten (als Strings!), z.B. "23", "5","13".
Wandeln Sie die Strings in Integer-Werte um und ermitteln Sie das Minimum und Maximum der drei Zahlen.
Geben Sie die drei Zahlen und das Minimum/Maximum auf der Konsole aus.

Das Minimum von 23, 5 und 13 ist 5.
Das Maximum von 23, 5 und 13 ist 23.
*/

String zahl1 = "23";
String zahl2 = "5";
String zahl3 = "13";

boolean minimum = Integer.parseInt(zahl2) < Integer.parseInt(zahl1) && Integer.parseInt(zahl2) < Integer.parseInt(zahl3);
System.out.println(minimum);

boolean maximum = Integer.parseInt(zahl1) > Integer.parseInt(zahl2) && Integer.parseInt(zahl1) > Integer.parseInt(zahl3);
System.out.println(maximum);

//true
//true

...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

Pseudocode lesen?

Hallo, ich tue mich sehr schwer in Pseudocode s lesen. Kann mir jemand helfen, das zu lernen oder zeigen, was im folgenden Pseudocode (es geht um den Countingsort) steht?
Ich verstehe nur die Eingabe und das Ende bei return :((

Ich wäre sehr dankbar!

Um genauer zu sein und die Fragen am Beispiel zu stellen:

was bedeutet zahlen [0]

was ist i++

temporäre Liste ist wahrscheinlich der Hilfsarray?

finaleposition ist dann das Ergebnisarray? Was bedeutet finaleposition++

Ich glaub man sieht, ich komme nicht ganz zurecht, aber ich würde mich freuen, wenn das jemand erklären könnte.

...zur Frage

Was ist besser: Selection Sort, Bubble Sort oder Quick Sort und warum?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen