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?

Ich verstehe nicht was O(n) oder O(n+k) bedeutet. Weiss es jemanden?

Kann jemand mal erklären wie bubble sort funktioniert? Warum gibt es ihn wenn er doch uneffektiv ist?

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.

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

1. Divide and Conquer
2. QuickSort
3. QuickSort mit zufälliger pivotwahl

was sagt ihr?

Gruß

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!

Hey,

Ich habe eine Aufgabe zu Bubblesort - natürlich möchte ich nicht das ihr meine Hausaufgaben erledigt, jedoch sitze ich im Moment fest, da ich etwas verwirrt bin und habe eine Frage dazu.

Also hier soll man ja eine Handsimulation durchführen und so wie ich das verstanden habe, geht Bubblesort die Schleife durch und "blubbert" dann sozusagen das größte Element nach oben. Also müsste hier erst 43 "hochblubbern" und dann 21. Danach sollte es eigentlich bereits sortiert sein.

Ich dachte meine Handsimulation ist so richtig, aber was mich verwirrt ist, dass dort nachdem es eigentlich (?) fertig sein sollte noch so viel Platz ist? Auch verstehe ich nicht ganz was ich bei Swap Nummer schreiben soll. Was bedeutet Swap Nummer?

Könnte mir jemand einen Tipp geben? Vielen Dank!

Wenn ihr nicht wüsstet was das wäre und das erklärt bekommen würdet, wie schnell könntet ihr sowas in Java umsetzen wenn ihr nicht auf bestehende Heapklassen zugreifen könntet

Hey, ich soll ein zweiseitiges Handout zu den Sortieralgorithmus selection sort erstellen, wobei ich

1. auf die grundlegende Vorgehensweise dieses Algorithmus eingehen soll
2. und ich brauche die Java- Methode zur Implementierung, wobei man davon ausgehen soll, dass ein Array von int- Werten zu sortieren ist.

Dazu wurde uns auch Material gegeben, welches ich als Foto anhängen werde.

Ich freue mich auf Rückmeldungen!

Hallo kann mir jemand erklären was die Zeile macht?

Selectionsort selectionsort = new Selectionsort

Hallo zusammen,
Ich schreibe morgen eine Informatik Klausur über Sortieralgorithmen und wir müssen die Formeln für die jeweilige Laufzeit der verschiedenen Sortieralgorithmen im Best-/Average-/Worstcase Szenario wissen. Allerdings war ich in der Stunde krank und kann mir nicht wirklich erschließen, für was das "O" und das "n" steht. Hat hier wer eine Ahnung davon, da ich im Internet nicht wirklich was hilfreiches finde.
Danke schonmal im Voraus und LG!

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.

Hallo, ich hab die O-Notation schon so mehr oder weniger verstanden, also dass es um den Zeit/Platzverbrauch von Algorithmen geht und bei O(n^3) der Zeit/Platzverbrauch immer hoch drei dem Eingegebenen entspricht.

Was ich aber nicht verstehe, wie man das bei mathematischen Ausdrücken zeigen soll. Z.B.:

Was ich mir vorstellen könnte wäre, dass n die Eingabe entspricht und der Funktionswert der dann rauskommt gleich der Eingabe hoch vier entsprechen muss (ist hier ja aber nicht der Fall).

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?

Zum Beispiel Bubblesort (O(n^2)).

Vor- und Nachteile folgender Sortierverfahren: Insertionsort, Tournamentsort, Mergesort, binäre Suche ?

Bitte schülergerecht erklären.

Vielen Dank 😊

Dieser Algorithmus läuft ja immer linear, warum insertionsort nicht, der ja auch eigentlich nur Vergleiche vollzieht?:

Lösung n-1 vergleiche überall,

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?

Wasist der Unterschied zwischen Bubblesort und Selection-sort. Ich meine beides sind ja vergleichsbasierte Sortierverfahren.

Guten Abend,

hab mir mal den Quicksort angeschaut und frage mich ,warum der average case und der best case dieselbe Laufzeit haben.

Ich möchte ein Programm schreiben, dass ein Array mit Count Sort sortieren soll. Doch habe ich einen Fehler. Meine Eingabe für das unsortierte Array war:

38 38 19 57 0 18 59 27 18 57 19 47 4 2 5 5 1 1 

Aber als Ausgabe bekam ich bloß:

 0 1 1 2 4 5 5 0 0 0 0 0 0 0 0 0 0 0

Für dieses Programm sind besonders 2 Funktionen wichtig und ich denke, dass in einen der Beiden mein Fehler ist. Hier ist meine erste Funktion fürs Zählen:

void count(int input_array[], int len, int count_array[]) 
{
	for (i=0; i < len; i++) 
	{
		count_array[i] = 0;
    }
	for (j=0; j<len;j++) 
	{
		count_array[input_array[j]]++;
    }
}

Meine erste For-schleife soll sagen, dass count_array min. 38 Stellen lang sein soll und soll überall mit 0 initialisierst werden. "len" steht für Länge und ist 38.

Die zweite for-Schleife soll das eigentliche Nachzählen tun. zBs. bei j=1 sollte die for-Schleife also im output_array eine 38 finden. Also soll count_array bei der Stelle 38 um eins erhöhen. Das gleiche mit j=2 usw.

Und meine zweite Funktion soll nun das output Array schreiben, welches richtig sortiert ist. k ist der Index im output_array. k ist der Index. Die erste for-Schleife soll das count_array durchgehen und die zweite for-Schleife soll das schreiben der Zahl so oft wiederholen, wie häufig diese gefunden wurde.

void write_output_array(int output_array[], int len, int count_array[]) 
{
	k=0;
    for (j=0; j < len; j++) 
	{
		for (i=0; i < count_array[j]; i++) 
		{
			output_array[k] = j;
			k++;
		}
	}
}

Hat jemand eine Idee warum write_output_array wohl früher endet als gewollt?

Hallo,

was genau bedeutet denn der Begriff "In-Place"? Vielleicht könnte mir jemand eine Erklärung mit Bezug auf den Selectionsort geben?

LG

Ist das Sortierverfahren, das im unteren Bild zu sehen ist, bubblesort oder insertionsort?

Danke im voraus!

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.

Die Frage sagt schon alles, ich würde gern wissen in welchem Jahr es ca. erfunden wurde aber finde dazu irgendwie nichts.

Ich kenne mich recht gut mit dem Selectionsort aus. Meine Frage ist, wofür dieser verwendet werden kann / verwendet wird.

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.

Guten Morgen,

ich wollte mal fragen ob es schon Technische Lösungen gibt in der KI ein Datenfeld nach vorgegebenen Regeln bearbeiten und ausgeben kann. Es geht dann darum Produktionsabläufe zu optimieren. Gibt es da schon KNNs die je nachdem individuell anpassbar sind?

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.

LG

Jensek81

Wir haben folgenden Algorithmus für Insertion-Sort:

void InsertionSort int a[], int n) {
   int i, j, key;
   for(j = 1; j < n; j++) {
   key = a[j];
   i = j-1;
   while (i >= 0 && a[i] > key){
      a[i+1] = a[i];
      i = i-1;
   }
   a[i+1] = key;
   }
}

Die Aufgabe lautet:

Drehen Sie die Reihenfolge bei InsertionSort: Statt uber das Maximum einzusortieren, soll uber das Minimum einsortiert werden.

Ich verstehe die Aufgabe nicht. Wo wird denn "über das Maximum einsortiert", was bedeutet das?

Ich verstehe wie der Algorithmus funktioniert ... wenn da steht 671, und man bei j = 2 angelangt ist, dann wird 671 -> 677 -> 667 -> 167.

Aber ich verstehe nicht wo da "über das Maximum einsortiert" wird, oder was ich da nun ändern soll, oder wie ich das ändern sollte.

Könnte mir das wer erklären?

Ich verstehe nicht, wie der Algorithmus funktionieren soll??

Wieso wird i zu j umbenannt?

Was heißt solange j>0 und sortiert[j-1] > buecher i? Wieso das j-1 dort?

Wieso j= j-1 und was passiert bei sortiert[j]= buecher[i]

Der Algorithmus ist ein Sortier Algorithmus Insertion Sort

Bitte um Hilfee

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

Hey liebe Gute Frage Community,

ich bin gerade dabei mir das Thema Sortierverfahren und deren Komplexität genauer anzuschauen. Ich treffe immer wieder auf den in der Frage genannten Ausdruck O(n*log(n)). Kann mir vielleicht jemand erklären, was die einzelnen Bestandteile aussagen? Soviel hab ich selber schon herausgefunden, n beschreibt die Anzahl von Elementen im zu sortierenden Array. O ist ein Landau Ausdruck (Bitte nochmal erklären, hab noch nicht so ganz den Sinn verstanden). Log(x) ist sozusagen eine umgedrehte Exponentialfunktion, aber ich hab noch nicht so ganz verstanden, was das Ergebnis ist. Die Funktion beschreibt doch einen Graphen. Aber eigentlich brauche ich doch ein eindeutig definiertes Ergebnis, oder irre ich mich?

Vielen Dank für Eure Hilfe, ich würde mich über ausführliche Erklärung unglaublich freuen und Website Verweise wären top, wenn ich mal etwas zitieren muss. Danke!!

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! "

1. 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)
2. 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)
3. 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)
4. 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)
5. 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

LG

Lara

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 :-)

Hallo,

ich verstehe den Unterschied zwischen Bucketsort und Radixsort nicht. Beide sortieren doch die Elemente in Buckets.

Kann mir das jemand mal erklären?