Algorithmus zum entmischen einer Zahlenfolge

[BlackParrot]

Hallo zusammen,
leider weiß ich nicht, ob ich hier richtig bin, aber leider komme ich bei einem Problem nicht weiter:Ich habe eine Frage zu folgendem Algorithmus:

Mischen(Feld A)
    n1 = ⌊(A.länge + 1)/2⌋
    n2 = A.länge − n1
    L = neues Feld[1..n1]
    R = neues Feld[1..n2]
    L[1..n1] = A[1..n1]
    R[1..n2] = A[n1 + 1..A.length]
    i=j=1
    für k = 1 bis A.length mache {
        b = Random(0,1)
        wenn(b==0 und i≤n1) oder j>n2 dann {
            A[k] = L
            i=i+1
}
        sonst {
            A[k] = R[j]
            j=j+1
}
}

Ich habe ein sortierte Feld A, auf das nur 1x obiger Misch-Algorithmus angewendet wurde.
Jetzt ist es meine Aufgabe, einen vergleichsbasierten Algorithmus zu entwerfen, der in linearer Laufzeit dieses einmal gemischte Feld wieder (rück-)sortiert.

Leider komme ich hier nicht weiter. Kann mir vielleicht jemand einen Tipp geben?

Vielen Dank!

 

[Flown]

Was hast du bisher versucht? Kannst du mit Worten sagen, was der obige Algorithmus macht?

 

[mariane]

Die ersten zwei Codezeilen sind so nicht direkt auf Java übertragbar, nur als Tipp. Dann wären nämlich n1 und n2 vom Zahlenwert her identisch. Beachte dabei auch das L-ähnliche Symbol links und rechts (gespiegelt), die haben eine spezielle Bedeutung.
Unabhängig davon kann Codezeile 6 nicht korrekt sein, weder in Java noch in irgendeiner anderen Programmiersprachen, da knallt es einfach.

Versuche aber durchaus dahinter zu kommen, was hier passieren soll und setze das mal Java-Konform um und passe dabei vorallem bei den Indizes auf.

Ansonsten kann ich mir gut vorstellen was da passieren soll und kann dir versichern, das es kein besonderen Algorithmus geben wird, der das wieder in die richtige Reihenfolge bringt, es sei denn du nimmst Monkey-Sort (Bogo-Sort). Nein, ernsthaft, jeder bekannter Sortieralgorithmus ob Bubblesort oder Quicksort oder oder wäre eine Lösung für das Problem hier.

 

[BlackParrot]

Hallo zusammen,

ja meine Code soll nur Pseudocode sein.
Wir können uns das ja vorstellen, als wäre Fels A ein Kartenstapel:
Ein Kartenstapel wird zuerst in der Mitte geteilt
(falls A.length gerade: zwei gleich große Stapel; falls A.lenght ungerade:
Stapel L um 1 größer als Stapel R -> Abrundungsklammern);
Nun werden die Stapel von oben nach unten durchgegangen:
Wenn der Zufallszahlengenerator die Zahl 0 ausgibt (Wahrscheinlichkeit = 0,5)
und es noch Karten im Stapel L gibt (i<= n1) oder es keine Karten mehr im
Stapel R gibt (j > n2), wie die oberste Karte von Stapel L weggenommen.
Wenn hingegen die Zufallszahl 1 ist und der Stapel R noch nicht leer ist
oder wenn der Stapel L bereits leer ist, wird vom Stapel R eine Karte genommen
und auf die bereits weggenommenen Karten gelegt, sodass diese
gemischt werden.

Was der Misch-Algo macht, ist mir prinzipiell klar und ich kann das auch mit Beispielfeldern durchgehen.
Die Aufgabe ist es nun aber, einen vergleichsbasierten Sortieralgorithmus zu entwerfen, der ein Feld, das zuvor sortiert war und auf das dann nur einmal der obere Algorithmus angewendet wurde, wieder zu sortieren. Und das soll in linearer Zeit geschehen. vergleichsbasierten Sortieralgorithmen (wie auch Quicksort) brauchen ja mindestens nlogn als Laufzeit. Diesen Spezialfall eines "unsortierten" Felds kann man scheinbar aber mit einem speziellen Algorithmus in linearer Zeit sortieren.

 

[DrZoidberg]

Du musst den Mischalgorithmus im Grunde nur umkehren. Du hast dann also wieder zwei Felder L und R.
Du weißt, dass alle Elemente in R grösser oder gleich sämtlichen Elementen in L sein müssen.
Du gehst jetzt alle Elemente von A der Reihe nach durch. Wenn das aktuelle Element >= dem letzten Element von R ist, muss das Element aus A an R angehängt werden, andernfalls an L.
Am Schluss musst du nur noch L und R wieder nach A zurückkopieren.
Das einzige Problem dabei ist, dass R anfangs noch leer ist. Deshalb musst du erst einmal A so lange durch gehen, bis das aktuelle Element kleiner ist als das vorangegangene. Jetzt kannst du die nicht passenden Elemente nach R verschieben und dann mit dem zuvor genannten Algorithmus den Rest auf die beiden Felder verteilen.
Verwendest du Java um deinen Algorithmus zu testen?

 

[BlackParrot]

Hallo DrZoidberg, deine Idee hört sich für mich logisch und richtig an. Ich habe nur ein Verständnisproblem:

Jetzt kannst du die nicht passenden Elemente nach R verschieben

Meinst Du damit, dass ich am Anfang das Feld so lange durchgehe, bis A[i ]<A[i-1]. Sobald das gilt, schreibe ich A[i ] in R[1] und mache dann mit dem von dir zuerst genannten Algorithmus weiter. Habe ich das so richtig verstanden? Oder was genau meinst du mit den "nicht passenden Elementen"?
Vielen Dank für Deine Hilfe!

 

[DrZoidberg]

Fast richtig. Wenn A[i ] < A[i-1] kopierst du nicht A[i ] nach R, sondern A[i'] bis A[i-1], wobei i' kleiner ist als i und A[i'] das erste Element von A, das grösser ist als A[i ]. Die Elemente vor A[i'] müssen nach L kopiert werden.

 

[BlackParrot]

Okay, danke! Ich stehe glaube ich gerade auf dem Schlauch, denn ich kann mir gerade nicht vorstellen, wie ich diesen Kopiervorgang in Pseudocode (oder Java) schreiben könnte. Das andere ist mir alles klar, aber könntest du mir vielleicht die ersten Zeilen vorgeben? Den Rest kann ich dann vervollständigen.

 

[DrZoidberg]

Hier ist mal die erste Hälfte des Entmisch Algorithmus in Pseudocode.

Entmischen(Feld A)
    L = neues Feld[1..A.length]
    R = neues Feld[1..A.length]
    k=2
    while(k <= A.length und A[k] >= A[k-1]) {
      k++
    }
    wenn(k > A.length) {
      return; // A ist schon sortiert
    }
    i = k - 1
    while(i > 1 und A[i-1] > A[k]) {
      i--;
    }
    L[1..i-1] = A[1..i-1]
    R[1..k-i] = A[i..k-1]
    j = k-i+1
    // jetzt ist i gleich der "Länge" von L plus 1 und
    // j ist gleich der "Länge" von R plus 1

 

[BlackParrot]

Entmischen(Feld A)

    L = neues Feld[1..A.length]
    R = neues Feld[1..A.length]
    k=2
    while(k <= A.length und A[k] >= A[k-1]) {
      k++
    }
    wenn(k > A.length) {
      return; // A ist schon sortiert
    }
    i = k - 1
    while(i > 1 und A[i-1] > A[k]) {
      i--;
    }
    L[1..i-1] = A[1..i-1]
    R[1..k-i] = A[i..k-1]
    j = k-i+1
    // jetzt ist i gleich der "Länge" von L plus 1 und
    // j ist gleich der "Länge" von R plus 1

    k = i
    while (k <= A.length) {
      if A[k] >= R[j] then {
        R[j+1] = A[k]
        j++
        k++
      } else {
        L[i ] = A[k]
        i++
        k++
      }
    }
    for n = 1 to i -1 do {
      A[n] = L[n]
    }

    for n = i to j-1 do {
      A[i-1+n] = R[n]
    }
}

Habe ich das einigermaßen richtig gemacht?

 

[DrZoidberg]

Du musst dich entscheiden, ob i und j jeweils der momentanen Länge von L und R entsprechen oder der Länge plus 1. Ausserdem solltest du k nicht auf i setzen. k hatte schon den richtigen Wert (die aktuelle Position in A).

 

[BlackParrot]

Achso, also dann:

Entmischen(Feld A)

L = neues Feld[1..A.length]
R = neues Feld[1..A.length]
k=2
while(k <= A.length und A[k] >= A[k-1]) {
   k++
}
wenn(k > A.length) {
   return; // A ist schon sortiert
}
i = k - 1
while(i > 1 und A[i-1] > A[k]) {
   i--;
}

L[1..i-1] = A[1..i-1]
R[1..k-i] = A[i..k-1]
j = k-i+1
// jetzt ist i gleich der "Länge" von L plus 1 und
// j ist gleich der "Länge" von R plus 1

while (k <= A.length) {
   if A[k] >= R[j-1] then {
     R[j] = A[k]
     j++
     k++
   } else {
     L[i ] = A[k]
     i++
     k++
   }
}
for n = 1 to i -1 do {
   A[n] = L[n]
}

for n = i to j-1 do {
   A[i-1+n] = R[n]
}

Habe ich die Indizes jetzt richtig gesetzt oder ist da immer noch ein Denkfehler von mir drin?
PS: Danke für Dein Durchhaltevermögen, leider habe ich für diese Indizes kein Gefühl...

 

[DrZoidberg]

Einen kleinen Fehler sehe ich da noch. Und zwar in der letzten for Schleife. "for n = i to j-1". Ist das i da wirklich richtig?

 

[InfectedBytes]

benutz bitte Code Tags:
[code=java] hier kommt der code hin[/code]

 

[BlackParrot]

Oh ja, das war noch ein alter Gedankengang ...
Es müsste doch so heißen, oder?

for n = 1 to j-1 do {
A[i-1+n] = R[n]
}

 

[DrZoidberg]

Das sieht gut aus. Aber ich kann dir nicht garantieren, dass der Code jetzt wirklich fehlerfrei ist.