matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAlgorithmen und DatenstrukturenSortieren in linearer Zeit
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Algorithmen und Datenstrukturen" - Sortieren in linearer Zeit
Sortieren in linearer Zeit < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Sortieren in linearer Zeit: Aufgabe
Status: (Frage) beantwortet Status 
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?

        
Bezug
Sortieren in linearer Zeit: Idee
Status: (Antwort) fehlerhaft Status 
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.




Bezug
                
Bezug
Sortieren in linearer Zeit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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²).

Bezug
                        
Bezug
Sortieren in linearer Zeit: Antwort
Status: (Antwort) fertig Status 
Datum: 14:43 Sa 16.05.2009
Autor: Karl_Pech

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




Bezug
                                
Bezug
Sortieren in linearer Zeit: Frage (überfällig)
Status: (Frage) überfällig Status 
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.

Bezug
                                        
Bezug
Sortieren in linearer Zeit: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:21 Mo 18.05.2009
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
                                        
Bezug
Sortieren in linearer Zeit: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                
Bezug
Sortieren in linearer Zeit: Korrekturmitteilung
Status: (Korrektur) fundamentaler Fehler Status 
Datum: 13:53 Di 19.05.2009
Autor: bazzzty

Das Einsammeln der Werte aus dem Hilfsarray (sowie das Anlegen) benötigen schon quadratische Laufzeit.

Bezug
        
Bezug
Sortieren in linearer Zeit: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]