Hilfe keine Ahnung von Quicksort!!! Bubblesort zu Quicksort!

Hacky_sack · Hält's aus hier Beiträge: 2

Hallo,
Ich muss wegender Schule ein Sortierprogramm gestallten, was mit Quicksort läuft.
Ich find aber bis jetzt kein verständigen Quelltext. Vielleicht könnt ihr mir da helfen und mein Quelltext so verändern, dass Quicksort das sortiert und nicht Bubblesort?

Schon mal vielen Dank!!

mfg Hacky_sack

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:

unit Feld;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, StdCtrls, Buttons;
const max=25;

type
  x_feld=array[1..max] of char;
  TForm1 = class(TForm)
    StringGrid1: TStringGrid;
    BitBtn1: TBitBtn;
    Button1: TButton;
    Button2: TButton;
    procedure Feldbelegen;
    procedure Anzeigen(zelle:integer);
    procedure FormCreate(Sender: TObject);
    procedure BitBtn1Click(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  x:x_feld;

implementation

{$R *.dfm}

procedure TForm1.Feldbelegen;
var hilf:integer;
begin
randomize;
for hilf:=1 to max do
    x[hilf]:=char(random(26)+65);
end;

procedure TForm1.Anzeigen(zelle:integer);
var lauf2:integer;
begin
for lauf2:=1 to max do
  begin
    stringgrid1.Cells[0,lauf2]:=inttostr(lauf2);
    stringgrid1.cells[zelle,lauf2]:=x[lauf2];
  end;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
stringgrid1.ColWidths[0]:=70;
stringgrid1.ColWidths[1]:=80;
stringgrid1.ColWidths[2]:=80;
stringgrid1.Cells[0,0]:='Nummer';
stringgrid1.Cells[1,0]:='unsortiert';
stringgrid1.Cells[2,0]:='sortiert';
feldbelegen;
anzeigen(1);
end;

procedure TForm1.BitBtn1Click(Sender: TObject);
begin
close;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i, j : integer;
    wert : char;

begin
for i:= max downto 2 do
  for j:= 2 to i do
    if x[j-1]>x[j] then
      begin
      wert   := x[j];
      x[j]   := x[j-1];
      x[j-1] := wert;
      end;
      anzeigen(2);
end;

procedure TForm1.Button2Click(Sender: TObject);
var i, j : integer;
    wert : char;

begin
for i:= max downto 2 do
  for j:= 2 to i do
    if x[j-1]<x[j] then
      begin
      wert   := x[j];
      x[j]   := x[j-1];
      x[j-1] := wert;
      end;
      anzeigen(2);
end;

end.

Moderiert von raziel: Code- durch Delphi-Tags ersetzt

Shaddow89 · Hält's aus hier Beiträge: 15

Quicksort ist weiß Gott nicht schwer, das bekommst du allein hin. Hier wies funktioniert.
Quicksort lässt sich am besten Rekursiv erzeugen.

Die übergebene Zahlenfolge wird in der Mitte geteilt. Die Mitte (evtl. eins links oder rechts von der mitte bei gerade Zahlenanzahl) wird als referenzwert x genommen. Danach wird die linke Zahlenfolge durchlaufen und mit x verglichen. kleinere kommen nach LinksLinks und größere nach LinksRechts. Das wird solange wiederholt, bis die länge der Folge bei 1 liegt und sortiert ist. Rechts natuerlich immer das selbe, aber das macht die Rekursivitaet ja gleich mit.
Es ensteht am ende praktisch ne Baumstruktur

13452
/ \
132 45
/ \ / \
12 3 4 5
/ \
1 2

Tadaaa ^^

Hacky_sack · Hält's aus hier Beiträge: 2

Wenn ich es wüsste, dann würd ich ja nicht fragen.
Ich würd ja erstmal gern meinem Quelltext verändert sehen, damit ich Quicksort an ihm kapiere.Ich weiß auch nicht genau wie die Ausgabe funktioniert.

raziel · Verfasst: Do 05.10.06 08:12

Moin,

morgen hab ich Vordiplomsprüfung Informatik, weiß also wie Quicksort funktioniert, aber deine Beschreibung hab ich ehrlich gesagt nicht verstanden

Mal ein Versuch von mir (etwas andere Vorgehensweise):
Das jeweils erste Element deiner Menge sortierst du richtig ein und gehst wie folgt vor: Erst läufst du vom 2. Element aus nach rechts bis du ein größeres Element findest und merkst dir seine Position. Anschließend läufst Du vom letzten Element aus nach links bis du ein Element hast, das kleiner ist als dein erstes Element und merkst dir auch seine Position. Diese beiden Elemente vertauscht du nun. Von da aus gehst du wieder weiter nach rechts bzw. links und vertauscht weiter größere elemente mit kleineren, solange bis die beiden Positionen sich treffen. Nun vertauscht du noch das erste Element mit einer der beiden Positionen und hast somit dein erstes Element richtig einsortiert: links von dem Element sind nur noch Zahlen, die kleiner sind und rechts davon nur noch solche, die größer sind.

Dafür hast du jetzt zwei neue (Teil-)Mengen, die es gilt zu sortieren, aber da rufst du einfach nochmal Quicksort für auf

Bsp: 37249

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

 .  .   < Durchlauf
37249
^       < einzusortierendes Element

 . .
37249
^

 ..                         ..
37249  -- vertauschen -->  32749
^                          ^

 .
32749  -- fertig, vertauschen --> 23749
^                                  ^

Nun hast du 2 Teilmengen: {2} und {7,4,9}, die gilt es weiter zu sortieren genau wie oben (ok, bei der Menge {2} gibts nicht viel zu sortieren :lol:

)

Zitat:

Ich würd ja erstmal gern meinem Quelltext verändert sehen, damit ich Quicksort an ihm kapiere.Ich weiß auch nicht genau wie die Ausgabe funktioniert.

Nein, Quicksort ist nicht schwer, wenn du willst dass hier jemand deine Hausaufgaben macht, verschieb ichs in die Jobbörse...

_________________
JSXGraph

Narses · Verfasst: Do 05.10.06 08:14

Moin!

Und hier gibt´s den Code.

Aber c&p wird hier nicht unterstützt, mußt du also schon selbst integrieren.

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

Quake User · Beiträge: 159

Du wirst nicht programmieren lernen, wenn Du nicht programmieren lernst.

Falls Du KOPIEREN lernen willst, hier eine Anleitung:
de.wikipedia.org/wiki/Copy_&_Paste

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme