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ß

5 Antworten

regex9

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, programmieren, Informatik

11.09.2016, 03:14

Wenn der Timsort beim zweiten Durchlauf schneller war (vor allem mit einer Laufzeit von 0ms), dann muss das Sortierergebnis vom ersten Durchlauf gecached worden sein.

Bezüglich der std::sort-Funktion kann ich mir gut vorstellen, dass bei der Implementierung alle Möglichkeiten ausgenutzt wurden, die C++/der Compiler anbieten, um die Performance zu verbessern. Man wird sicherlich mit Pointern und Templates gearbeitet haben und einer Kombination verschiedener Sortieralgorithmen.

Was du noch untersuchen könntest:

Listen statt Arrays
ein Aggregat mit jeweils 10, 100 und 1.000.000 Elementen
ein Aggregat mit einer ungeraden Anzahl an Elementen

Bezüglich schnellerer Sortierverfahren: Sortieralgorithmen sind von ihrem Einsatzgebiet abhängig. Ein Quicksort wird nicht seine volle Stärke ausspielen können, wenn er nur eine kleine Menge an Elementen sortieren soll oder sein Pivot-Element schlecht gewählt wird.

Orientieren würde ich mich wohl an der O-Notation (im average case). Für weitere Sortierverfahren kannst du hier schauen: https://de.wikipedia.org/wiki/Sortierverfahren

Außerdem kannst du, wie hier in anderen Antworten schon angemerkt, sicherlich noch an der Implementierung feilen. Achte darauf, was du für Vergleichsfunktionen verwendest, was für Datentypen, etc..

W00dp3ckr

11.09.2016, 01:36

Deine Frage entspricht nicht dem, was Du testest. Du vergleichst eigentlich Implementierungen auf einer gegebenen Architektur mit einem gewissen Compiler.
Wie auch mein Vorredner sagt, ist nur ein kleiner Teil der eigentliche Sortieralgorithmus, die Implementierung spielt eine große Rolle. Sind die Vergleichsalgorithmen überall gleich?

Was für ein Sortierverfahren nutzt eigentlich Dein std::sort ?

adenosi

11.09.2016, 09:55

Ich würde mir an deiner Stelle die Algorithmen der Sortierungen ansehen und diese dann selber nachzuprogrammieren.

Ebenfalls kann es sein das sich manche Algorithmen für bestimmte Fälle besonders gut eignen.

TeeTier

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

programmieren

11.09.2016, 05:29

Die Antwort ist ganz einfach: Es gibt keinen "schnellsten" Sortieralgorithmus.

Denn es hängt extrem vom Anwendungsfall ab:

Soll / muss / darf das Ergebnis stabil sein? (z. B. wenn du mehrfach hintereinander nach unterschiedlichen Kritieren sortieren möchtest)
Ist dir Geschwindigkeit oder Speicherverbrauch wichtiger? (Wird einmalig bei der Initialisierung eines Embedded-Computers sortiert, oder dauerhaft im Betrieb eines starken Desktops?)
Sind die vorliegenden Daten schon zu großen Teilen vorsortiert?
Sind die Daten evtl. oftmals schon sortiert, allerdings rückwärts?
Sind die Daten wirklich zufällig verteilt?
Werden Container von Zeigern, Referenzen oder ganzen Objekten sortiert?
Welche Art von Container liegt vor?
Hast du wahlfreien Zugriff auf die Elemente, oder kannst du dich nur "durchhangeln"?
Darf das Ergebnis vielleicht sogar Fehler enthalten, d. h. falsch sortierte Einträge enthalten? (Lach nicht, dafür gibt es tatsächlich Anwendungsfälle!)

Es gibt noch eine Million weitere Punkte, die zu berücksichtigen sind, und wie du siehst, kann es aufgrund der verschiedenen Anforderungen keinen besten Algorithmus geben. :)

Im Übrigen ist korrektes Profiling eine Kunst. Dabei gibt es unglaublich viele Dinge, die du nicht beachtest, und die dir dann falsche Ergebnisse liefern, die du vermeintlich für richtig hältst. Deine genannten Zahlenwerte machen einen solchen Eindruck!

