Quicksort

Für Fragen von Einsteigern und Programmieranfängern...
Rawi
Beiträge: 14
Registriert: Sa 31. Mär 2018, 17:39

Quicksort

Beitrag von Rawi »

Hi zusammen,

ich soll in der Schule einen Vortrag über die Sortiermethode Quicksort halten.
Dazu soll ich ein Programm (mit Quellcode) zeigen, dass den Quicksort-Algorithmus durchführt. Das Programm sollte ich nicht selber schreiben (, weil es scheinbar recht kompliziert ist ?!), sondern ich soll es mir "einfach" aus dem Internet holen.

Hat jemand von euch zufällig ein solches Programm schon mal geschrieben, sodass er es mir zur Verfügung stellen kann?

7 Zahlen sortieren würde ausreichen. Animationen sind nicht notwendig. Man soll bloß jeden Schritt sehen. (Also wenn z.B. 2 Werte von 2 Edits (so kann man das doch machen oder???) vertauscht werden).

Oder Kennt ihr vllt. eine Internetseite, wo man an solche Programme kommt?

Ich würde den Algorithmus auch selber schreiben. Dafür bräuchte ich dann aber vllt. eine asuführliche Erklärung, weil ich vieles nicht verstehe, was ich in einigen Algorithmen online gelesen habe...

Danke

Benutzeravatar
Niesi
Lazarusforum e. V.
Beiträge: 331
Registriert: So 26. Jun 2016, 19:44
OS, Lazarus, FPC: Linux Mint Cinnamon (Windows wenn notwendig), Lazarus 3.0 FPC 3.3.1

Re: Quicksort

Beitrag von Niesi »

Rawi hat geschrieben:Hi zusammen,

ich soll in der Schule einen Vortrag über die Sortiermethode Quicksort halten.
Dazu soll ich ein Programm (mit Quellcode) zeigen, dass den Quicksort-Algorithmus durchführt. Das Programm sollte ich nicht selber schreiben (, weil es scheinbar recht kompliziert ist ?!), sondern ich soll es mir "einfach" aus dem Internet holen.

Hat jemand von euch zufällig ein solches Programm schon mal geschrieben, sodass er es mir zur Verfügung stellen kann?

7 Zahlen sortieren würde ausreichen. Animationen sind nicht notwendig. Man soll bloß jeden Schritt sehen. (Also wenn z.B. 2 Werte von 2 Edits (so kann man das doch machen oder???) vertauscht werden).

Oder Kennt ihr vllt. eine Internetseite, wo man an solche Programme kommt?

Ich würde den Algorithmus auch selber schreiben. Dafür bräuchte ich dann aber vllt. eine asuführliche Erklärung, weil ich vieles nicht verstehe, was ich in einigen Algorithmen online gelesen habe...

Danke



Hallo Rawi,

was ist denn passiert? Ist Dein Google kaputt?

Versuch mal das da: http://www.gidf.de/%E2%80%8E

Herzlichen Gruß
Niesi
Wissen ist das einzige Gut, das sich vermehrt, wenn es geteilt wird ...

Mathias
Beiträge: 6160
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Quicksort

Beitrag von Mathias »

Ein bisschen googeln und du bekommst die Lösung fertig präsentiert:
https://forum.lazarus.freepascal.org/in ... ic=31729.0

Inklusive eine Beschreibung in deutsch:
https://de.wikipedia.org/wiki/Quicksort
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Socke
Lazarusforum e. V.
Beiträge: 3158
Registriert: Di 22. Jul 2008, 19:27
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 10/Linux/Raspbian/openSUSE
CPU-Target: 32bit x86 armhf
Wohnort: Köln
Kontaktdaten:

Re: Quicksort

Beitrag von Socke »

Ich finde ja diese Anleitung sehr schön: KWICK SÖRT

Sortieralgorithem kann man auch Tanzen: Quick-sort with Hungarian (Küküllőmenti legényes) folk dance - mach deinen Vortrag doch interaktiv :D
Zuletzt geändert von Socke am Mo 23. Apr 2018, 17:18, insgesamt 1-mal geändert.
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein

Rawi
Beiträge: 14
Registriert: Sa 31. Mär 2018, 17:39

Re: Quicksort

Beitrag von Rawi »

Niesi hat geschrieben:
Rawi hat geschrieben:Hi zusammen,

ich soll in der Schule einen Vortrag über die Sortiermethode Quicksort halten.
Dazu soll ich ein Programm (mit Quellcode) zeigen, dass den Quicksort-Algorithmus durchführt. Das Programm sollte ich nicht selber schreiben (, weil es scheinbar recht kompliziert ist ?!), sondern ich soll es mir "einfach" aus dem Internet holen.

