Bubblesort

[Guest]

Hätte mal ne Frage bezüglich Bubble-Sort.
Die frage Stellung ist folgende:
Bubblesort wird typischerweise auf Arrays verwendet, kann aber auch auf Listen implementiert
werden.Wie ist dabei bei einfach und doppelt verketteten Listen vorzugehen?
Irgendwie kann ich mir da nix drunter vorstellen und hab auch schon ewig gegoogelt, nur leider nix hilfreiches gefunden.
Deswegen würd ich mich sehr über Antworten freuen.
Schonmal viele Dank im vorraus

 

[Gast2]

doppelt verketteten Listen hört sich nach C an

 

[der Verzweifelte]

.. ich kenn mich zwar auch nicht wirklich aus und wart eign nur drauf dass auf meinen thread geantwortet wird ;D aber im Gegensatz zur einfach verketteten Liste hat hat in ner doppelt / mehrfach verketteten liste jedes element nicht nur einen zeiger auf das nachfolgende sondern auch noch auf das vorherige element gespeichert.. ob jetzt in c, java etc. spielt da glaub ich keine rolle

 

[Gast2]

nur dass du in java keine pointer auf deine nächsten/vorherigen elemente programmieren musst...

 

[masta // thomas]

Weißt du eigentlich, wovon du sprichst, SirWayne? Warum hört sich eine doppelt verkettete Liste nach C an?

Zur Frage: du machst nichts anderes, als mit einem Array - du änderst die Position eines jeden Elements (nach bedarf). Du vergleichst aktuelles Element mit Nachfolger, wenn Platz getauscht werden soll, änderst du einfach die Referenzen.

 

[Gast2]

und du redest dann in java von verketteten listen anstatt von arrays??????
also nächstes mal wenn ich ein array problem hab red ich davon ob jemand meine verkette liste sortieren kann!!!!(SARKASMUS!!!!!!)
die frag stellung hört sich halt leicht c angelehnt an... kann mir schlecht vorstellen dass jemand das wort verkette liste in zusammenhang mit java bringt... das wort arraylist ist wohl üblicher?????!!!!!

 

[Tobias]

Nein, ich kann durchaus in Java eine verkettete Liste programmieren. Da brauch ich nicht mal ein Array für. Mach ich aber nicht, weil das JDK sowas schon hat -> LinkedList.

Datenstrukturen sind doch nicht von der Sprache abhängig ... * kopfschüttel*

mpG
Tobias

 

[Roar]

verkettete listen sind aber was anderes als arrays!!!!!!
darum fragte der threadersteller auch wie man statt eines arrays eine verkettete liste mit bs sortieren kann????

gruß :lol:

 

[Tobias]

Jo, schon klar. Klingt mir zu sehr nach Hausaufgabe, als das ich da konkreter drauf eingehen will als masta // thomas.

mpG
Tobias

 

[Gast2]

hab auch nie was anderes behauptet... hab nur gesagt dass in zusammenhang mit java wohl eher die wörter wie dynmaischer container oder collection oder sowas in die richtung fallen sollte, als verkette liste...
hab nur gesagt die fragegstellung hört sich leicht nach c an...Sorry ist meine subjektive meinung !!!hab halt nie ein prof gehört der sowas sagen würde...

 

[Roar]

hab halt nie ein prof gehört der sowas sagen würde...

habt ihr nie verkettete listen besprochen?

das wort arraylist ist wohl üblicher?????!!!!!

nein weil eine arraylist ein array ist und keine verkette liste, zu verketteten listen sagt man verkettete liste :gaen:

 

[Tobias]

Ah ja, in Java benutzen wir also lieber schwammige Begriffe, die nix bedeuten statt einfach zu sagen, was wir meinen?

Ich hoffe nicht.

mpG
Tobias

 

[der Verzweifelte]

hm ja das bringt alles dem Fragesteller sehr viel :>
aber geht mich ja eign nix an

 

[masta // thomas]

Das hab ich mir auch schon gedacht.

Gast: Woran scheiterst du denn letztlich? Hast du eine verkettete Liste bereits implementiert? Hast du ein Bubblesort implementiert? Was hast du / was kannst du - bzw. was kannst du nicht?

 

[Guest]

Implimentieren soll man ja nix ist nur ne theoretische Frage, ich checks einfach nicht.
Die Frage ist einfach was der Unterschied zu verketten Listen ist im Gegensatz zu nem Array

 

[tincup]

So also zweierlei:

@SirWayne: Du bringst da einiges durcheinander. Eine doppelt verkettete Liste ist ja zunächst einmal ein theoretisches Konstrukt aus der Informatik. Ob nun die konkrete Implementation mit Speicherpointern, Objekten, dynamischen Java Irgendwasdings gemacht wird ist ja nen völlig anderes paar Schuh'.

Jetzt konstruktiv @Gast:

Bei Bubblesort im Array gehst du einfach von unten nach oben durch und lässt zwei Elemente immer ihren Platz tauschen, wenn die Reihenfolge der beiden falsch ist. Also wenn das i-te größer ist als das i+1-te. Das ganze machst du so oft bis sich nichts mehr ändert.

Ne doppelt verkettete Liste ist etwas anderes das ist auch eine Folge von Werten "hintereinander" wie ein Array, nur besteht die aus Objekten (idealerweise). Jedes Objekt hat einen Wert und zeigt zudem einmal auf seinen Nachfolger und einmal auf seinen Vorgänger (es hat eine entsprechende Referenz). Der Vorgänger vom ersten und der Nachfolger vom letzten sind null.

Beim Bubblesort gehst du jetzt analog zum Array vor, du "hangelst" dich von vorne nach hinten durch die Liste, immer wenn die Reihenfolge nicht passt vertauschst du die Position der beiden. Das ist jetzt hier etwas komplizierter. In etwa so falls A vor B steht:

Vorgänger von A := B
Vorgänger von B := alter Vorgänger von A
Nachfolger von A := alter Nachfolger von B
Nachfolger von B := A

Mals dir mal auf dann solltes klar werden. Wenn du die doppelt verketteten Listen noch nicht begriffen hast, google mal danach, solltest leicht was finden.

So puh das ist aber lang geworden

HTH,
tin

 

[Gast2]

www.peter-junglas.de/fh/vorlesungen/algorithmen/html/kap1-4-1.html

na ja für mich sieht eine arraylist auch so aus.... wie name der halt schon sagt ein array mit einer LISTE...

@SirWayne: Du bringst da einiges durcheinander. Eine doppelt verkettete Liste ist ja zunächst einmal ein theoretisches Konstrukt aus der Informatik. Ob nun die konkrete Implementation mit Speicherpointern, Objekten, dynamischen Java Irgendwasdings gemacht wird ist ja nen völlig anderes paar Schuh'.

hab ich hab was anderes behauptet ???? Hab nur gesagt dass es eine unübliche fragstellung ist...

Implimentieren soll man ja nix ist nur ne theoretische Frage, ich checks einfach nicht.
Die Frage ist einfach was der Unterschied zu verketten Listen ist im Gegensatz zu nem Array

array=nicht dynamisch
Liste=dynamisch

 

[Backwardsman]

hab ich hab was anderes behauptet ???? Hab nur gesagt dass es eine unübliche fragstellung ist...

ich versteh auch nicht was daran unüblich sein soll?! verkettete listen, stacks, bäume... das alles sind datenstrukturen, welche, wie tincup bereits erwähnt hat, absolut unabhängig von C, java oder sonst einer programmiersprache sind!

 

[maki]

Verkettete Listen, auch doppelt, sind nicht unüblich in Java, oder Pascal, oder C, oder oder oder...

 

[Leroy42]

Habt ihr's jetzt endlich? :shock:

 

[Leroy42]

Habt ihr's jetzt endlich? :shock:

 

[Gast2]

jop in java gibts dafür Standardklassen wie ArrayList,Vector oder oder oder oder

 

[maki]

jop in java gibts dafür Standardklassen wie ArrayList,Vector oder oder oder oder

Hmm... naja, lassen wir das.

 

[tincup]

Allerdings! ???:L

An den Original-Poster: Ist denn der Lösungansatz jetzt klarer geworden?