Forum "Algorithmen und Datenstrukturen" - Sortieren einer Folge - ev.vorhilfe.de

- Förderverein -

Der Förderverein. Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
	Hallo Gast! [ einloggen \| registrieren ]
	Startseite · Mitglieder · Impressum

Forenbaum

VH e.V.

Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation

Startseite...
Suchen
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

Weitere Fächer:

Vorhilfe.de

FunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme

Forum "Algorithmen und Datenstrukturen" - Sortieren einer Folge

Sortieren einer Folge < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe

Ansicht:

[ geschachtelt ]

Forum "Algorithmen und Datenstrukturen" |

Alle Foren |

Forenbaum | Materialien

Sortieren einer Folge: Aufgabe

Status:	(Frage) beantwortet
Datum:	16:30 Sa 17.06.2006
Autor:	Fahnder

Aufgabe

 Zeigen Sie, dass das Sortieren einer Folge a der Länge N mittels Quicksort im Best Case die Laufzeit Tmin(N) = (N · logN) hat. 

Hi,
also kann mir jemand mal sagen, was man darunter versteht? Also ich habe keine Ahnung was ich da machen soll.

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

Ich danke im Voraus

Bezug

Sortieren einer Folge: Antwort

Status:	(Antwort) fertig
Datum:	19:26 So 18.06.2006
Autor:	Bastiane

Hallo!

> Zeigen Sie, dass das Sortieren einer Folge a der Länge N
> mittels Quicksort im Best Case die Laufzeit Tmin(N) = (N ·
> logN) hat.
> Hi,
> also kann mir jemand mal sagen, was man darunter versteht?
> Also ich habe keine Ahnung was ich da machen soll.

Du verstehst also nur die Aufgabenstellung nicht!?

Das ist doch recht einfach:
Wenn du ohne irgendeinen Algorithmus sondern einfach mit dem normalen Menschenverstand eine Folge von Zahlen sortieren sollst, und die Folge schon sortiert ist, dann brauchst du gar nichts zu machen. Das hätte dann also z. B. die Laufzeit 0, oder von mir aus auch 1, wenn du das "angucken der Folge" als Zeit zählen möchtest. Wenn du Folge jetzt zum Beispiel absteigend sortiert ist, du sie aber aufsteigend sortieren sollst, dann müsstest du nichts anderes machen, als sie "umzudrehen".

Und was ist der beste Fall für Quicksort? Naja, was macht Quicksort? Es nimmt sich ein Pivotelement und schmeißt alle Elemente, die kleiner sind nach links und alle, die größer sind, nach rechts. Wenn du dabei anfangs eine sortierte Folge hast, geht das mit Quicksort nicht so schnell, wenn du z. B. das erste Element als Pivotelement wählst. Denn dann wird quasi jedes Element einmal als Pivotelement gewählt, weil alle Elemente größer sind und somit auf die selbe Seite geschmissten werden. Du hättest also N Pivotelemente.
Am besten wäre es, wenn du immer ein Pivotelement erwischst, sodass links und rechts genauso viele Elemente stehen. Und du sollst nun zeigen, dass genau dann die Laufzeit [mm] $N*\log [/mm] N$ rauskommt.

Viele Grüße
Bastiane