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 in einem zweidimensionalen Koordinatensystem dar.
/**
* Quicksort
*
* Alternative 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 (Alternative Darstellung)");
setSize(500, 500);
setDefaultCloseOperation(EXIT_ON_CLOSE);
setBackground(Color.white);
// Zufällige Zahlen speichern
zahlen = new int[250];
for(int i=1; i<=250; i++)
{
int pos = 0;
while(zahlen[pos] != 0)
pos = (int)Math.round(Math.random() * 249);
zahlen[pos] = i;
}
// Zeichnen
show();
// Sortieren
quickSort(zahlen);
}
public void paint(Graphics gra)
{
// Weiß füllen
gra.setColor(Color.white);
gra.fillRect(0, 0, getWidth(), getHeight());
// Punkte zeichnen
gra.setColor(Color.red);
for(int i=0; i<250; i++)
gra.drawRect(zahlen[i] * 2, i * 2, 2, 2);
}
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());
for(int i=0; i<250; i++)
{
if(i == pivot)
{
gra.fillRect(zahlen[i] * 2, i * 2, 3, 3);
gra.setColor(Color.green);
}
else if(i == swap1 || i == swap2)
{
gra.setColor(Color.blue);
gra.fillRect(zahlen[i] * 2, i * 2, 3, 3);
}
else if(i == leftBorder || i == rightBorder)
{
gra.setColor(Color.black);
gra.fillRect(zahlen[i] * 2, i * 2, 3, 3);
}
else
{
gra.setColor(Color.red);
gra.drawRect(zahlen[i] * 2, i * 2, 2, 2);
}
}
getGraphics().drawImage(newGraph, 0, 0, this);
}
/** 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);
}
}
}