Quicksort

Für Fragen von Einsteigern und Programmieranfängern...

Quicksort

Beitragvon Rawi » 19. Apr 2018, 15:37 Quicksort

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
Rawi
 
Beiträge: 14
Registriert: 31. Mär 2018, 16:39

Beitragvon Niesi » 19. Apr 2018, 17:15 Re: Quicksort

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
Niesi
 
Beiträge: 37
Registriert: 26. Jun 2016, 18:44

Beitragvon Mathias » 19. Apr 2018, 17:17 Re: Quicksort

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 gün
Mit Java und C/C++ sehe ich rot
Mathias
 
Beiträge: 3781
Registriert: 2. Jan 2014, 17:21
Wohnort: Schweiz
OS, Lazarus, FPC: Linux (die neusten Trunc) | 
CPU-Target: 64Bit
Nach oben

Beitragvon Socke » 19. Apr 2018, 19:11 Re: Quicksort

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 23. Apr 2018, 16:18, insgesamt 1-mal geändert.
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein
Socke
 
Beiträge: 2484
Registriert: 22. Jul 2008, 18:27
Wohnort: Köln
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 8.1/Debian GNU/Linux/Raspbian/openSUSE | 
CPU-Target: 32bit x86 armhf
Nach oben

Beitragvon Rawi » 20. Apr 2018, 17:36 Re: Quicksort

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: 31. Mär 2018, 16:39

Beitragvon Rawi » 20. Apr 2018, 17:38 Re: Quicksort

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.
Rawi
 
Beiträge: 14
Registriert: 31. Mär 2018, 16:39

Beitragvon Mathias » 20. Apr 2018, 18:00 Re: Quicksort

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 gün
Mit Java und C/C++ sehe ich rot
Mathias
 
Beiträge: 3781
Registriert: 2. Jan 2014, 17:21
Wohnort: Schweiz
OS, Lazarus, FPC: Linux (die neusten Trunc) | 
CPU-Target: 64Bit
Nach oben

Beitragvon wp_xyz » 20. Apr 2018, 20:05 Re: Quicksort

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?
wp_xyz
 
Beiträge: 2460
Registriert: 8. Apr 2011, 08:01

Beitragvon Rawi » 20. Apr 2018, 22:47 Re: Quicksort

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
Rawi
 
Beiträge: 14
Registriert: 31. Mär 2018, 16:39

Beitragvon AndreasMR » 21. Apr 2018, 18:47 Re: Quicksort

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
AndreasMR
 
Beiträge: 84
Registriert: 4. Aug 2015, 14:29
OS, Lazarus, FPC: Linux, Raspbian, Windows | 
CPU-Target: 64/32 Bit
Nach oben

Beitragvon mintpc » 21. Apr 2018, 21:49 Re: Quicksort

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: 121
Registriert: 6. Sep 2010, 17:39
Wohnort: Mailand
OS, Lazarus, FPC: Win 7 (L 1.6 FPC 3.0.0) | 
CPU-Target: Win 7
Nach oben

Beitragvon mintpc » 21. Apr 2018, 21:50 Re: Quicksort

Ups. Falscher Knopf.
mintpc
 
Beiträge: 121
Registriert: 6. Sep 2010, 17:39
Wohnort: Mailand
OS, Lazarus, FPC: Win 7 (L 1.6 FPC 3.0.0) | 
CPU-Target: Win 7
Nach oben

Beitragvon Thandor » 22. Apr 2018, 01:49 Re: Quicksort

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.
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Thandor
 
Beiträge: 113
Registriert: 30. Jan 2010, 18:17
Wohnort: Berlin
OS, Lazarus, FPC: Windows 10 64Bit/ lazarus 1.6 mit FPC 3.0.0 (32Bit) | 
CPU-Target: 64Bit
Nach oben

Beitragvon Mathias » 22. Apr 2018, 16:16 Re: Quicksort


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 gün
Mit Java und C/C++ sehe ich rot
Mathias
 
Beiträge: 3781
Registriert: 2. Jan 2014, 17:21
Wohnort: Schweiz
OS, Lazarus, FPC: Linux (die neusten Trunc) | 
CPU-Target: 64Bit
Nach oben

Beitragvon Niesi » 23. Apr 2018, 06:42 Re: Quicksort

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 ...
Niesi
 
Beiträge: 37
Registriert: 26. Jun 2016, 18:44

» Weitere Beiträge siehe nächste Seite »
Nächste

Zurück zu Einsteigerfragen



Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

porpoises-institution
accuracy-worried