Severin Kacianka: Eine Liste mit 5 Element mit 7 Vergleichen sortieren

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:

  1. 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.

  2. Sortiere die beiden Mengen

  3. Füge das kleinere Element der Menge eins in Menge zwei ein und merk dir dir einfüge position

  4. 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
  1. gudn tach!

    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.

    ich finde, es ist schwierig, dafuer tipps zu geben, ohne die loesung komplett zu verraten, aber ich versuch's mal:
    die loesung ist, dafuer dass es bloss 5 zahlen sind, relativ kompliziert. mache einige der zu waehlenden vergleiche davon abhaengig, was bei vorigen vergleichen herausgekommen ist -> einige fallunterscheidungen.
    ach ja, und benenne die 5 werte am besten mit variablennamen z.b. a,b,c,d,e und schreibe dir nach jedem vertauschvorgang auf, welche informationen du nun hast, z.b. sowas wie "a<b und e<d<b".
    die sortier-verfahren, die hier genannt werden, koennen afais dir allesamt _nicht_ weiterhelfen.
    wenn ich mehr tipps, geben soll, wuerde das einer komplettloesung entsprechen. willst du das? ich empfehle dir eher, noch eine weitere (halbe) stunde zu investieren.

    prost
    seth

    1. Hallo,

      die loesung ist, dafuer dass es bloss 5 zahlen sind, relativ kompliziert. mache einige der zu waehlenden vergleiche davon abhaengig, was bei vorigen vergleichen herausgekommen ist -> einige fallunterscheidungen.

      Es gibt also keine "elegante" Lösung? Ich habe wohl schon daran gedacht, dass Transitivität eventuell wichtig ist, aber ich habe irgendwie gedacht, dass es anders geht als mit einer Unmenge an Fallunterscheidungen.

      Naja, dann setze ich mich morgen einmal hin und male Entscheidungsbäume ;-p Danke für den Denkanstoß!

      Gruß,
      Severin

      --
      They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety.
      -- Benjamin Franklin
      1. gudn tach!

        Es gibt also keine "elegante" Lösung?

        doch, die gibt es: http://www.mat.unb.br/~ayala/4FordJohnson.pdf.
        aber fuer 5 elemente machen die fallunterscheidungen wohl weniger arbeit.

        prost
        seth

  2. Hallo Severin,

    Ich hab mal etwas überlegt und der Ansatz ist folgender:
    Es gibt ja für 5 Elemente 5! = 120 Kombinationen.
    In jedem Schritt kann man nun die Menge der Kombinationen halbieren. Da log(120) / log(2) <= 7, ist das Problem also in 7 Schritten lösbar.

    Man hat also 5 Elemente a,b,c,d,e.
    Wenn man nun z.B. a und b und c und d vergleicht, kommt man schon auf 30 Kombinationen. Anschließend kann man noch die beiden größeren Elemente vergleichen und ist bei 15.
    Man kann die Elemente also so vertauschen, dass a < b, c < d und b < d gilt.

    15 ist nicht mehr durch zwei Teilbar, d.h. ab diesem Punkt wird das Problem asymetrisch. Mit ist keine bessere Möglichkeit aufgefallen, als einfach alle Möglichkeiten zu betrachten und sich zu überlegen, wie man diese wieder in zwei (bis auf 1) gleichgroße Mengen unterteilt.

    So bald man einen Schritt macht, bei dem keine solche Teilung passiert, hat man verloren.

    Im Prinzip müsste man die Lösung auch automatisch generieren können, indem man einfach alle 120 Kombinationen generiert und dann die Menge automatisch rekursiv unterteilt und dabei den Code für den Algorithmus generiert.

    Grüße

    Daniel