Sortierverfahren für Liste

[Deep-Sea]

Zitat von DeddyH:

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

Richtig! Funktionieren tun aber trotzdem alle - nur eben manche besser als andere

[Deep-Sea]

Ich habe immer noch ein Programm rumliegen, wo ich mit Sortieralgos gespielt habe *in erinnerungen schwelg*
Sort.png

(PS: Rechts sind gerade die Daten von BubbleSort dargestellt, nicht das noch einer meckert, dass es nicht zum MergeSort passt )

[BUG]

Weil es gerade so durch die Blogs geht:

• Bubble Sort
• Insert Sort
• Selection Sort
• Shell Sort

[DeddyH]

OK, bei verketteten Listen machen nur die Sortieralgorithmen Sinn, die die Liste von vorn nach hinten (oder andersherum) abarbeiten. Dinge wie "in die Mitte pieksen und vergleichen" funktionieren nicht, da man nicht weiß, wo die Mitte ist.

[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

[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.

[gucci]

Okay!

Danke für eure Hilfe!

[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.