Sortieralgorithmen - Array oder Verkettete Liste

Marco D. · Verfasst: Fr 02.03.07 22:20

Für den Info-Unterricht sollen wir (die, die nicht erst lernen müssen, wie man ein Label auf die Form zieht :mrgreen:

) mit Sortieralgorithmen auseinandersetzen. An sich ist das ja nicht das Problem.
Nur eine Frage habe ich bezüglich der Performance (also der Schnelligkeit). Macht sich da ein Array oder eine verkettete Liste besser?

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

Gausi · Verfasst: Fr 02.03.07 22:28

Da man bei Arrays freien Zugriff auf beliebige Elemente in konstanter Zeit hat (über den Index), sind bei Sortierungen Arrays auf jeden Fall den Listen vorzuziehen. Einige Verfahren lassen sich zwar genauso gut über Listen machen (z.B. "Bubblesort" oder auch "Sortieren durch Einfügen"), aber die schnelleren Verfahren wie Quicksort benötigen Arrays. Mit Listen wär das zu friemelig, würde ich sagen.

_________________
We are, we were and will not be.

Marco D. · Verfasst: Fr 02.03.07 22:32

Aber bei Listen kann man schnell umsortieren, da man dort nur die Zeiger ändern brauch. Und irgendwo hatte ich gelesen, dass bei Arrays das gesamte Array im Speicher umkopiert werden muss.

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

Gausi · Verfasst: Fr 02.03.07 22:36

Ein Element irgendwo einfügen geht mit Listen schneller, ja. Allerdings kann man bei Listen nicht "wild umherspringen", sondern kann immer nur auf das nächste/vorige Element zugreifen. Wenn das Array einmal komplett gefüllt ist, und nur vertauscht wird (und quasi alle Verfahren arbeiten nur mit Vertauschungen, bzw. wird das als Maß für die Laufzeit genommen), sind Arrays nicht weniger effizient als Listen. Und sie bieten als Vorteil den schnellen Zugriff über Indizes, was bei einer Liste nicht möglich ist.

_________________
We are, we were and will not be.

Marco D. · Verfasst: Fr 02.03.07 22:42

Gausi hat folgendes geschrieben:

Ein Element irgendwo einfügen geht mit Listen schneller, ja. Allerdings kann man bei Listen nicht "wild umherspringen", sondern kann immer nur auf das nächste/vorige Element zugreifen. Wenn das Array einmal komplett gefüllt ist, und nur vertauscht wird (und quasi alle Verfahren arbeiten nur mit Vertauschungen, bzw. wird das als Maß für die Laufzeit genommen), sind Arrays nicht weniger effizient als Listen.

Ich gebe dir Recht.

Gausi hat folgendes geschrieben:

Und sie bieten als Vorteil den schnellen Zugriff über Indizes, was bei einer Liste nicht möglich ist.

Also du meinst damit, dass man sofort auf das Element zugreift und sich nicht erst vom ersten Eintrag bis zum Index hinhangeln muss?

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

Ehemaliges Mitglied Erhaltene Danke: 1

bei den arrays, muss man aufpassen, dass dies selbstverwaltete sind... bei solchen wie tlist und abkömmlinge wird bei jeden tausch der ganze speicher umgeschichtet. handelt es sich um ein normales array, braucht man nur die zwei pointer zu tauschen. aber es kommt halt auf die art der sortierung an... ab und an, sind auch bäume (z.b. binarbäume) auch sehr fein... :-)

und die müssen ja auch sortiert werden... ;-)

Gausi · Verfasst: Fr 02.03.07 22:48

Grenzgaenger hat folgendes geschrieben:

bei den arrays, muss man aufpassen, dass dies selbstverwaltete sind... bei solchen wie tlist und abkömmlinge wird bei jeden tausch der ganze speicher umgeschichtet.

Kannst du das irgendwie belegen? Das halte ich nämlich für falsch.

@Marco: Ja, das meine ich.

_________________
We are, we were and will not be.

Ehemaliges Mitglied Erhaltene Danke: 1

Marco D. hat folgendes geschrieben:

Also du meinst damit, dass man sofort auf das Element zugreift und sich nicht erst vom ersten Eintrag bis zum Index hinhangeln muss?

wie gesagt, bei den arrays kann man sich die mitte berechnen und darauf frei zugreifen, bei 'ner liste muss man sich durchhangeln und bei 'n binärbaum braucht man sich die mitte nicht mal zu berechen, weil man die immer gegeben hat.

