Sortieralgorithmus – die meistgelesenen Beiträge

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

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

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

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.

Hallo,

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

LG

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.

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

Bitte schülergerecht erklären.

Vielen Dank 😊

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

Hallo,

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

Kann mir das jemand mal erklären?

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

Guten Abend,

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

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

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

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?

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.

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?

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

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

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 kenne mich recht gut mit dem Selectionsort aus. Meine Frage ist, wofür dieser verwendet werden kann / verwendet wird.

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

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

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

Lösung n-1 vergleiche überall,

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!

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.

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

Danke im voraus!