Sortieralgorithmus verbessern (Haskell)

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo ihr lieben,

an unsrer Uni haben wir zur Zeit das Thema Sortieren und Suchen. das heißt wir sollen verschiedene Sortieralgorithmen schreiben. Wir programmieren in im Moment noch mit Haskell, also funktional. Ich habe den Bubbelsortalgorithmus geschrieben. Hat mich eigentlich gewundert, denn es hat beim ersten Interpretieren schon funktiniert :smile:
Meine Problem ist nun, dass ich für jeden bubble die eine fkt über die Liste laufen lassen muss ob sie denn schon sortiert ist, wenn nicht muss die funktion springen nochmal durch die ganze Liste springen. Ist natürlich extrem langsam. Ich hab dir Fkt mal mit (reverse[1…10000]) also dem worst case aufgerufen, die Folge war, nach ca 20 Sek. hat mein Pc den Prozess gekillt :smile:

Hier mal mein Code:

-- springen ist "fast" analog zum Algorithmus geschrieben, z.B: [3,2,7,1]
-- 3 \> 2 =\> 3 springt über zwei, (3 und zwei tauschen also)
-- 3 Algorithmus beginnt von neuem, mit veränderter liste [2,3,7,1]
-- 2 1 =\> Algorithmus beginnt von neuem, mit veränderter liste [1,2,3,7] fertig
springen :: [Integer] -\> [Integer]
springen [x] = [x]
springen (x:xs:xl) = if x \> xs then springen(xs:x:xl) else x : springen(xs:xl)

-- istkleiner benötige ich für die Hauptfkt bubblesort, sie bewirkt den erneuten Aufruf der Springenfkt.
istkleiner :: [Integer] -\> Bool
istkleiner [] = True
istkleiner [x] = True
istkleiner (x:xs:xl) = if x [Integer]
bubblesort (x:xs) = if istkleiner(x:xs) then (x:xs) else bubblesort(springen(x:xs))

hat jemand eine Idee wie ich den ganzen Algorithmus verbessern kann?

lg Matthias

#2

Hi,

es sieht besser aus, wenn Du die Rekursion umdrehst und dabei ausnutzt, dass bubblesort() eine sortierte Liste liefert.

bubblesort :: [Integer] -\> [Integer]
bubblesort [] = []
bubblesort (x:xs) = ???(x:bubblesort(xs))

Jetzt Du wieder: Was muss die Funktion ‚???‘ machen? (Wie sieht die Eingabe für ‚???‘ aus?)

Gruß,
KHK

#3

Hallo KHK, :smile:

danke für deine schnelle Antwort, ich habe mir mal Gedanken drüber gemacht was du damit meinst und wie ich daraus was machen kann. Da kam mir die Idee, wenn ich istkleiner ein wenig abändere, und prüfe ob die erste Zahl in der Liste das kleinste Element ist, dann kann er die Zahl ja schonmal ausgeben. War es dass was du meinst, hier nochmal der gesamte Code dazu.

springen :: [Integer] -\> [Integer]
springen [x] = [x]
springen (x:xs:xl) = if x \> xs then springen(xs:x:xl) else x : springen(xs:xl)

-- istkleiner benötige ich für die Hauptfkt bubblesort, sie bewirkt den erneuten Aufruf der Springenfkt.
istkleiner :: [Integer] -\> Bool
istkleiner [] = True
istkleiner [x] = True
istkleiner (x:xs:xl) = if x [Integer]
bubblesort [] = []
bubblesort [x] = [x]
bubblesort (x:xs) = if istkleiner(x:xs) then x : bubblesort(springen(xs)) else bubblesort(springen(x:xs))

Mein Problem habe ich allerdings immer noch. Kann es sein, dass der Bubblesort im Worst Case garnicht schneller ist als der Selectionsort oder Insertionsort?

Wenn ich so drüber nachdenke… kann er eigentlich nicht besser sein, da er die ganze Liste durchlaufen muss um das Element zu verschieben, oder habe ich deine Idee noch nicht ganz gertoffen?

Dankeschön nochmal,

lg Matthias

#4

Hallo KHK :smile:

ich habe es geschafft. :smile: Gerade habe ich mir bei YouTube Videos zum Sortieren angesehen und da kam ich auf die Idee…

Es ist zwar etwas anders als in der „Def.“ des Bubblesort Alg. aber naja … :smile: Ich habe die „bubble“ Funktion so umgeschrieben, dass nicht das größte Element, sondern das kleinste nach hinten geschoben wird. In der Hauptfkt. nutze ich dann die Lazyfkt. von Haskell aus und gebe immer die kleinsten Elemente (das letzte Element) aus.

Zum besseren Verständnis wieder der Code:

bubbeln :: [Integer] -\> [Integer]
bubbeln [] = []
bubbeln [x] = [x]
bubbeln (x:xs:xl)
 | x [Integer]
bubblesort2 [] = []
bubblesort2 [x] = [x]
bubblesort2 (x:xs:xl) = let k = bubbeln(x:xs:xl)
 in last(k) : bubblesort2(init(k))

lg Matthias

#5

Hi,

Ein Punkt, der die Effizienz steigert, ist die Ausnutzung der Tatsache, dass der rekursive Aufruf eine sortierte Liste zurückgibt.

(Ich kenne Haskell nicht, bitte korekte Syntax selber dazudenken)

bubblesort: [int] -\> [int]
bubblesort [] = []
bubblesort (x:xs) = bubbeln(x:bubblesort(xs))




-- Precondition(s):
-- \* die übergebene Liste ist nicht leer
-- \* die übergebene Liste ist ab der zweiten Position aufsteigend sortiert
bubbeln: [int] -\> [int]
bubbeln [x] = [x]
bubbeln (x1:x2:xs) = 
_if x1_

Die anfängliche Liste (x1,x2,…,xn) wird zerlegt, es entsteht der Ausdruck

bubbeln(x1 : bubbeln (x2 : bubbeln( ... bubbeln( xn : [])...)).

Von innen nach außen augewertet, wird die Liste wieder zusammengesetzt und dabei ein Wert nach dem anderen von links in die wachsende Liste „hineingebubbelt“.

Gruß,
KHK

#6

Hallo KHK,

danke für deine Antwort. Ich habe mal dein Code sytaktisch verbessert und ihn laufen lassen, wenn ich ihm aber den worst case mit 10000 übergebe, also eine absteigend Sortierte Liste bis 10000 übergebe, ist der nicht schneller als mein Insertionsort.

Ist das normal?

lg Matthias

#7

Ja. Das ist normal. Üblicherweise ist Bubblesort zwar am schnellsten zu programmieren, aber in der Ausführung am langsamsten.

Gruß Lutz