Verkettungsalgorithmus

[Astasor]

Hey

ich soll einen Algorithmus beschreiben, der mit der laufzeit n log(k) läuft und folgende eigenschaften hat.

eingabe: k aufsteigend sortierte listen mit insgesamt n elementen

ausgabe: eine aufsteigend sortierte liste mit allen elementen der eingabelisten

meine überlegung: n log k errinnert mich sehr stark an mergesort und "divide & conquer"

problem: ich komme auf ne laufzeit die bei n^2 liegt, da ich immer wieder vergleichen muss.

bsp: mit 2 listen

liste 1= 2 4 6 8

liste 2= 1 3 5 7




länge(1)+länge(2)=n

while (länge(ergebnisarray)!=n) tue{

1 mit 2 vergleichen 


ergebnisarray: 1 2


3 mit 4 vergleichen


ergebnisarray: 1 2 3 4


5 mit 6 vergleichen


ergebnisarray: 1 2 3 4 5 6


7 mit 8 vergleichen


ergebnisarray: 1 2 3 4 5 6 7 8

}

ergebnisarray hat n elemente, gebe es aus

doch wenn sich hier meine eingabe verdoppelt ich also 4 felder habe, verdoppelt sich auch der aufwand. ich hatte auch daran gedacht mit binärer suche das feld abzulaufen und nach dem jeweils nächst kleineren element zu suchen. 2 4 6 8 1 3 5 7

suche kleineres element von 2 -> 1 ( der -> zeigt auf das suchergebnis)


ergebnisarray: 1 2 


eingabearrays verkürzen sich 


4 6 8

3 5 7


suche kleineres element von  4 -> 3


ergebnisarray: 1 2 3 4


eingabearrays verkürzen sich 


6 8

5 7


suche kleineres element von  6 -> 5


ergebnisarray: 1 2 3 4 5 6


eingabearrays verkürzen sich 


8

7


suche kleineres element von  8  -> 7


ergebnisarray: 1 2 3 4 5 6 7 8


eingabearrays sind leer, gebe ergebnisarray aus.

doch das klappt nicht bei allen listen. außerdem bin ich mir mit der laufzeit unsicher.

die felder kann ich ja eigentlich auch als text nehmen, oder? dann könnte ich algorithmen der textsuche darauf anwenden.

in der vorlesung sind wir gerade bei binären suchbäumen, doch so einen baum zu erstellen dauert länger als n log k. also scheidet das als lösungsmöglichkeit meiner meinung nach aus, obwohl man einen suchbaum mit inorder traversierung ganz leicht korrekt sortiert auslesen kann.

ich stecke in einer sackgasse, *haaalp*

mfg Astasor

[Astasor]

merke gerade das ich oben einen ziemlichen fehler mit reingebaut habe. statt eingabearrays sollte es eingabelisten heißen.

denn ein array ist etwas anderes als eine liste. is mir heute aufn heimweg klar geworden.

und da es eine listen sind, kann man sie ja nach belieben aufbrechen und neuverketten. nun leibt nur noch das problem mit der laufzeit -.-

[flashpixx]

Ein Tipp: Nimm mal zwei Listen mit je einem Element z.b. 2 und 3, wie würdest Du diese verketten. Nun nimm mal eine Liste mit 2 und eine mit einem Element: [1 4] und [3] wie verkettest Du diese.

Überlege Dir einfach was als Methode dahinter steht