/**
 * 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);
		}
	}
}