Hat jemand von euch zufällig ein solches Programm schon mal geschrieben, sodass er es mir zur Verfügung stellen kann?

7 Zahlen sortieren würde ausreichen. Animationen sind nicht notwendig. Man soll bloß jeden Schritt sehen. (Also wenn z.B. 2 Werte von 2 Edits (so kann man das doch machen oder???) vertauscht werden).

Oder Kennt ihr vllt. eine Internetseite, wo man an solche Programme kommt?

Ich würde den Algorithmus auch selber schreiben. Dafür bräuchte ich dann aber vllt. eine asuführliche Erklärung, weil ich vieles nicht verstehe, was ich in einigen Algorithmen online gelesen habe...

Danke



Hallo Rawi,

was ist denn passiert? Ist Dein Google kaputt?

Versuch mal das da: http://www.gidf.de/%E2%80%8E

Herzlichen Gruß
Niesi



Leider absolut nicht hilfreich. Eher asozial. Deshalb leider kein Danke von mir an dich.

Rawi
Beiträge: 14
Registriert: Sa 31. Mär 2018, 17:39

Re: Quicksort

Beitrag von Rawi »

Mathias hat geschrieben:Ein bisschen googeln und du bekommst die Lösung fertig präsentiert:
https://forum.lazarus.freepascal.org/in ... ic=31729.0

Inklusive eine Beschreibung in deutsch:
https://de.wikipedia.org/wiki/Quicksort



Danke, das habe ich auch schon gefunden. Leider verstehe ich nicht, an welcher Stelle die Werte-"Eingabe" erfolgt. Also wie er z.B. 100 Werte Quicksortieren will. Auch kann ich leider mit WriteIn und Read wenig anfangen.

Mathias
Beiträge: 6160
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Quicksort

Beitrag von Mathias »

Ich gebe es zu, das Muster auf dem Wiki ist nicht so der Hit.

Auch kann ich leider mit WriteIn und Read wenig anfangen.

Mit Read, kann man eine Eingabe auf der Konsole empfangen, und mit Writeln, kann man auf der Konsole etwas ausgeben.

Für Write(Ln) habe mal ein Wiki geschrieben: http://wiki.freepascal.org/Write/de

Das mit dem Read kannst du dir erst mal sparen, und kannst direkt die Zahlen in der Source erzeugen.

Code: Alles auswählen

begin
  Randomize; // Man will nicht immer die gleichen Zufalls-Zahlen.
  Len := 20;
  SetLength(AI, Len);
  for I := Low(AI) to High(AI) do begin
    AI[I] := Random(len)// Zufallszahlen der Array zuordnen.
  end;
 
  QuickSort(AI, Low(AI), High(AI));

Ich hoffe, das dir dies weiter hilft.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: Quicksort

Beitrag von wp_xyz »

Rawi hat geschrieben:Leider absolut nicht hilfreich. Eher asozial. Deshalb leider kein Danke von mir an dich.

Was ist das denn für eine Einstellung?

Rawi
Beiträge: 14
Registriert: Sa 31. Mär 2018, 17:39

Re: Quicksort

Beitrag von Rawi »

wp_xyz hat geschrieben:
Rawi hat geschrieben:Leider absolut nicht hilfreich. Eher asozial. Deshalb leider kein Danke von mir an dich.

Was ist das denn für eine Einstellung?


Nun, ich war ein wenig ungehalten darüber, dass man auf meine ehrlich gemeinte Frage mit so einer beleidigenden Antwort antwortet.
Danach zu fragen, ob ich Google genutzt habe, ist ja verständlich, wenn auch nicht wirklich sinnvoll, weil ich ja eine Frage nicht stellen würde, wenn mein Problem mit simplem Googlen gelöst wäre. Ich bin nun mal Einsteiger, deswegen sind viele Quellcodes für mich noch sehr unverständlich und ich muss nachfragen. (Dazu dient dieses Forum hier doch auch unter anderem?! Oder bin ich hier falsch???)
Mich dann aber auf eine Seite weiterzuleiten, die mir ganz offensichtlich sagt, dass ich faul und dumm sei und nur andere Leute nerven will, halte ich für sehr unangemessen.

Ich habe mich vielleicht nicht fein und höflich ausgedrückt, was aber bei so einem Angriff (meiner Meinung nach) versätndlich ist...

LG

AndreasMR
Beiträge: 98
Registriert: Di 4. Aug 2015, 15:29
OS, Lazarus, FPC: Linux, Raspbian, Windows
CPU-Target: 64/32 Bit

Re: Quicksort

Beitrag von AndreasMR »

Hallo Rawi,

die Erlernen einer Programmiersprache setzt voraus, dass man sich erst einmal selber damit beschäftigt. Sich also die Grundlagen aneignet.
Dazu gehören solche Dinge wie WriteLn() und Read(). Zu den Grundlagen gehört ganz sicher kein Quicksort-Algorithmus - oder gar diesen zu verstehen oder verstehen zu wollen.

