www.jammni.de

Gepostet:
18.12.2010 19:35

Selectionsort

Hallo,

wir sollen die fünf Sortieralgorithmen Selection-, Insertion-, Merge-, Bubble- und Quicksort schreiben, wobei wir sie nur für Integer werte deklarieren sollen. Ich habe schon gesehen dass jemand so fleißig war und sich die mühe gemacht hat die Sortieralgorithmen in jammni zu veröffentlichen, das finde ich auch echt super, nur hilft es mir nicht sehr viel für unsre Klausur wenn ich nicht weiß wieso dass so geschrieben wird und weil es mit Sicherheit auch mehrere Möglichkeiten gibt diese zu schreiben, würde ich es gerne selber versuchen und hoffe auf eure Unterstützung. :-)

Ich habe beschlossen mit Selectionsort zu beginnen. Vielleicht kurz zur Erleuterung, Bei einer gegebenen Liste wird das kleinste Element gesucht, an die neue liste angehangen und aus der alten Liste entfernt, dann beginnt die Rekursion und alles beginnt von neuem stimmt das soweit?

Als nächstes hab ich mir gedacht muss ich also eine Funktion schreiben die mir das kleinste Element aus der liste sucht. Weil es schon eine Funktion gibt die dass macht, nämlich "minimum" ist die erste Funktion auch nicht so groß:

mini :: [Integer] -> Integer
mini [] = 0
mini (x:xs) = minimum (x:xs)

nun brauch ich noch eine Funktion die das kleinste Element z.B. "x" aus der alten liste löscht, da weiß ich nicht mehr so richtig weiter, woher weiß denn der Computer wo das Element x ist, da könnte ja überall sein. Auch hier gibt es schon eine vordeklarierte Funktion "delete" kann man die hier mit einbringen?

Ich hoffe mir kann jemand weiterhelfen.

Liebe Grüße Matthias

Zum Seitenanfang

ICQ

Siracusa

Gepostet:
18.12.2010 19:47

Hallo,

du kannst delete dazu benutzen, denn delete löscht nur das erste Vorkommen eines Elements in der Liste. Wenn in der Liste bspw. 3x eine 1 vorkommt und 1 gerade das Minimum ist wird nur die erste 1 in der Liste gelöscht. Es genügt also das gefundene Minimum in die Ergebnisliste zu nehmen, delete auf die alte Liste anzuwenden und dann Selectionsort rekursiv auf der so entstandenen Liste weiterzuführen.

Viele Grüße,

Siracusa

Zum Seitenanfang

Anfaenger

Gepostet:
19.12.2010 10:31

Hallo,

danke schön deine Erklärung war echt super. Jetzt läuft das Programm hier mal meine Version:

select :: [Integer] -> [Integer]
select [] = []
select xs = mini xs : select (delete (mini xs) xs)

und weil ich nicht wusste ob wir die programmierten Funktionen von Data.List benutzen dürfen hab ich minimum und delete noch geschrieben

mini :: [Integer] -> Integer
mini [] = 0
mini (x:xs) = minimum (x:xs)

delete :: Integer -> [Integer] -> [Integer]
delete x [] = []
delete x (y : xs) = if x == y then delete x xs else y : delete x xs

wobei das delete sehr schwer zu verstehen ist fide ich.
vorallem dieses Stück der Zeile

delete x xs else y : delete x xs

Ich versuch delete mal zu beschreiben, also es vergleicht ob ein ihm bereits vorgegebenes Element in der vorgegebenen Liste zu finden ist, wenn ja dann löscht er es wenn nein dann löscht er es nicht.
Das müsste doch der Sinn von delete sein. Aber was macht das "delete x xs" das löscht x und was ist mit xs warum steht das noch hinten dran?

Liebe Grüße Matthias

Zum Seitenanfang

ICQ

Siracusa

Gepostet:
19.12.2010 16:50

Hallo,

was dein delete jetzt macht, ist alle Vorkommen von x aus der Liste zu löschen. Das ist nämlich genau der rekursive Aufruf delete x xs. Dort nimmst du y nicht mit in die Ergebnisliste, machst dann mit dem delete aber auf der Restliste xs weiter. Das sollte an der Stelle nicht passieren, sonst funktioniert dein Sortieren nicht mehr richtig.

Viele Grüße,

Siracusa

Zum Seitenanfang

Landei

Gepostet:
21.01.2011 12:05


select :: [Integer] -> [Integer]
select [] = []
select xs = let mini = minimum xs 
            in mini : select (del mini xs)

del :: Integer -> [Integer] ->  [Integer]
del x (y:ys) = if x == y then ys else y : del x ys
del _ _ = []

Zum Seitenanfang

Haskell-Forum