Sortierverfahren für Liste

[gucci]

"Der Bubblesort ist ziemlich einfach - grundsätzlich funktionieren alle der oben aufgeführten Sortieralgorithmen (wir haben damals Arrays und keine Listen verwendet). "

Wir nehmen jetzt Listen durch und sollen diese sortieren. Unser Lehrer hat gesagt, dass nicht alle von den vieren funktionieren.

[DeddyH]

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

[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

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

[gucci]

Zitat von DeddyH:

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

es handelt sich um verkette Listen!

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