Array

[Moeki]

In einem Array der Größe n seien nur die Werte rot, blau, grün gespeichert. Das Array soll so sortiert werden, daß zunächst alle roten, dann alle grünen und zuletzt alle blauen Farben vorkommen. Die einzigen erlaubten

Zugriffsoperationen auf das Array sind

test(i): Liefert die Farbe der i-ten Komponente

tausch(i,j): tauscht die Inhalte der beiden Komponenten i und j

Schreiben Sie einen Algorithmus, der das Array in situ in O(n) Zeit sortiert. Zeigen Sie, daß Ihr Algorithmus in O(n) Schritten (also linear) terminiert und daß das Array dann tatsächlich sortiert ist.

Dieses Problem müsste man doch eigentlich rekursiv lösen oder? Quasi indem ich das Feld durchlaufe, solange die Bedingung rot < grün < blau erfüllt ist und andernfalls zwei Elemente tausche. Muss ich nun erst die ganze Liste einmal durchgehen, dabei alle relevanten Paare tauschen und danach die Liste von vorne beginnen oder welche Vorgehensweise empfiehlt ihr mir?

Danke, Moeki.

[Muadibb]

Klingt für mich stark nach Bubble Sort

Ich denke, das beantwortet alles, ausser den mathematischen Nachweis zur Komplexität

[perdian]

Dieses Problem müsste man doch eigentlich rekursiv lösen oder?

Warum müsste?

Rekursiv oder iterativ - beides ist möglich, in der Aufgabenstellung steht nix.

Allgemein dürfte dir das hier weiterhelfen:

http://www.sortieralgorithmen.de/

[Moeki]

Bubble Sort ist iterativ und die Laufzeit n^2. n^2 ist doch nicht linear oder?

[perdian]

Bubble Sort ist iterativ und die Laufzeit n^2. n^2 ist doch nicht linear oder?

Nein, ist es nicht - die Frage hast du dir doch schon selbst beantwortet, oder?

n != n^2

[Muadibb]

Mal eine bescheidende Frage:

Gibt es überhaupt einen Sortieralgorhitmus, der O(n) hat?

Oder liegt das nur an der Aufgabenstellung, dass man bei 3 verschiedenen Elementen O(n) erreichen kann?

[perdian]

Gibt es überhaupt einen Sortieralgorhitmus, der O(n) hat?

Das kommt immer auf die Datenstruktur an. Wenn ich ziemlich genau weiss, welche Daten ich zum Sortieren bekomme, und in welcher Art und Weise diese sortiert werden müssen, in welcher Art vielleicht schon eine Vorsortierung stattgefunden hat, und letzen Endes alles ideal abläuft, dann ist jede Laufzeit denkbar. Theoretisch sogar O(1).

Ein allgemeiner Sortieralgorithmus wird allerdings niemals schneller als O(n·log(n)) sein können.

Siehe auch: http://de.wikipedia.org/wiki/Sortierverfahren

[piomode1]

Hi, perdi!

n != n^2

Und dann kommt da so ein Klug******er und muß seinen Senf dazu abgeben:

n <> n^2, für alle n <> 0 und n <> 1

[Klotzkopp]

n <> n^2, für alle n <> 0 und n <> 1

n ist hier keine Variable in einem algebraischen Ausdruck, sondern gehört zur Beschreibung einer Komplexitätsklasse. n steht hier nicht für einen Wert, den man einsetzen könnte.

[Bubble]

Mal eine bescheidende Frage:

Gibt es überhaupt einen Sortieralgorhitmus, der O(n) hat?

Nein. Der "beste" hat O(n*log(n)).

[Bubble]

Sind die Farben anfangs komplett durcheinander im Array, also "grbgrbbgbb", oder in der Form "rrbbbbbggg", die nach "rrgggbbbbb" umgewandelt werden soll? Letzteres kann in linearer Zeit umgearbeitet werden, die Sortierung einer beliebigen Anordnung nicht.

[Klotzkopp]

int i, j = 0;

for(i=0; i<size; ++i)

{

	if(test(i) == rot)

	{

		tausche(i, j);

		++j;

	}

}

for(i=j; i<size; ++i)

{

	if(test(i) == gruen)

	{

		tausche(i, j);

		++j;

	}

}[/code]
Sollte eigentlich linear sein...

[themaster]

Ja, der Algorithmus ist linear.

Mal zur Klärung: Der beste mögliche Sortieralgorithmus (! der nur auf Vergleichsoperationen basiert) hat eine Laufzeit von O(n log(n)).

Bei diesem Sortieralgorithmus wurde allerdings die Einschränkung gemacht, dass nur drei verschiedene Werte möglich sind.

Damit braucht man nicht mehr mit Vergleichsoperationen arbeiten, sondern mit dem Tauschen (ohne Vergleichen), daher ist der Algo mit O(n) möglich.