Du solltest unbedingt die Last so erhöhen, dass du mindestens im zweistelligen Sekundenbereich bist, denn bei 9ms ist einfach viel zu viel Spielraum für "Dreckeffekte", die jede Aussage zu Nichte machen. :)

Naja, viel Spaß noch! Aber ohne vernünftige Vorgaben kann man nicht sagen, was das "Beste" ist. :)

PS: TimSort ist ja der Standard-Sortier-Algorithmus in Java und hatte vor ca. einem Jahr noch einen Bug, sodass u. U. einige Listen von Eingangsdaten fehlerhaft sortiert wurden. Das Lustige daran ist, dass es ewig keiner gemerkt hat und dann plötzlich alle: "Java sortiert falsch! Aaahhh!". :)

Such mal bei Google nach "java timsort bug" ... interessante Geschichte! ;)

DerCo

11.09.2016, 00:44

wenn nach dem hinzufügen eines Elements 0ms reichen, würde ich sagen, du hast den Kram im Cache - hast du den heap dealloziert nach der Routine? Sonst stimmen deine Ergebnisse alle nicht.

Was sortierst du eigentlich? Ein simples Array mit Randomdaten?

Was ist mit bubble sort? Schon probiert?

DerCo

11.09.2016, 00:48

Zu Teil 2 deiner Frage: Eine kluge Indizierung ist wertvoller als der coolste Algo, da du von vorneherein die betroffenen Datensätze extrem einschränken kannst; darum ist z.B. eine clevere Datenbank 1000mal mehr wert als das geilste Script.

Alleine über Restrukturierung einiger SQL-Datenbanken konnte ich die Scriptlaufzeiten bis zu 800% schneller machen; hab den alten Kram selbst verbrochen, aber man lernt ja immer wieder was neues und ab und zu lohnt das Nachschauen :)
Trotzdem wie gesagt: Indizierung ist extrem wertvoll; ich habe alle Emails seit 1997 (immerhin 20 Jahre) in meiner Datenbank; das sind knapp 300GByte - und durchsuche nach beliebigen Kriterien in 10-15 Sekunden; nach bestimmten Indexfeldern in unter 1 Sek.

PeterLustig1999

Fragesteller

11.09.2016, 01:01

Ich habe mir mein unsortiertes Array kopiert, sortieren lassen und danach die sortierte Kopie wieder gelöscht. Gemessen habe ich nur die Zeit, die das reine sortieren gebraucht hat.

Ich sortiere ein simples Array mit Randomdaten, wie du bereits sagst. Des unsortierte Array speichere ich jedoch zwischen, sodass jeder Algorithmus quasi mit dem gleichen Array startet.

Weiterhin habe ich das Ganze mehrfach getestet und mich nicht nur auf ein Testergebnis beschränkt. Generell ist std::sort bei der ersten Sortierung ungefähr 2 ms schneller als Timsort, generell benötigt Timsort bei der zweiten Sortierung immer 0 mikrosekunden.

Bubble Sort habe ich noch nicht ausprobiert, könnte ich vielleicht einmal versuchen.

DerCo

11.09.2016, 01:17

@PeterLustig1999

naja das mit bubble war eher für die Vollständigkeit, Qsort ist, wenn ich mich richtig erinnere quasi so etwas wie der "Nachfolger"; insofern wird es sicher keine Top-Werte liefern.

Für eine spätere Anwendung wird es nicht nur entscheidend sein, wie viel Daten du hast, sondern auch wie komplex sie sind, also wie oft die schleifen laufen und wie tief die Rekursionen werden (schliesslich gibt es auch hier eine Grenze, bei der du in den "too many nested scopes"-Fehler rennst).

Für eine poplige Adresssortierung ist es schlicht irrelevant, was du nimmst, da hier ein paar Millisekunden mehr oder weniger nicht ins Gewicht fallen; Ganz anders sieht das aus, wenn du z.B. mit Suggests arbeitest (das ist das was Google macht, dass direkt bei der Eingabe der User Vorschläge ausgespuckt werden, die ja über Ajax geladen werden müssen).

Wieder etwas völlig anderes ist beispielsweise eine Programm um Daten zu ver/ent-schlüsseln.