Ich habe das erste Mal 1982 von Quicksort gehört, den damals in der CHIP veröffentlichten Algorithmus in BASIC und später auch in andere Programmiersprachen übertragen.

Quicksort gehört wohl zu den Algorithmen, der am häufigsten in diverse Programmiersprachen übertragen wurde. Du findet da also alles, was irgendjemand von Dir darüber wissen möchte. Minimale Durchläufe, maximale Durchläufe, mittlere Durchläufe, Verhalten bei bereits sortierten Daten und solches bei umgekehrt sortierten Daten, Änderung dieser Kennzahlen bei Verdopplung der Datenmenge, ..., Vergleiche mit anderen Sortier-Algorithmen (die im Extremfall leicht nachvollziehbar und deswegen auch langsamer sind)


Wenn Du Dich dann in etwas hinein gekniet hast, verschiedenstes ausprobiert hast, aber alle Deine Versuche gescheitert sind, genau dann ist ein Computerforum für Dich da! Und dann würde Dir auch jeder, der eine Antwort kennt, gerne helfen wollen.

Aber was Du hier verlangst, ist dass jemand Dir Deine Schulaufgaben macht. Ich kann mir nicht vorstellen, dass Dein Musik-Lehrer ein Referat zu Quicksort hören will - es wird wohl Dein Informatik-Lehrer sein. Und dann - das Schuljahr ist ja bald zu Ende - solltest Du deutlich mehr gelernt haben als dass Dir WriteLn) und Read() nichts sagt.

Übrigens, ein Computer-Forum funktioniert so, dass man zeigt, was man selber probiert hat. Das setzt voraus, dass man sich mal damit (Programmiersprache, Algorithmus, Datenerzeugung) beschäftigt hat. Was davon hat funktioniert, woran hängt's noch? Dass man auch mal einen Code zeigt. Ganz sicher wird sich keiner hinsetzen und für Dich Beiträge recherchieren und altersgerecht aufbereiten, damit Du eine tolle Note bekommst.
Stell Dir mal vor, ein guter Mitschüler von Dir erledigt die Aufgabe mit viel eigenem Aufwand, macht die Sache so gut, wie es die Gegebenheiten ermöglichen. Und dann kommst Du. Die Lösung von einem Profi hier aus dem Forum erarbeitet. Alles tippi-toppi. Der Lehrer ist begeistert. Du bekommst die tolle Note. Fachlich weißt Du aber weiterhin nichts. Und dein guter Mitschüler mit einer gehörigen Portion Eigeninitiative bekommt eine schlechtere Note als Du.

Gerecht geht anders...


Denk mal drüber nach! Nicht für die Schule lernt man sondern fürs Leben...


Beste Grüße

Andreas
Ubuntu 14.04 LTS / Raspbian / Windows: Lazarus ab 0.9 bis 3.0

mintpc
Beiträge: 124
Registriert: Mo 6. Sep 2010, 18:39
OS, Lazarus, FPC: Win 7 (L 1.6 FPC 3.0.0)
CPU-Target: Win 7
Wohnort: Mailand

Re: Quicksort

Beitrag von mintpc »

Hier: http://www.martinjakobs.de/pages/sortieralgorithmen.php --> Modul 4

Fertig für die Schule aufbereitet.

Und der absolute Kracher als Ergänzung für den Schulvortrag: Modul 0 und Modul 7

Gruß
mintpc

P.S.: Davon abgesehen halte ich es für "ungeschickt", Quicksort als Schülerreferat an
einen Schüler zu vergeben, der vom Fach wenig Ahnung hat. Gib deinem Lehrer das
Arbeitsblatt aus Modul 4, dann kann er selbst damit eine ganz tolle Stunde zu Quicksort
machen (keine Ironie, ist wahr).

mintpc
Beiträge: 124
Registriert: Mo 6. Sep 2010, 18:39
OS, Lazarus, FPC: Win 7 (L 1.6 FPC 3.0.0)
CPU-Target: Win 7
Wohnort: Mailand

Re: Quicksort

Beitrag von mintpc »

Ups. Falscher Knopf.

Thandor
Beiträge: 153
Registriert: Sa 30. Jan 2010, 18:17
OS, Lazarus, FPC: Windows 10 64Bit/ lazarus 3.0 mit FPC 3.2.2 (32Bit + 64bit)
CPU-Target: 64Bit
Wohnort: Berlin

Re: Quicksort

Beitrag von Thandor »

Ich gehe denke, dass du uns hier die Wahrheit sagst...