daher bringen arrays gegenüber 'n baum nur 'n vorteil, bei 'n randomsort... ;-)

Marco D. · Verfasst: Fr 02.03.07 22:50

Mit anderen Worten: Ich nehme Arrays

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

Gausi · Verfasst: Fr 02.03.07 22:53

Rrrischtisch :zustimm:

Ne Liste zu sortieren macht ja auch keinen Sinn - denn von einer sortierten Liste hat man eigentlich nichts. Bei nem sortierten Array kann man dann aber hinterher schneller suchen, wenn man z.B. Binärsuche oder so macht ;-)

_________________
We are, we were and will not be.

Ehemaliges Mitglied Erhaltene Danke: 1

Gausi hat folgendes geschrieben:

Grenzgaenger hat folgendes geschrieben:

bei den arrays, muss man aufpassen, dass dies selbstverwaltete sind... bei solchen wie tlist und abkömmlinge wird bei jeden tausch der ganze speicher umgeschichtet.

Kannst du das irgendwie belegen? Das halte ich nämlich für falsch.

vor einiger zeit hatte ich mir mal die quellen angeguckt und da hat er bei jeder kleinigkeit das ganze memory hin und her kopiert. müsst mir das mal wieder angucken, ist schon eine zeitlang her... seitdem sind für mich solche listen nur noch für kleinere listen geeignet... was hier ja auch schon öfters diskutiert wurde, wegen performanceproblemen.

bei gelegenheit werd ich mal wieder nachsehen.

Marco D. · Verfasst: Fr 02.03.07 22:59

Gausi hat folgendes geschrieben:

Rrrischtisch :zustimm:

Ne Liste zu sortieren macht ja auch keinen Sinn - denn von einer sortierten Liste hat man eigentlich nichts.

Hä? Wieso nicht? Wenn ich z.B. Dinge in einer verketteten Liste verwalte, die man oft verschiebt und oft neue Dinge einfügt (darum nehme ich in diesem Beispiel kein Array), dann will ich die auch einmal z.B. nach dem Alphabet ordnen lassen.

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

Gausi · Verfasst: Fr 02.03.07 23:05

Turbo-Delphi hat folgendes geschrieben:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

procedure TList.Exchange(Index1, Index2: Integer);
var
  Item: Pointer;
begin
  {...Fehlerbehandlung...}
  Item := FList^[Index1];
  FList^[Index1] := FList^[Index2];
  FList^[Index2] := Item;
end;

Da wird nur getauscht. :gruebel:

@Marco: Ja, natürlich kann man ne Liste sortiert anzeigen wollen. Aber algorithmisch betrachtet hat man davon nicht wirklich was. Mir fällt jetzt auf Anhieb nichts ein, was man in einer sortierten Liste wirklich schneller machen könnte als auf einer unsortierten - so meinte ich das ;-)

_________________
We are, we were and will not be.

Marco D. · Verfasst: Fr 02.03.07 23:08

Meine Frage ist beantwortet.
Von mir aus können Gausi und Grenzgaenger ihre heiße Diskussion noch weiter fortsetzen :mrgreen:

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

Ehemaliges Mitglied Erhaltene Danke: 1

Gausi hat folgendes geschrieben:

Turbo-Delphi hat folgendes geschrieben:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

procedure TList.Exchange(Index1, Index2: Integer);
var
  Item: Pointer;
begin
  {...Fehlerbehandlung...}
  Item := FList^[Index1];
  FList^[Index1] := FList^[Index2];
  FList^[Index2] := Item;
end;

Da wird nur getauscht. :gruebel:

stimmt, hast recht, dann war's wohl die löschfunktion.... 'ne tList mit 'n paar einträgen muss man ja auch wieder freigeben...

Gausi hat folgendes geschrieben:

@Marco: Ja, natürlich kann man ne Liste sortiert anzeigen wollen. Aber algorithmisch betrachtet hat man davon nicht wirklich was. Mir fällt jetzt auf Anhieb nichts ein, was man in einer sortierten Liste wirklich schneller machen könnte als auf einer unsortierten - so meinte ich das ;-)

mit 'ner unsortieren liste, kann man nix anfangen... aber auch nichts mit 'n unsortierten array... wenns sortiert ist, dann kann man prima sachen mit machen... :-)

, z.b. queues abbilden....

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme