AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Sortieralgorithmus

Ein Thema von snears · begonnen am 6. Mai 2012 · letzter Beitrag vom 7. Mai 2012
Antwort Antwort
Seite 1 von 2  1 2   
snears

Registriert seit: 25. Jan 2010
51 Beiträge
 
#1

Sortieralgorithmus

  Alt 6. Mai 2012, 13:59
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
Wenn man bei einem Projekt nicht weiter kommt, einmal um das Haus rennen und wieder an das Projekt setzen...
  Mit Zitat antworten Zitat
Benutzerbild von Luckie
Luckie

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#2

AW: Sortieralgorithmus

  Alt 6. Mai 2012, 14:02
Probier es doch aus und guck, was passiert.
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
Benutzerbild von Gausi
Gausi

Registriert seit: 17. Jul 2005
844 Beiträge
 
Delphi 11 Alexandria
 
#3

AW: Sortieralgorithmus

  Alt 6. Mai 2012, 14:39
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.
The angels have the phone box.
  Mit Zitat antworten Zitat
snears

Registriert seit: 25. Jan 2010
51 Beiträge
 
#4

AW: Sortieralgorithmus

  Alt 6. Mai 2012, 15:37
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;
Wenn man bei einem Projekt nicht weiter kommt, einmal um das Haus rennen und wieder an das Projekt setzen...
  Mit Zitat antworten Zitat
Benutzerbild von Luckie
Luckie

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#5

AW: Sortieralgorithmus

  Alt 6. Mai 2012, 15:39
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.
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#6

AW: Sortieralgorithmus

  Alt 6. Mai 2012, 17:48
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.

Geändert von Delphi-Laie ( 6. Mai 2012 um 18:35 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Gausi
Gausi

Registriert seit: 17. Jul 2005
844 Beiträge
 
Delphi 11 Alexandria
 
#7

AW: Sortieralgorithmus

  Alt 6. Mai 2012, 18:13
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.
The angels have the phone box.
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#8

AW: Sortieralgorithmus

  Alt 6. Mai 2012, 21:37
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
  Mit Zitat antworten Zitat
Benutzerbild von implementation
implementation

Registriert seit: 5. Mai 2008
940 Beiträge
 
FreePascal / Lazarus
 
#9

AW: Sortieralgorithmus

  Alt 6. Mai 2012, 21:55
Ich kannte es bisher sogar nur mit äußerer While-Schleife, mit zwei For-Schleifen habe ich es bisher noch nie gesehen
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#10

AW: Sortieralgorithmus

  Alt 7. Mai 2012, 08:54
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.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 01:39 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz