Sortierverfahren für Liste

[blauweiss]

Zitat von JasonDX:

Auch wenns eine verkettete Liste ist, macht das keinen Unterschied, auch nicht in der Laufzeitkomplexität - Die Algorithmen lassen sich daran anpassen.
Auf jeden Fall ist die Aussage des Lehrers, dass "einer der Algorithmen nicht funktioniert", falsch.

greetz
Mike

Richtig. Die Methoden/Eigenschaften von TList ebenso wie ein prozeduraler Ansatz auf Arrays lassen sich für eine einfach/doppelt verkettete Liste nachbilden und umgekehrt.
Entweder ist die Beschreibung von "funktioniert nicht" unvollständig (Wahrscheinlichkeit 1/3 geschätzt) und/oder (auch) dieser sog. "Lehrer" ist inkompetent (Wahrscheinlichkeit 4/5 geschätzt).

Gruß,
blauweiss

[Deep-Sea]

Mh, schon lange nicht mehr mit gearbeitet ... aber auf dem von mir geposteten Screenshot sieht man ja in der ComboBox rechts, dass "MergeSort (VL)" markiert ist. VL steht dabei für verkettete Listen. Es ist eine spezielle MergeSort-Implementation, die dann - im Gegensatz zur normalen Version - sogar in-place arbeitet In der normalen Version ist MergeSort für verkettete Listen ebenfalls suboptimal.

[himitsu]

Zitat von DeddyH:

Dinge wie "in die Mitte pieksen und vergleichen" funktionieren nicht, da man nicht weiß, wo die Mitte ist.

Es sei denn man legt sich einen Index, z.B. in Form eines Array oder TList an, sortiert diese Liste und baut im Anschluß die verkettete Liste über das Array/TList neu auf.

[DeddyH]

Dann kann ich aber gleich auf TList ausweichen.

[Delphi-Laie]

Zitat von DeddyH:

TList oder verkettete Listen? Das ist ein riesiger Unterschied im Bezug auf Sortierung.

Richtig, da TList letztlich intern über ein dynamisches Array implementiert ist, ist auch dort völlige Zugriffsfreiheit bezüglich der Elemente vorhanden. Bei doppelt oder gar nur einfach verketteten Listen muß man sich hingegen recht umständlich von Element zu Element zum gesuchten/gewünschten „hangeln“ - eine ziemliche Sisyphusarbeit.

[mleyen]

Zitat von Delphi-Laie:

da TList letztlich intern über ein dynamisches Array implementiert ist

statisch*

[Gausi]

Insertionsort und Bubblesort lassen sich sehr einfach auf Listen implementieren. Hier werden immer nur benachbarte Elemente verglichen und vertauscht - kein Problem bei Listen.

Bei Quicksort laufen zwei "Zeiger" von vorne und hinten durch die Datenstruktur und vertauschen ggf. die Werte an den beiden Positionen - kein Problem mit Listen. Auch der rekursive Schritt ist mit Listen kein Problem.

Mergesort ist das einzige, wo man etwas mehr nachdenken könnte - hier kommt es auch auf die Variante an, die verwendet werden soll. Generell sollte aber der natürliche Mergesort (das ist die Variante, die Vorsortierungen berücksichtigt) aber auch mit Listen gehen - und da geht auch das mischen ohne zusätzlichen Speicher. (Man kann auch Arrays in Linearzeit auf konstantem Platz mischen, aber das ist nicht ganz trivial)

Wenn in der Liste noch ein Heapsort aufgeführt wäre, dann würde ich sagen: Der geht nicht (ohne weiteres) mit Listen. Wenn dann würde sich da ein Binärbaum anbieten.

[gucci]

Okay!

Danke für eure Hilfe!