Um den Quicksortalgorithmus besser verstehen zu können, habe ich (bzw. sollte ich) ein Javaprogramm schreiben, das den Sortiervorgang darstellt. Diese Version stellt den Vorgang dabei als Histogramm dar.
/**
* Quicksort
*
* Visualisierung des Algorithmus
* Phillip Berndt
*
*/
import javax.swing.*;
import java.awt.*;
import java.awt.image.*;
public class Quicksort extends JFrame
{
int[] zahlen;
public static void main(String arg[])
{
new Quicksort();
}
public Quicksort()
{
// Form initialisieren
super("Quicksort Demo");
setSize(400, 300);
setDefaultCloseOperation(EXIT_ON_CLOSE);
setBackground(Color.white);
// Zufällige Zahlen speichern
zahlen = new int[15];
for(int i=0; i<15; i++)
zahlen[i] = (int)Math.round(Math.random() * 30);
// Zeichnen
show();
// Sortieren
quickSort(zahlen);
}
public void paint(Graphics gra)
{
// Zahlen zeichnen
gra.setColor(Color.white);
gra.fillRect(0, 0, getWidth(), getHeight());
int width = (int)(getWidth() / 16);
int left = 0;
int top = getHeight() - 20;
int height = (int)((getHeight() - 40) / 30);
gra.setColor(Color.red);
for(int i=0; i<15; i++)
{
left += width;
gra.fill3DRect(left, top - height * zahlen[i], 10, height * zahlen[i], true);
}
}
private void swapDraw(int[] Array, int swap1, int swap2, int pivot, int leftBorder, int rightBorder)
{
swap(Array, swap1, swap2);
// Animiert zeichnen, dabei Buffer verwenden
BufferedImage newGraph = ((Graphics2D)getGraphics()).getDeviceConfiguration().createCompatibleImage(
getWidth(), getHeight(), Transparency.TRANSLUCENT);
Graphics gra = newGraph.getGraphics();
gra.setColor(Color.white);
gra.fillRect(0, 0, getWidth(), getHeight());
int width = (int)(getWidth() / 16);
int left = 0;
int top = getHeight() - 20;
int height = (int)((getHeight() - 40) / 30);
for(int i=0; i<15; i++)
{
if(i != pivot)
gra.setColor(Color.red);
else
gra.setColor(Color.green);
if(i == swap1 || i == swap2)
gra.setColor(gra.getColor().brighter().brighter().brighter());
left += width;
gra.fill3DRect(left, top - height * zahlen[i], 10, height * zahlen[i], true);
gra.setColor(Color.black);
if(i == leftBorder)
gra.fillRect(left, top - height * zahlen[i], 3, height * zahlen[i]);
else if(i == rightBorder)
gra.fillRect(left + 10 - 3, top - height * zahlen[i], 3, height * zahlen[i]);
}
getGraphics().drawImage(newGraph, 0, 0, this);
try { Thread.sleep(300); } catch(Exception e) { }
}
/** Wichtige Funktionen für Quicksort */
private void swap(int[] Array, int i, int j)
{
int tmp = Array[i];
Array[i] = Array[j];
Array[j] = tmp;
}
/** Ab hier das eigentliche Quicksort */
public void quickSort(int[] Array)
{
_quickSort(Array, 0, Array.length - 1);
}
private void _quickSort(int[] Array, int left, int right)
{
if(right > left)
{
int index = left + (int)((right - left) / 2);
int pivot = Array[index];
// swap(Array, index, right)
swapDraw(Array, index, right, index, left, right);
index = left;
for(int i = index; i < right; ++i)
{
if(Array[i] < pivot)
// swap(Array, index++, i)
swapDraw(Array, index++, i, index, left, right);
}
// swap(Array, index, right)
swapDraw(Array, index, right, index, left, right);
_quickSort(Array, left, index);
_quickSort(Array, index + 1, right);
}
}
}