Ich kann dir ein Quicksort geben, aber ich glaube das würde dich eventuell nur verwirren.
Ich habe hier versucht das möglichst allgemein zu halten, deswegen Pointerbasierend (Speicheradressen), deswegen etwas komplizierter als im Grunde nötig.

Zum Glück habe ich damals extrem viel kommentiert, somit hast du eventuell doch noch eine Chance den Code zu verstehen, wenn du dich intensiev damit beschäftigst.
Dateianhänge
stdqSort.pas
(8.14 KiB) 114-mal heruntergeladen

Mathias
Beiträge: 6160
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Quicksort

Beitrag von Mathias »


So was motiviert einem ja riesig zum Coden. Da war jedes Turbo-Pascal-Buch das ich gekauft hatte um einiges besser.

Noch ein sehr stark vereinfachter Quick-Sort:

Code: Alles auswählen

program Project1;
 
  procedure QuickSort(var ia: array of integer; ALo, AHi: integer);
  var
    Lo, Hi, Pivot, T: integer;
  begin
    Lo := ALo;
    Hi := AHi;
    Pivot := ia[(Lo + Hi) div 2];
    repeat
      while ia[Lo] < Pivot do begin
        Inc(Lo);
      end;
      while ia[Hi] > Pivot do begin
        Dec(Hi);
      end;
      if Lo <= Hi then begin
        T := ia[Lo];
        ia[Lo] := ia[Hi];
        ia[Hi] := T;
        Inc(Lo);
        Dec(Hi);
      end;
    until Lo > Hi;
    if Hi > ALo then begin
      QuickSort(ia, ALo, Hi);
    end;
    if Lo < AHi then begin
      QuickSort(ia, Lo, AHi);
    end;
  end;
 
var
  ia: array of integer;
  i: integer;
  Len: integer;
begin
  Randomize;
  Len := 2000;
  SetLength(ia, Len);
  for i := 0 to Len - 1 do begin
    ia[i] := Random(len);
  end;
 
  QuickSort(ia, 0, Len - 1);
 
  for i := 0 to Len - 1 do begin
    Writeln(i:8, '.', ia[i]: 8);
  end;
  Readln;
end.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Benutzeravatar
Niesi
Lazarusforum e. V.
Beiträge: 331
Registriert: So 26. Jun 2016, 19:44
OS, Lazarus, FPC: Linux Mint Cinnamon (Windows wenn notwendig), Lazarus 3.0 FPC 3.3.1

Re: Quicksort

Beitrag von Niesi »

Rawi hat geschrieben:
Niesi hat geschrieben:
Rawi hat geschrieben:Hi zusammen,

ich soll in der Schule einen Vortrag über die Sortiermethode Quicksort halten.
Dazu soll ich ein Programm (mit Quellcode) zeigen, dass den Quicksort-Algorithmus durchführt. Das Programm sollte ich nicht selber schreiben (, weil es scheinbar recht kompliziert ist ?!), sondern ich soll es mir "einfach" aus dem Internet holen.

Hat jemand von euch zufällig ein solches Programm schon mal geschrieben, sodass er es mir zur Verfügung stellen kann?

7 Zahlen sortieren würde ausreichen. Animationen sind nicht notwendig. Man soll bloß jeden Schritt sehen. (Also wenn z.B. 2 Werte von 2 Edits (so kann man das doch machen oder???) vertauscht werden).

Oder Kennt ihr vllt. eine Internetseite, wo man an solche Programme kommt?

Ich würde den Algorithmus auch selber schreiben. Dafür bräuchte ich dann aber vllt. eine asuführliche Erklärung, weil ich vieles nicht verstehe, was ich in einigen Algorithmen online gelesen habe...

Danke



Hallo Rawi,

was ist denn passiert? Ist Dein Google kaputt?

Versuch mal das da: http://www.gidf.de/%E2%80%8E

Herzlichen Gruß
Niesi



Leider absolut nicht hilfreich. Eher asozial. Deshalb leider kein Danke von mir an dich.



Auch wenn es AndreasMR bereits geschrieben hat: Das Forum ist nicht dazu da, Deine Hausaufgaben zu erledigen - dann lernst Du nämlich nichts.
Wenn Du konkrete Fragen hast, dann gerne, aber so NICHT.

Und des weiteren darfst Du gerne mal darüber nachdenken, wer von uns beiden sich "asozial" verhält: Der, der klar einen Hinweis auf die Suchmaschinen im Internet gibt oder der, der sich auf Kosten anderer durch das Leben mogeln will.

Und jetzt sie zu, dass Du die Suchmaschinen nutzt, Dir etwas ERARBEITEST und dann den Erfolg davon spürst. Ansonsten solltest Du die Programmierung lieber lassen ...
Wissen ist das einzige Gut, das sich vermehrt, wenn es geteilt wird ...

Antworten