Um es kurz zu machen; jeder Algorithmus hat seine Stärken und Schwächen und abgesehen davon, dass es eine gute Übung ist, wirst du in Zukunft deine Wahl abhängig von der Aufgabenstellung treffen müssen; da helfen dir deine jetzt ermittelten Testwerte nicht weiter.

DerCo

11.09.2016, 01:21

@DerCo

Bevor ich es vergesse: WO du richtig was gutmachen kannst, ist bei der klugen Auswahl der verwendeten Stringoperatoren.
Ein
strpos, ein substr oder, wenn möglich ein Byteshift, sind je nach
Stringaufbau und -länge verschieden schnell - hier lassen sich ggf.
sogar SEKUNDEN einsparen!

regex9

11.09.2016, 02:44

@DerCo

Ich habe mich schon gewundert. Der BubbleSort ist ein etwas langsames Sortierverfahren im Vergleich zu anderen (mit einem Laufzeitverhalten von O(n²)).

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

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

Warum ist der Quick Sort instabil?

ich habe morgen einen Vortrag über quick sort und stoße immer wieder darauf, dass es ein instabiler sortieralgorithmus ist. Kann mir das jemand erklären, was damit gemeint ist? Am besten auf Schüler Niveau :)

...zur Frage

Pyhton - Sortieralgorithmus?

Hallo Zusammen,

Aktuell müssen wir in der Berufsschule ein Lottozahlen Generator schreiben, das dieser 6 Zahlen ausgibt hab ich schon geschafft.

Das zweite wäre das wir die Ausgaben in der in der gezogenen sowie aufsteigend sortierten Reihenfolge ausgeben sollen. Ich hatte schon im Netz gesucht aber nichts gefunden, und jeder Lottozaglengenerator verweist auf die "sort" Funktion hin die wir nicht benutzen dürfen.

Weiß jemand daher wie man diesen Algorithmus schreibt ?

Grüße, YouGetMyAnswer

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

In Java bestimmte Werte aus einem Array in Indexvariable eines neuen Arrays speichern?

Hallo,

ich habe gerade das Problem, dass ich an einer Aufgabe sitze, bei welcher man ein Neues Feld erzeugen soll in welchem die Werte aus einem vorgegebenen Feld so eingefügt werden, dass alle negativen Zahlen im linken Bereich und alle postiven Zahlen sowie 0 im rechten Bereich liegen. Gegeben ist folgender Code:

public static int randomInt(int a, int e) {
    return (int) (Math.random() * ((e - a) + 1)) + a;
}

public static void fuellen(int[] feld, int a, int e) {
    for (int i=0;i<feld.length;i++){
        feld[i] = randomInt(a,e);
    }
}

public static void ausgeben(int[] feld){
    for (int i=0;i<feld.length;i++){
        System.out.printf("%3d ", feld[i]);
        if ((i+1) % 10 == 0) {
            System.out.println();
        }
    }
    System.out.println();
}

bis Jetzt war mein Ansatz dieser hier:

public static int[] verteilen(int[] feld){
    int[] feld2 = new int[feld.length];
    int first = feld2[0];
    int last = feld2[feld2.length - 1];
    int count = 0;
    int right = feld2.length - 1;
    for(int i=0;i<feld.length;i++) {
        if(feld[i] < 0) {
            first = feld[i];
            count++;
        }
        else {
            last = feld[i];
            right--;
        }
    }
    return feld2;
}

und als Ergebnis soll das rauskommen aber irgendwie klappt es nicht:

39-34 76-84-79-61-59-50 96 55 -71-51-89 77 64 93-20-86 43 33

-34 -84 -79 -61 -59 -50 -71 -51 -89 -20
-86  33  43  93  64  77  55  96  76  39

...zur Frage

Code zur Kombination von Werten ohne Widerholung?

Guten Tag zusammen,

ich möchte in einem Programm eine Matrix aus einem Vektor erstellen, in welcher alle Kombinationen der Werte des Vektors ohne Widerholung aufgetragen sind.

Also z.B:

Vektor: (1,2,3)

Ergebnis: (1,2,3) , (1,3,2) , (2,1,3) , (2,3,1) , (3,1,2) , (3,2,1)

Der Code sollte mit jeglicher Anzahl an Zahlen funktionieren (die Laufzeit ist unwichtig). Die Werte im Array sind nie doppelt (falls das von Bedeutung sein sollte).

