Sortieralgorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Es sei ein ungeordnetes Zahlenarray a der Länge n gegeben, das nur ganzzahlige Werte
zwischen 1 und 100n enthält.
Skizzieren Sie für dieses Array einen Sortieralgorithmus, der durch Ausnutzen dieses
eingeschränkten Wertebereiches nur eine Komplexität von O(n) aufweist.
Hinweis: Das Sortieren muss nicht innerhalb des Arrays erfolgen. Man kann die
gegebenen Werte in ein anderes Array übertragen und von hier wieder in das
ursprüngliche zurückkopieren. |
Das Problem ist das ausnutzen dieses
eingeschränkten Wertebereiches von eine Komplexität von O(n).
ich habe Schwierigkeiten beim Lösen der Aufgabe, wäre super, wenn mir jemand helfen könnte.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo sabrina007,
> Hinweis: Das Sortieren muss nicht innerhalb des Arrays
> erfolgen. Man kann die
> gegebenen Werte in ein anderes Array übertragen und von
> hier wieder in das
> ursprüngliche zurückkopieren.
Kann es sein, daß hier bereits die Lösung der Aufgabe steht? Du nimmst halt ein Array, daß für 100n Elemente Platz hat und gehst dein zu sortierendes Array einmal von Anfang bis Ende durch, wobei du jedes Element in das andere Array "kopierst", indem du jedes Element als einen Addressierungsindex einer Zelle des 100n-Array betrachtest. (D.h. das 100n-Array könnte z.B. ein Boolean-Array sein, wobei 0 "Wert nicht benutzt" und 1 "Wert benutzt" bedeutet.) Danach gehst du das 100n-Array nocheinmal durch und schreibst den Index jeder Zelle, wo eine 1 steht in dein ursprüngliches Array. Damit brauchst du n Schritte für das "Kopieren" in, und 100n Schritte für das "Rückkopieren" aus dem 100n-Array. Wegen [mm]101n\in\mathcal{O}(n)[/mm] wäre dieser Sortiervorgang linear. (Du "tauschst" hier quasi benötigte Sortierzeit gegen höheren Speicherplatzbedarf.)
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:28 Mo 04.06.2007 | | Autor: | Marc |
Hallo zusammen,
> > Hinweis: Das Sortieren muss nicht innerhalb des Arrays
> > erfolgen. Man kann die
> > gegebenen Werte in ein anderes Array übertragen und von
> > hier wieder in das
> > ursprüngliche zurückkopieren.
>
>
> Kann es sein, daß hier bereits die Lösung der Aufgabe
> steht? Du nimmst halt ein Array, daß für 100n Elemente
> Platz hat und gehst dein zu sortierendes Array einmal von
> Anfang bis Ende durch, wobei du jedes Element in das andere
> Array "kopierst", indem du jedes Element als einen
> Addressierungsindex einer Zelle des 100n-Array betrachtest.
> (D.h. das 100n-Array könnte z.B. ein Boolean-Array sein,
> wobei 0 "Wert nicht benutzt" und 1 "Wert benutzt"
> bedeutet.)
Ergänzung: Wenn Werte auch mehrfach auftreten können, dann wählt man für das Array ein einen Integer-Datentyp, der Zahlen von 0..n darstellen kann.
> Danach gehst du das 100n-Array nocheinmal durch
> und schreibst den Index jeder Zelle, wo eine 1 steht in
> dein ursprüngliches Array. Damit brauchst du n Schritte für
> das "Kopieren" in, und 100n Schritte für das "Rückkopieren"
> aus dem 100n-Array.
Und 100n Schritte für das Initialisieren des Arrays mit 0en 
> Wegen [mm]101n\in\mathcal{O}(n)[/mm] wäre dieser
> Sortiervorgang linear. (Du "tauschst" hier quasi benötigte
> Sortierzeit gegen höheren Speicherplatzbedarf.)
Viele Grüße,
Marc
|
|
|
|
