Hi,
ich weiß, dass es ja Formeln gibt, die den Aufwand eines Sortierverfahrens beschreibeb, dies aber allerdings immer nur im schlimmsten Fall zutrifft.
Zu meinem Problem:

ich habe drei Listboxen (Gerade Zahlen, Ungerade Zahlen, Primzahlen), die mit Verschiedenen Sortierverfahen sortiert werden sollen.
In den Listen befinden sich meistens 100 oder mehr Items und hier ist mehr erst der imense Aufwand von z.B. Bubble-Sort aufgefallen, als ich mir mal die Verschiebungen ausgegeben habe.
Nun möchte ich den Fortschritt des Sortierens mit einer Progressbar veranschaulichen.
Gibt es jetzt eine Möglichkeit (bestimmt... ), dass zu machen, da man die ANzahl der SOrtierschritte ja nicht kennt?

Bin für Hinweise gerne offen...

Du kannst ja beim Bubble-Sort zum Beispiel zählen, wie viele Einträge in einem Durchlauf vertauscht wurden. Wenn die Zahl bei 0 angelangt ist, ist die Sortierung ja fertig. Jetzt könntest du schauen, wieviel Durchläufe durchschnittlich bei x Zahlen benötigt werden, und daraus kannst du dann eine ungefähre Prozent-Angabe machen. Natürlich ist das resultierende Ergebnis sehr ungenau, vielleicht hat ja jemand eine bessere Idee.

Es gibt verschiedene Maße für den Grad der Vorsortierung. Z.B. die Länge der längsten sortierten Teilfolge, die Anzahl der zusammenhängenden sortierten Teilfolgen, Anzahl der Fehlstellungen etc. Leider kann man auch daran nicht unbedingt feststellen, wie lange ein Verfahren benötigt, da jedes Verfahren unterschiedlich gut oder schlecht darauf reagiert.

Beispiel: Zahlenfolge 2,3,4,...,N,1. Ist so gut wie sortiert, aber für Bubblesort ist das der Worstcase. Es sei denn, man implementiert in andersrum oder nimmt Varianten wie Shakersort (ich glaub, so heißt der).

Man könnte überlegen, für welches Verfahren welches Maß halbwegs geeignet ist, das nach jedem Durchlauf bestimmen lassen und daran die Fortschrittsanzeige ausrichten. 100%ig wird man das wahrscheinlich nicht hinbekommen, und die einzelnen Maße zu bestimmen ist nicht unbedingt trivial - die Laufzeit wird dadurch wahrscheinlich signifikant steigen.

Also in der Urform ohne vorzeitigen Abbruch ist die Zahl der Schleifendurchgänge klar. Wird vorher abgebrochen(also eine optimierte Variante genommen), gilt das, was meine Vorredner gesagt haben.
www.sortieralgorithmen.de

BTW:

Stinger47 hat folgendes geschrieben:

Hi, ich weiß, dass es ja Formeln gibt, die den Aufwand eines Sortierverfahrens beschreibeb, dies aber allerdings immer nur im schlimmsten Fall zutrifft.

Nö, die beschreiben nicht immer den schlimmsten Fall. Manchmal auch den besten. Allerdings handelt es sich dabei meist um obere bzw. untere Schranken(Landau-Notation). Siehe hierzu: r2c2.weingut-rehn.de/facharbeit.htm

mfg

Christian

danke ersteinmal für die Antworten...
Vielleicht fällt einigen ja dazu noch etwas ein. Werde den Links mal folgen und schauen wie ich es weiter angehe

LG