Sortieren in linearer Zeit < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:46 Fr 15.05.2009 | | Autor: | farnold |
| Aufgabe | | Wie kann man n ganze Zahlen (typ int) im Bereich von 0 bis (n²-1) in linearer Zeit (d.h. Komplexität O(n)) sortieren? |
Hallo,
Mein erster Gedanke war RadixSort, ich habe zahlen in der form "abcde" sortiere zuerst alle zahlen nach e, dann nach b,... dann nach a => zahlen sind in linearer Zeit sortiert! nun ist das problem dass der Wertebereich bis n²-1 geht.
Heißt das nun, dass ich n²-1 mal sortieren muss und es in diesem fall nicht mehr linear, sondern O(nlogn) ist, oder geht soetwas mit radixsort dennoch in linearer zeit?
Was wäre wenn mein Wertebereich von 0 - n geht, könnte man es dann in linearer zeit schaffen, oder wäre dann die Komplexität O(n²)
Könnte ich statt RadixSort das ganze mit Countingsort lösen oder mit welchem Sortieralgorithmus würdet ihr diese Aufgabe lösen?
|
|
| |
|
| Status: |
(Antwort) fehlerhaft  | | Datum: | 08:07 Sa 16.05.2009 | | Autor: | nikito |
Da der Wertebereich ja nach oben begrenzt ist würde ich spontan sagen, dass du ein Lösungsarray mit [mm] n^2 [/mm] Felder anlegst. Das entspricht dann einer Indizierung von 0 - [mm] n^2-1. [/mm] Dann gehst du deine zu sortierendes Array durch und schiebst jedes Element entsprechend seines Wertes in das Lösungsarray. Das läuft dann in O(n). Hat aber den Nachteil das es [mm] n^2 [/mm] - n leere Felder gibt.
Pseudocode:
Sort(A[n-1])
{
Array [mm] L[n^2-1]
[/mm]
for i = 0 to n-1
do L[A[i]] := A[i]
return L
}
Das wars dann schon.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:27 Sa 16.05.2009 | | Autor: | farnold |
hm aber wenn ich das Hilfsarray ausgebe oder die Daten in eins der Größe n speicher will, bekomme ich eine Komplexität von O(n²)
code:
for(int i=0 ; i<n² ; i++)
{
if(Hilfsarray[i] != empty)
cout << Hilfsarray[i]
}
=> O(n²).
|
|
|
| |
|
Hallo farnold,
> hm aber wenn ich das Hilfsarray ausgebe oder die Daten in
> eins der Größe n speicher will, bekomme ich eine
> Komplexität von O(n²)
Eigentlich hast du diese Komplexität bereits vorher bei dem vorgeschlagenen Sortierverfahren, denn dort muß ja auch das komplette Array durchlaufen werden. Und da es nunmal [mm]n^2-1[/mm] Elemente hat, und du keine genauere Information über die Startanordnung der Arrayelemente hast, mußt du alle Elemente des Arrays wenigstens einmal betrachten.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 15:52 Sa 16.05.2009 | | Autor: | farnold |
also ist es in O(n) nicht zu schaffen und die frage ist falsch gestellt?
habe hier noch einen interessanten ansatz gefunden:
http://cgg.unibe.ch/teaching/courses/fruhlingssemester-2009/datenstrukturen-algorithmen/04%20Sortieren%20II.pdf
ab Folie 23
nur die Frage bezieht sich das nun auf CountingSort oder auf RadixSort? ICh würde Radix sagen, da man versuch die länge zu verkleinern indem man die zahlen bezüglich anderen Basen darstellt, aber auf den Folien könnte man meinen es sei für Counting sort.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:21 Mo 18.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:56 Di 19.05.2009 | | Autor: | bazzzty |
> also ist es in O(n) nicht zu schaffen und die frage ist
> falsch gestellt?
Es ist nicht mit einem Hilfsarray zu schaffen, wie Nikito es vorgeschlagen hat.
> habe hier noch einen interessanten ansatz gefunden:
>
> http://cgg.unibe.ch/teaching/courses/fruhlingssemester-2009/datenstrukturen-algorithmen/04%20Sortieren%20II.pdf
> ab Folie 23
>
> nur die Frage bezieht sich das nun auf CountingSort oder
> auf RadixSort? ICh würde Radix sagen, da man versuch die
> länge zu verkleinern indem man die zahlen bezüglich anderen
> Basen darstellt, aber auf den Folien könnte man meinen es
> sei für Counting sort.
Ich habe mir die Folien nicht angeschaut, aber ich würde Radixsort verwenden. Bei Schlüsselmenge [mm] M^k [/mm] kann man n Werte in O(k*(n+|M|)) sortieren, und wenn man die Werte n-adisch darstellt, ist M={0,..,n-1} und k in diesem Fall =2. Das ist die klassische Anwednung von Radixsort.
|
|
|
| |
|
| Status: |
(Korrektur) fundamentaler Fehler  | | Datum: | 13:53 Di 19.05.2009 | | Autor: | bazzzty |
Das Einsammeln der Werte aus dem Hilfsarray (sowie das Anlegen) benötigen schon quadratische Laufzeit.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:52 Di 19.05.2009 | | Autor: | bazzzty |
> Wie kann man n ganze Zahlen (typ int) im Bereich von 0 bis
> (n²-1) in linearer Zeit (d.h. Komplexität O(n)) sortieren?
Ich komme vielleicht zu spät, um noch hilfreich zu sein, aber Radixsort ist schon die Lösung.
Zunächst schreibst Du jede Zahl im Bereich nicht dezimal, sondern n-adisch. Heißt: Ist n=23, dann schreibst Du 400 = 17*23+9, oder kurz (17,9). So geschrieben sortierst Du erst per Bucketsort nach der zweiten Komponente, und dann stabil nach der ersten. Beide Sortierdurchläufe benötigen 0(n) Zeit, und danach ist alles sortiert.
|
|
|
|
