Hallo,
die in der Überschrift angedeutete Angabe haben wir in der Übung zu Algorithmen und Datenstrukturen bekommen. Verlangt ist das beste Verfahren das uns einfällt, mit dem Zusatz, dass eine Lösung in 7 Schritten möglich ist.
Nach stundenlanger Knobelei bin ich zu folgender Lösung gelangt:
-
Teile die Menge/das Array/das Feld in zwei Teile. Teil eins enthält die Element 0 und 1, Teil zwei die Elemente 2,3 und 4.
-
Sortiere die beiden Mengen
-
Füge das kleinere Element der Menge eins in Menge zwei ein und merk dir dir einfüge position
-
Füge das größere Element der Menge eins in Menge zwei ein, beginne mit den Vergleichen aber erst ein Element nach der Einfügeposition vom kleineren Element von Menge eins.
Ausgeführt könnte das ganze so aussehen:
Menge (3,1,0,4,2)
Menge 1: (3,1)
Menge 2: (0,4,2)
(3,1) (0,4,2) #vergleiche 0 und 1
(1,3) (0,4,2) # 2,3
(1,3) (0,4,2) #3,4
(1,3) (0,2,4) #2,3)
(1,3) (0,2,4)
#Das waren vier Schritte
#Füge 1 in (0,2,4) ein:
(1,3) (0,2,4) #1<0?
(1,3) (0,2,4) #1<2?
#vier schritte, 1 ist an Position (Array Index) 1 eingefügt worden
(3) (0,1,2,4) #3<4?
Ich wollte jetzt ja eigendlich eine Frage zur Implementierung stellen, aber mir ist aufgefallen, dass dieser Algorithmus im worst Case mehr als 7 Schritte braucht:
(63) (091)
#4 schritte
(36) (019) #3<0?
(36) (019) #3<1?
(36) (019) #3<9?
#7 Schritte....
Jetzt bin ich mir nicht sicher, ob ich dieses Posting noch posten soll, weil ja die konkrete Frage sich während des Schreibens zur elementaren Frage gewandelt hat. Naja, vielleicht hat ja jemand Probleme beim Einschalfen und Lust mir einen Denkanstoß zu geben :-)
Danke für eure Zeit und liebe Grüße,
Severin
--
They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety.
-- Benjamin Franklin