Sortieralgorithmus

[snears]

Ich habe eine Frage und zwar würde ich gerne wissen was passiert wenn ein ein sortieralgorithmus auf ein bereits sortiertes Feld angewandt wird? Und außerdem würde ich gerne wissen, wie bei folgendem Quelltext eine äußere Schleife den Sortiervorgagn automatisiert.

Code:

procedure TForm1.Button1.Click(Sender: TObject);
var i:integer;
begin
for i:= 1 to laenge -1 do begin
 if meinFeld[i]> meinFeld[i+1] then begin
  Tausch(meinFeld[i], meinFeld[i+1]);
end;
end;
end;

Ich danke euch schonmal im voraus für die Antworten

[Luckie]

Probier es doch aus und guck, was passiert.

[Gausi]

Ein Sortieralgorithmus sortiert. Wenn die Eingabe schon sortiert ist, wird trotzdem sortiert. Je nach Sortieralgorithmus geht das dann schneller oder auch nicht schneller gegenüber einer unsortierten Folge.

Insertsort oder Bubblesort nutzen die Vorsortierung und sind schneller fertig. Selectionsort oder Quicksort können die Sortierung nicht erkennen und brauchen im wesentlichen genauso lang wie bei einer unsortierten Folge.

[snears]

außerdem würde ich gerne wissen, wie bei folgendem Quelltext eine äußere Schleife den Sortiervorgagn automatisiert.

Code:

procedure TForm1.Button1.Click(Sender: TObject);
var i:integer;
begin
for i:= 1 to laenge -1 do begin
 if meinFeld[i]> meinFeld[i+1] then begin
  Tausch(meinFeld[i], meinFeld[i+1]);
end;
end;
end;

[Luckie]

Zitat von snears:

außerdem würde ich gerne wissen, wie bei folgendem Quelltext eine äußere Schleife den Sortiervorgagn automatisiert.

Code:

procedure TForm1.Button1.Click(Sender: TObject);
var i:integer;
begin
for i:= 1 to laenge -1 do begin
 if meinFeld[i]> meinFeld[i+1] then begin
  Tausch(meinFeld[i], meinFeld[i+1]);
end;
end;
end;

Stichwort Bubblesort.

[Delphi-Laie]

Zitat von snears:

Ich habe eine Frage und zwar würde ich gerne wissen was passiert wenn ein ein sortieralgorithmus auf ein bereits sortiertes Feld angewandt wird?

Diese Eigenschaft, auf (Vor-)Sortierungen gegenüber völlig unsortierten/-geordneten Mengen mit einer merklichen Laufzeitverkürzung zu reagieren, nennt sich Adaptivität.

Schneller werden alle Sortieralgorithmen, die auf Vergleichen und vor allem (weil in diesem Kontext wichtig) Vertauschungen basieren, schon deshalb geringfügig, weil die Vertauschungen weniger werden oder gar entfallen. Andere Sortieralgorithmen, die nicht auf Vergleichen beruhen, haben m.E. überhaupt nichts von einer (Vor-)Sortierung, die sind immer gleich schnell. Doch die fehlenden Vertauschungen allein reizen das Beschleunigungspotential nicht immer aus, d.h., Adaptivität ist mehr.

Daß Bubblesort per se adaptiv ist, ist allerdings falsch. Vielmehr muß ein etwas höherer Entwicklungs- und Programmieraufwand betrieben werden, um ihn für (vor-)sortierte Mengen merklich zu beschleunigen. In meinem "Sortierkino" (auch hier im Forum zu finden) machte ich Bubblesort adaptiv, ließ aber den originalen - und bezüglich der Adaptivität eben völlig "unintelligenten" - Quellcode auskommentiert dort stehen. Einfach mal beides ausprobieren.

[Gausi]

Zitat von Delphi-Laie:

Daß Bubblesort per se adaptiv ist, ist allerdings falsch.

Ich meine die Bubblesort-Variante mit der äußeren "While-getauscht-do"-Schleife. Die bricht nach einem Durchlauf dann ab. Die Variante mit zwei for-Schleifen ist ja komplett Banane, die hab ich hier unter den Tisch fallen lassen.

[Furtbichler]

Zitat von Gausi:

Die Variante mit zwei for-Schleifen ist ja komplett Banane, die hab ich hier unter den Tisch fallen lassen.

Ich möchte jetzt keinen Contest entfachen, aber wenn ich Bubblesort irgendwo verwende, dann mit zwei For-Schleifen. Das ist imho kompakter und es ist eh Banane, weil ich das nur für sehr kleine Arrays einsetze.

Straight insertion wäre noch schneller, aber .. wie gesagt: Krumme gelbe Frucht.

Die äußere While-Schleife ist vielleicht sogar auch im Mittel schneller, aber -damned- ich kann sie mir einfach nicht merken

[implementation]

Ich kannte es bisher sogar nur mit äußerer While-Schleife, mit zwei For-Schleifen habe ich es bisher noch nie gesehen

[Furtbichler]

Zitat von implementation:

Ich kannte es bisher sogar nur mit äußerer While-Schleife, mit zwei For-Schleifen habe ich es bisher noch nie gesehen

Delphi-Quellcode:

For i:=1 to n-1 do
  for j:=i+1 to n do
    SwapIfGreater(a,i,j);

Das kann ich mir merken.