 Brauche einen bestimmten Sortieralgorithmus |
TheDancer
Grünschnabel
Dabei seit: 07.11.2007
Beiträge: 2
 |
|
| 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?
|
|
07.11.2007 11:56 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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.
|
|
|
07.11.2007 13:53 |
|
|
TheDancer
Grünschnabel
Dabei seit: 07.11.2007
Beiträge: 2
|
|
Herzlichen Dank für den Denkanstoss!
|
|
|
07.11.2007 17:32 |
|
|
|
