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 von 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

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 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 )

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

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