Vergleichen Sie den Sortieralgorithmus
Ich habe verschiedene Arten der Sortierung implementiert (Bubble, Insertion, Selection). Ich weiß, dass ich ihre Implementierungen wie folgt für jede Sorte vergleichen möchte (hier ist ein Beispiel mit der Blasensortierung):
Hier ist zum Beispiel meine Blase sortieren:
%Vor% Ich habe die GUI gestartet und ich habe 1000 zufällige Punkte darauf und die Zeile y=x :
Folgendes habe ich getan:
Jetzt bin ich fest, ich habe keine Ahnung, wie ich anfangen soll. Könnte jemand mir die Schritte / Hinweise angeben, die folgen müssen, um das zu implementieren?
Danke:)
4 Antworten
Sie müssen definieren, was die Punkte bedeuten. Betrachtet man die Animation, sieht es so aus, als ob die y-Achse ein value darstellt, während die x-Achse das position im Array dieses Wertes darstellt.
In Ihrer Methode paint würden Sie dann die Liste der Elemente durchgehen und einen Punkt malen, wobei der x-Punkt die Position im Array und der y-Punkt eine Position auf der y-Achse ist. Angenommen, die Werte liegen in einem bekannten Bereich.
Denken Sie auch daran, dass die y-Achse in Grafiken mit 0 am Anfang beginnt. Daher müssen Sie möglicherweise einige Werte in Koordinaten umrechnen (je nachdem, wie Sie es aussehen lassen möchten).
Der einfachste Weg wäre, Ihre Malmethode in eine Methode umzuwandeln, bei der anstelle von zufälligen Punkten ein vordefinierter List der Punkte als Parameter verwendet wird. Übergeben Sie bei jeder Iteration Ihrer Sortiermethode das sortierte Array in die Paint-Methode und zeichnen Sie die Punkte neu.
Sie müssen
- Erstellen Sie ein
int[]-Array mit zufälligen Werten als Elementvariable. Lassen Sie uns das Arraydataaufrufen. Sie möchten wahrscheinlich mit einer festen Array-Größe und einem Bereich von jeweils 100 beginnen. Sie können die Werte später an die Fenstergröße anpassen, wenn eine einfache Version funktioniert. Es kann sogar noch besser sein, bei einer festen Größe und einem festen Bereich zu bleiben und nur auf den verfügbaren Platz inpaintComponentzu skalieren, was das Verhalten unabhängig von der Fenstergröße macht. - Ändern Sie
paintComponentin Schleife überdata. Der Schleifenindex ist Ihr x-Wert unddata[x]bestimmt den y-Wert. - Testen Sie, dass der Code immer noch das ursprüngliche zufällige Array zeichnet. Es ist mir egal, ob es sich gerade jetzt in der linken Ecke befindet, das kannst du reparieren, wenn die Animation funktioniert.
- Sie müssen der innersten Schleife Ihrer Sortiermethode eine Art
sleep()-Aufruf hinzufügen, damit Sie die Schritte beobachten können. Andernfalls wird sogar bubblesort zu schnell sein, um zu beobachten. Ich würde empfehlen, mit einer Sekunde zu beginnen (Parameterwert 1000). Mach es später schneller, wenn alles funktioniert. - Starten Sie die Methode
bubbleSortin einem neuen Thread und stellen Sie sicher, dass Ihre Komponente bei jedem Schritt neu gezeichnet wird. Dies kann der schwierigste Teil sein. Vielleicht geben Sie die Komponente an diebublleSort-Methode weiter (oder machenbubbleSortzu einer nicht statischen Methode der Komponente) und lassen sie bei jedem Schritt einerepaint()anfordern (glücklicherweise ist dies eine der wenigen thread-sicheren Methoden in Schaukel). - Optimieren Sie Ihren Code: Skalieren Sie die x- und y-Koordinaten, indem Sie mit dem verfügbaren Platz multiplizieren und dann durch die Array-Größe oder den Wertebereich dividieren. Passen Sie die Ruhezeit nach Bedarf an. Fügen Sie Unterstützung für verschiedene Sortieralgorithmen hinzu ....
Wenn einer der Schritte unklar ist, fügen Sie einen Kommentar hinzu.
Ich habe dies für meine Bachelorthesis getan, ich habe es so gemacht ( es ist nicht perfekt, aber es könnte dir helfen ):
(Ich entfernte einige unwichtige Methoden / Funktionen aus dem unten stehenden Code. Es soll hauptsächlich veranschaulichen, wie ich es visualisiert habe. Sie können die GRectangle-Klasse beispielsweise durch einen einfachen java.awt.Point ersetzen.)
Die Initialisierungsmethode gibt Ihnen ein Beispiel dafür, wie Sie den maximalen und minimalen Wert der Daten finden können, damit Sie wissen, wie Sie Ihre Datenwerte transformieren können = & gt; Koordinaten.
%Vor%Berücksichtigen Sie dies: Die Visualisierung von ganzen Zahlen zwischen 0 und 150 auf einer Höhe von 150 Pixeln ist einfach. Das Anzeigen eines Satzes von ganzen Zahlen zwischen den Werten 565 und 3544545 auf einer Höhe von 150 ist etwas weniger.
PS: Der Code verwendet den Index des Elements im Eingabearray als X-Koordinate.
PS: Die Klasse behält einen Verweis auf das Inputarray (Variable m_data), aber das ist natürlich nicht erforderlich, Sie brauchen es nur, um Ihre Punkte zu initialisieren.
PS: Meine "Visualisierungs" -Klasse, die um alle Visualisierungen erweitert wird, ist grundsätzlich ein JPanel.
PS: Der Code oben ist für positive ganze Zahlen geschrieben, so wird wahrscheinlich einige zusätzliche Codierung benötigt, um auch negative ganze Zahlen zu behandeln;).
Um die Aktionen des Algorithmus zu visualisieren, verwendete ich das Beobachtermuster. Der Algorithmus, zum Beispiel bubblesort, sah so aus:
%Vor%Wo der Funktionsaustausch wie folgt definiert wurde (vereinfachte Version):
%Vor%Wo ich meinen Beobachtern (Visualisierungen) mitgeteilt habe, dass ein Swap auf index1 und index2 stattgefunden hat. Die m_command-Variable ist eine Instanz der Command-Klasse (schrieb sie selbst), die nur ein Wrapper für die Informationen ist, die für die Visualisierung benötigt werden. Was ist: die aufgetretene Aktion und die relevanten Informationen (zB Indizes für eine Tauschaktion).
Also habe ich in der Visualisierung die GRectangles auf diesen Indizes sowie deren X-Koordinaten getauscht;
%Vor%Sie können Zeilen wie folgt hinzufügen:
%Vor%Lassen Sie einen Thread 100ms schlafen, bevor Sie fortfahren. Dies kann nützlich sein, wenn es zu schnell visualisiert wird.
Für ein Array mit zufälligen Ganzzahlen könnte es so aussehen:
Und nach dem Sortieren: (Natürlich ist es keine gerade Linie, weil die Werte im Inputarray in diesem Fall zufällig erzeugt wurden)
Wenn Sie also - wie ich musste - mehreren Algorithmen erlauben, mit derselben Visualisierung zu arbeiten, kann ich Ihnen empfehlen, die Visualisierungsklasse und die Algorithmusklasse zu trennen und mit einem Beobachtermuster zu arbeiten, damit die Visualisierung jedes Mal aktualisiert wird Aktion tritt auf (set, swap, ...).
Und dann können Sie so etwas für Vergleiche erstellen;
Viel Glück!
Tags und Links java user-interface swing sorting paintcomponent