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