Fortschritt von Quicksort teilen

Question

Ich arbeite gerade an der Sortierung von Dateien. Im Moment benutze ich Heapsort, weil es ziemlich einfach ist, den Fortschritt davon zu erzählen. Ich meine, es gibt zwei Loops hintereinander und mit einigen leichten Anpassungen, wie viel Gewicht Sie eine Runde von jedem der beiden Schleifen geben Sie haben eine sehr gute Schätzung des aktuellen Fortschritts und die Anzeige eines Fortschrittsbalken könnte nicht einfacher sein.

Da Quicksort in den meisten Fällen schneller als Heapsort ist, möchte ich das stattdessen verwenden, aber ich bin nicht sicher, wie ich den Fortschritt davon erzählen soll.

Answer 1

Es gibt drei Stufen:

• Getrennte Elemente in zwei Listen

• Sortieren linke Liste

• sortieren rechts Liste

Sie jeden Schritt eine geben kann Teil des Fortschritts, den es während der Ausführung zu füllen hat. Sagen wir, es gibt 100% insgesamt. Schritt 1 erhält 20%, Schritt 2 40% und Schritt 3 ebenfalls 40% unter der Annahme, dass beide Listen dieselbe Größe haben. Dies kann rekursiv fortgesetzt werden.

Die Frage ist, wie groß der Bruchteil jedes Schrittes tatsächlich ist. Die durchschnittliche Zeitkomplexität von Quicksort ist n*log(n). Nehmen wir an, es dauert total = c*n*log(n) Vergleiche, um eine Liste mit n Elementen zu sortieren. Das Sortieren einer Unterliste mit der Größe n*f (f < 1) ergibt die folgende Anzahl von Vergleichen.

c*(n*f)*log(n*f) = 
c*(n*f)*(log(n)+log(f)) = 
(c*n*log(n))*f + c*n*log(f)*f = 
total*f + c*n*log(f)*f 

c*n*log(f)*f ist negativ, weil f < 1. Die andere Unterliste benötigt total*(1-f) + c*n*log(1-f)*(1-f) Vergleiche. Also, der erste Schritt benötigt die folgende Anzahl von Vergleichen.

total - (total*f + c*n*log(f)*f) - (total*(1-f) + c*n*log(1-f)*(1-f)) = 
total - total*f - total*(1-f) - (c*n*log(f)*f) - (c*n*log(1-f)*(1-f)) = 
- (c*n*log(f)*f) - (c*n*log(1-f)*(1-f)) = 
- c*n*(log(f)*f+log(1-f)*(1-f)) 

Die verbleibende Frage ist: Was ist der Wert von c ist? Wenn c bekannt ist und ich keinen Fehler gemacht habe, sollte es möglich sein, die durchschnittlichen Zeitanteile der drei Schritte mit den obigen Formeln zu berechnen.