Selection Sort hat Bugs...

[No0oB]

Hallo Leute.
Ich programmiere gerade ein Programm, welches zufällige Zahlen sortieren soll.
Bis jetzt hab ich BubbleSort und SelectionSort, bzw. ich meinte SelectionSort zu haben.
Vor kurzem habe ich jedoch folgenden Bug gefunden:
Bei erstem Hinsehen meint man, dass er korrekt sortiert hat, nur taucht ab und zu eine Zahl auf die nicht hingehört, also eine kleine Zahl, wo egtl. eine große stehen soll.

Hier ist der Code für die SelectionSort Prozedur

Delphi-Quellcode:

procedure TForm1.B_SelectionSortClick(Sender: TObject);
var i, j:longint;
var min:longint;
begin
  M_1.Clear;
  swapi := 0;
  for i:=1 to amount do begin
     min := i;
     for j:=i+1 to amount do begin
       if numbers[j] < numbers[min] then begin
        min := j;
       end;
     swapvals(numbers[min], numbers[i]);
     end;

  end;
  for i:=1 to amount do
    M_1.Lines.Add(IntToStr(i)+':  '+IntToStr(numbers[i]));
  L_vergleichei.Caption := IntToStr(swapi);
end;

Die Prozedur swapvals()

Delphi-Quellcode:

procedure swapvals(var val1, val2:longint);
var buff:longint;
begin
  buff := val1;
  val1 := val2;
  val2 := buff;
  inc(swapi);
end;

Globale Variablen

Delphi-Quellcode:

var
  Form1: TForm1;
  numbers :array [1..amount] of LongInt;
  swapi: longint = 0;

Ich hoffe mir kann geholfen werden.
Ggf. kann ich ja die .exe zum Download freigeben, falls meine Fehlerbeschreibung nicht sehr aufschlussreich ist.
Danke.
PS: Ich weiss nicht ob Delphi 7 Delphi.NET oder Delphi Win32 ist ...

[Klaus01]

Hallo,

Delphi7 ist Win32.

Damit Du ein wenig vergleichen kannst, hier ist ein SelectionSort
,das Memo Zeilen sortiert, zu finden: http://www.dsdt.info/tipps/?id=378

Grüße
Klaus

[marabu]

Herzlich willkommen in der Delphi-PRAXiS, NoOoB.

Zusätzlich zum Link von Klaus möchte ich dir noch zwei weitere Links an Herz legen: Daniel hat vor längerer Zeit einmal ein Tutorial verfasst, in dem verschiedene Sortierverfahren beispielhaft implementiert sind - und auch WikiPedia hat umfangreiche Informationen zu diesem Thema.

Zitat von NoOoB:

... bzw. ich meinte SelectionSort zu haben ...

Du hast einen event handler mit deinem Code bestückt. Besser ist es du verpackst deine Sortierverfahren in eine Funktion oder Prozedur. Im event handler OnClick() eines Button ist dein Code nur die Hälfte wert.

Freundliche Grüße vom marabu


PS: In deinem Code werden die Grenzen für die innere und äußere Schleife falsch gesetzt und die Zahl der notwendigen Vertauschungen ist unnötig hoch.

Delphi-Quellcode:

function SelectionSort(var ida: TIntegerDynArray): Integer;
var
  iMin, iOuter, iInner, iTemp, iCount: Integer;
begin
  iCount := 0;
  for iOuter := Low(ida) To Pred(High(ida)) do
  begin
    iMin := iOuter;
    for iInner := Succ(iOuter) to High(ida) Do
      if ida[iInner] < ida[iMin] then 
        iMin := iInner;
    if iMin <> iOuter then
    begin
      iTemp := ida[iMin];
      ida[iMin] := ida[iOuter];
      ida[iOuter] := iTemp;
      Inc(iCount);
    end
  end;
  Result := iCount;
end;

Dieser Code ist nur getippt und nicht getestet.

[No0oB]

Zitat von marabu:

Du hast einen event handler mit deinem Code bestückt. Besser ist es du verpackst deine Sortierverfahren in eine Funktion oder Prozedur. Im event handler OnClick() eines Button ist dein Code nur die Hälfte wert.

Danke für die Tipps, allerdings hab ich eine Frage.
Ich wollte zuerst eine solche Prozedur schreiben, allerdings kann dann nicht auf das Memofeld namens M_1 zugegriffen werden.
Kann man das beheben oder soll ich den Output immer bein onClick() hinsetzen?

[marabu]

Zitat von No0oB:

... soll ich den Output immer bein onClick() hinsetzen?

Genau so solltest du es machen. Die Funktion SelectionSort() liefert dir die Zahl der Vertauschungen zurück und im Ereignis OnClick() deines Buttons kümmerst du dich um die Anzeige dieser Zahl. So funktioniert die Trennung von Darstellung und Funktionalität.

Freundliche Grüße

marabu

[No0oB]

Vielen Dank für die Hilfe marabu, das Tutorial von Daniel hab ich mir schon angeguckt, allerdings habe ich dort nicht die Variablendeklarationen gefunden.
Allerdings noch eine Frage zu deinem Code: Was bewirkt denn dieses Pred() ?
Edit: hat sich erledigt

Zitat:

Die Funktion gibt den Vorgänger des Arguments zurück.