---

Geschrieben von TheDancer am 07.11.2007 um 11:56:

  Brauche einen bestimmten Sortieralgorithmus

Ich habe folgende Aufgabenstellung, aber leider keine Ahnung, wie ich sie lösen könnte.

Ein lineares Feld A[1 . . . n] enthalte ganzzahlige Eintäge. Es soll so umgeordnet werden daß im
ersten Teil des Feldes alle negativen Zahlen stehen, im mittleren Teil alle Nullen und im letzten Teil
alle positiven Zahlen. Beschreiben Sie einen Algorithmus der eine solche Umordnung durchführt
ohne zus¨atzlichen Speicher zu verwenden (außer Indizes und Zählvariablen). Der Zeitaufwand des
Algorithmus soll linear in n sein.

Hat jemand eine Idee, wie man das Beispiel lösen könnte?

---

Geschrieben von Tobias am 07.11.2007 um 13:53:

 

Idee ist folgende:


Suche im Array von links nach einer Zahl, die größer older gleich 0 ist. Merke dir die Position in l.
Suche dann im Array von rechts nach einer Zahl, die kleiner als 0 ist. Merke dir die Position in r.
Tausche beide Zahlen.
Wiederhole das von den Positionen l und r solange, bis sich die Zeiger kreuzen.

Das Ergebnis ist eine Sortierung, die links alle Zahlen < 0 und rechts alle Zahlen >= 0 hat. Jetzt musst du noch in einem zweiten Durchgang die 0en von den positiven Zahlen trennen. Dafür kannst du dieselbe Idee verwenden.

---

Geschrieben von TheDancer am 07.11.2007 um 17:32:

 

Herzlichen Dank für den Denkanstoss!