Brauche einen bestimmten Sortieralgorithmus |
| 07.11.2007, 11:56 | Auf diesen Beitrag antworten » |
| TheDancer | 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, 13:53 | Auf diesen Beitrag antworten » |
| Tobias | 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, 17:32 | Auf diesen Beitrag antworten » |
| TheDancer | Herzlichen Dank für den Denkanstoss! |
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