Wäre super, wenn ihr mir einen pseudocode schreiben oder gängige Algorithmen/Verfahren für eine weitere eigenrecherche nennen könntet.

Vielen Dank für eure Hilfe!

...zur Frage

C++ alle Kombinationen eines Strings mit der Länge L mit zurücklegen?

Hallo,

ich möchte so etwas wie einen Password-List-Generator schreiben, komme aber nicht auf die richtige Rekursionsfunktion.

Es soll zum Beispiel aus einem Zeichensatz wie "abcdef" und der information L = 9 Passwörter im vector<string> zurückgegeben werden, bei denen jeder der Buchstaben an jeder Position 0, 1, .., 9 mal vorkommt, wie beim Passwortgenerator "crunch".

Hat mir jemand ein Code-Beispiel parat?

Viele Grüße

Lukas Z

...zur Frage

Python Algorithmus für Perfekten Sitzplan?

Hallo liebe Community,

Ich habe es mir zum Ziel gemacht einen Algorithmus zu entwickeln, der mir den wirklich perfekten Sitzplan ausgibt:

Dass heißt ich habe mir gedacht ich vergebe Leuten eine Wertigkeit: 0,1,2

Daraus möchte ich dann die perfekte Zusammenstellung erarbeiten und ein Produktives Umfeld zu erschaffen. Hat jemand eine Idee bzw Anregungen für mich?

...zur Frage

C++ Code für LGS?

Ich möchte mit einen C++-Programm alle LGS lösen können (endlich, unendlich und keine Lösungen). Ich habe auch einen Code. Endlich viele und keine Lösungen kann er recht gut (bisher), aber unendlich viele Lösungen kann er nicht anzeigen lassen (soll dann auch t einführen, nicht einfach einen Wert einsetzen).

Wo liegt der Fehler?

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// Funktion zur Berechnung des Determinanten einer Matrix
double determinant(vector<vector<double>>& matrix, int n) {
  double det = 0;

  if (n == 1) {
    return matrix[0][0];
  }

  if (n == 2) {
    return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
  }

  for (int i = 0; i < n; i++) {
    vector<vector<double>> subMatrix(n - 1, vector<double>(n - 1));

    for (int j = 1; j < n; j++) {
      for (int k = 0; k < n; k++) {
        if (k < i) {
          subMatrix[j - 1][k] = matrix[j][k];
        }
        else if (k > i) {
          subMatrix[j - 1][k - 1] = matrix[j][k];
        }
      }
    }

    det += pow(-1, i) * matrix[0][i] * determinant(subMatrix, n - 1);
  }

  return det;
}
 
// Funktion zur Durchführung der Gauss-Jordan-Elimination
void gaussJordan(vector<vector<double>>& matrix, vector<double>& constants) {
  int n = matrix.size();

  for (int i = 0; i < n; i++) {
    int maxIndex = i;

    for (int j = i + 1; j < n; j++) {
      if (abs(matrix[j][i]) > abs(matrix[maxIndex][i])) {
        maxIndex = j;
      }
    }

    if (maxIndex != i) {
      swap(matrix[maxIndex], matrix[i]);
      swap(constants[i], constants[maxIndex]); // Korrektur hier
    }

    double factor = matrix[i][i];

    for (int j = i; j < n; j++) {
      matrix[i][j] /= factor;
    }

    constants[i] /= factor;

    for (int j = 0; j < n; j++) {
      if (j != i) {
        double factor = matrix[j][i];

        for (int k = i; k < n; k++) {
          matrix[j][k] -= factor * matrix[i][k];
        }

        constants[j] -= factor * constants[i];
      }
    }
  }
}

// Funktion zur Überprüfung der Invertierbarkeit und zur Lösung des LGS
vector<double> solveLinearSystem(vector<vector<double>>& matrix, vector<double>& constants) {
  int n = matrix.size();
  double det = determinant(matrix, n);

  // Überprüfung auf unendlich viele Lösungen
  bool allZero = true;

  for (double constant : constants) {
    if (constant != 0) {
      allZero = false;
      break;
    }
  }

  if (det == 0) {
    if (allZero) {
      cout << "Das LGS hat unendlich viele Lösungen." << endl;
      return {}; // Leerer Vektor, da unendlich viele Lösungen existieren
    }
    else {
      cout << "Das LGS hat keine Lösung." << endl;
      return {}; // Leerer Vektor, da keine Lösung existiert
    }
  }

  // Anwendung der Gauss-Jordan-Elimination
  gaussJordan(matrix, constants);

  vector<double> solution(n);

  for (int i = 0; i < n; i++) {
    solution[i] = constants[i];
  }

  return solution;
}

int main() {
  vector<vector<double>> matrix = {
    { 1, -3,  5 },
    { 2, -5,  12 },
    { 3, -11,  11 }
  };
  vector<double> constants = { 2, 1, 12 };

  vector<double> solution = solveLinearSystem(matrix, constants);

  if (!solution.empty()) {
    cout << "Die Lösung des LGS ist: ";

    for (int i = 0; i < solution.size(); i++) {
      cout << "x" << i + 1 << " = " << solution[i] << ", ";
    }

    cout << endl;
  }
  else {
    cout << "Das LGS hat keine Lösung." << endl;
  }

  return 0;
}

...zur Frage

Java Bubble Sort Algorithmus programmieren wer kann mir helfen (bitte keine Lösung schreiben sondern nur Tipps geben)?

Die Aufgabenstellung lautet:

"Damit Sie sehen wie nervig das Sortieren eines Arrays wirklich sein kann wenn man es selbst programmieren muss: implementieren Sie einen einfachen Sortieralgorithmus in einer Methode namens 'bubblesort'. Diese Methode erwartet einen Parameter 'x' wie in der letzten Aufgabe, und verfährt auch genauso mit ihm. Die Sortierung wird wie folgt durchgeführt: angefangen beim zweiten Array-Element (also mit Index 1) prüfen Sie für alle Elemente, ob sie kleiner sind als ihr Vorgänger, und vertauschen sie sofort falls ja. Dies wird so lange durchgeführt, bis bei einem kompletten Durchlauf durch das Array (beginnend bei Index 1) keine Vertauschung mehr vorgenommen werden muss, in diesem Fall ist das Array sortiert. Falls das Array 0 oder 1 Elemente hat muss nichts getan werden da solche Arrays bereits sortiert sind (warum?). Tipp: die perfekte Gelegenheit eine do/while-Schleife zu benutzen!"

Mit freundlichen Grüßen

...zur Frage

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

...zur Frage

Kann mir jemand helfen?

Ich soll ein Struktogramm für diese Aufgabenstellung erstellen: Erstellen Sie einen Algorithmus, der den Benutzer nach zwei Zahlen Z1 und Z2 fragt und der anschließend ausgibt, ob

• Z1 größer als Z1 ist, oder

• Z1 kleiner als Z2 ist, oder

• beide Zahlen gleich sind.

Mein Struktogramm sieht so aus:

Bei der Auswertung im Programm bekomme ich immer Fehler und ich weiß nicht was an meinem Struktogramm falsch ist:

...zur Frage

Python: Balkendiagramm beim Sortieren?

Hallo,

ich wollte ein Sortierverfahren programmieren und bei jedem Durchlauf durch das Array soll ein Balkendiagramm erzeugt werden.

Die sortierten Zahlen sollen rot sein und die unsortierten blau.

Bisher habe ich es geschafft, dass die sortierte Liste als Balkendiagramm angezeigt wird. Mein Programm sieht so aus:

def Sortierverfahren_Bubblesort(Liste):
  n = len(Liste)
  for i in range(n):
    for x in range(0, n - i - 1):
      if Liste[x] > Liste[x + 1]:
        Liste[x], Liste[x + 1] = Liste[x + 1], Liste[x]

Sortierverfahren_Bubblesort(Liste)
print("Sortierte Liste: ", Liste)

#Balkendiagramm
import matplotlib.pyplot as plt
import numpy as np

bar_width = 0.5
index = np.arange(len(Liste))
plt.bar(index, Liste, bar_width, color="blue")
plt.xticks(index, range(len(Liste)))
print("Balkendiagramm: ")
plt.show()

Es wäre cool, wenn mir jemand die Lösung dazu sagen würde.

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen