Sortierverfahren für Liste

[gucci]

Hallo Leute,

Ich soll im Informatikunterricht eine Präsentation über "Sortierverfahren" erstellen. Unter anderem gibt es da das Thema "Sortierverfahren mit Listen". Ich bin mir nicht sicher, welcher von den vieren funktioniert:

1. Merge Sort
2. Quick Sort
3. Insertion Sort
4. Bubble Sort

Allerdings bin ich mir ziemlich sicher, dass der Bubble Sort nicht klappt.

Ich soll auch selber einen Sortieralghorithmus schreiben. Könnt ihr mir einen Tipp geben, welcher der einfachste und sinnvollsten ist?

LG, Gucci

[aurikel_Max]

Zitat:

Zitat von gucci (Beitrag 1095119)

Hallo Leute,

Ich soll im Informatikunterricht eine Präsentation über "Sortierverfahren" erstellen. Unter anderem gibt es da das Thema "Sortierverfahren mit Listen". Ich bin mir nicht sicher, welcher von den vieren funktioniert:

1. Merge Sort
2. Quick Sort
3. Insertion Sort
4. Bubble Sort

Allerdings bin ich mir ziemlich sicher, dass der Bubble Sort nicht klappt.

Ich soll auch selber einen Sortieralghorithmus schreiben. Könnt ihr mir einen Tipp geben, welcher der einfachste und sinnvollsten ist?

LG, Gucci

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

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

Zitat von DeddyH (Beitrag 1095125)

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 :-D

[Deep-Sea]

Ich habe immer noch ein Programm rumliegen, wo ich mit Sortieralgos gespielt habe *in erinnerungen schwelg* :stupid:
Anhang 33901

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

[gucci]

Zitat:

Zitat von DeddyH (Beitrag 1095125)

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

es handelt sich um verkette Listen!

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

Zitat von JasonDX (Beitrag 1095148)

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 :-D In der normalen Version ist MergeSort für verkettete Listen ebenfalls suboptimal.

[himitsu]

Zitat:

Zitat von DeddyH (Beitrag 1095136)

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:

Zitat von DeddyH (Beitrag 1095125)

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:

Zitat von Delphi-Laie (Beitrag 1095333)

da TList letztlich intern über ein dynamisches Array implementiert ist

statisch* :duck:

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