AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Sortierverfahren für Liste

Ein Thema von gucci · begonnen am 14. Apr 2011 · letzter Beitrag vom 15. Apr 2011
Antwort Antwort
Seite 2 von 2     12
blauweiss

Registriert seit: 19. Jun 2007
142 Beiträge
 
#11

AW: Sortierverfahren für Liste

  Alt 14. Apr 2011, 17:41
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
  Mit Zitat antworten Zitat
Benutzerbild von Deep-Sea
Deep-Sea

Registriert seit: 17. Jan 2007
907 Beiträge
 
Delphi XE2 Professional
 
#12

AW: Sortierverfahren für Liste

  Alt 15. Apr 2011, 08:46
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.
Chris
Die Erfahrung ist ein strenger Schulmeister: Sie prüft uns, bevor sie uns lehrt.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
39.647 Beiträge
 
Delphi 11 Alexandria
 
#13

AW: Sortierverfahren für Liste

  Alt 15. Apr 2011, 09:14
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.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.400 Beiträge
 
Delphi 11 Alexandria
 
#14

AW: Sortierverfahren für Liste

  Alt 15. Apr 2011, 09:15
Dann kann ich aber gleich auf TList ausweichen.
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#15

AW: Sortierverfahren für Liste

  Alt 15. Apr 2011, 09:38
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.
  Mit Zitat antworten Zitat
Benutzerbild von mleyen
mleyen

Registriert seit: 10. Aug 2007
609 Beiträge
 
FreePascal / Lazarus
 
#16

AW: Sortierverfahren für Liste

  Alt 15. Apr 2011, 09:43
da TList letztlich intern über ein dynamisches Array implementiert ist
statisch*
  Mit Zitat antworten Zitat
Benutzerbild von Gausi
Gausi

Registriert seit: 17. Jul 2005
764 Beiträge
 
Delphi 11 Alexandria
 
#17

AW: Sortierverfahren für Liste

  Alt 15. Apr 2011, 09:45
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.
The angels have the phone box.
  Mit Zitat antworten Zitat
gucci

Registriert seit: 2. Mär 2011
4 Beiträge
 
#18

AW: Sortierverfahren für Liste

  Alt 15. Apr 2011, 13:06
Okay!

Danke für eure Hilfe!
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 20:57 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf