/* Автор не несет никакой ответственности за поведение сего произведения
        на вашем компьютере.
*/

import java.awt.*;
import	java.applet.*;

public class DemoSort extends Applet implements Runnable
{
	Thread		thread;
	int[]		item;
	int		N, winWidth;
	String 		sortName;	
	boolean		completed;
	Color		myOrange;
	public void init()
	{
		N		= 50;
		item		= new int[N];
		myOrange	= new Color(209, 97, 16);
		winWidth 	= size().width;
		
		setLayout( new BorderLayout() );
		setBackground(Color.white);

		if ( (sortName=getParameter("sortType")) == null)  sortName = "BubbleSort";
		prepareArray();
		repaint();	
	}//init
	
	void prepareArray()
	{
		int 	i, j;
		
		completed=false; //creation new random array 
		for ( i = 0; i < N ;i++) item[i] = i; 
		for ( i = 1; i < N ;i++){
		    j = (int)(N * Math.random());
	    	swap( item, i, j);
		}//for
	}//prepareArray

	public void run()
	{
		if (sortName.equals("ShellSort") )
			doShell();
		else if (sortName.equals("QuickSort") ) 
			doQuickSort(0, N-1);
		else if (sortName.equals("BiDirBubbleSort") )
			doBiDirBubbleSort();
		else 
			doBubbleSort();
		
		completed=true;
		repaint();
		thread.stop();
	}//run
	
	public synchronized void stop()
	{
		if (thread != null){
           try {thread.stop();}
           catch (IllegalThreadStateException e) {} // ignore this exception
        	thread = null;
       }
	}//stop

	void doBubbleSort()
	{
		int 	i, j;
		
		for (i=1; i < N; i++){
			for (j=N-1; j>=i; j--){
				if (item[j-1] > item[j]){
					 swap( item, j-1, j );
					 sleep(40);
					 repaint();
				}
			}//for j
		}
	}//doBubbleSort
	
	void doQuickSort( int left, int right)
	{
		int		i, j;
		int		center;
		
		i = left;
		j = right;	
		center = item[ (left+right)/2 ];
		while (i < =j )
		{
			while ( (item[i] < center) && (i < right ) ) i++;
			while ( (item[j] > center) && (j > left  ) ) j--;
			
			if ( i < =j ){
				swap( item, i, j);
				i++;
				j--;
				sleep(40);
				repaint();
			}
		
		} 
		if (left  < j) doQuickSort(left , j);
		if (right > i) doQuickSort(i	, right);
	}//QuickSort
	
	void doShell()
	{
		int	 i, j, gap, k;
		int		x;
		byte	a[]={37, 21, 13, 9, 5, 3, 2, 1};
		
		for(k=0; k < 8; k++){
			gap=a[k];
			for (i=gap-1; i < N; i++){
				x=item[i];
				for (j=i-gap; j>=0 && item[j]>x ;j-=gap){
					sleep(40);
					repaint();
					item[j+gap]=item[j];
				}//for j
				item[j+gap]=x;
			}//for i
		}
	}//doShell
	
	void doBiDirBubbleSort()
	{
		int j;
		int limit 	= N ;
		int st 		= -1;
		while (st < limit){
	    	boolean flipped = false;
	    	st++;
	    	limit--;
	    	for (j = st; j < limit; j++){
				if (item[j] > item[j + 1]) {
		 			swap(item, j, j+1);
		 			flipped = true;
		    		repaint();
		    		sleep(40);
				}//if
	    	}
	    	if (!flipped) {
			return;
	   		}
	    	for (j = limit; --j >= st;) {
				if (item[j] > item[j + 1]) {
		   	 		swap(item, j, j+1);
		   	 		flipped = true;
		    		repaint();
		    		sleep(40);
				}//if
	    	}
	    	if (!flipped) return;
	  	}
 	}//BiDirBubble

	void swap(int a[], int i, int j)
	{
		int swap;
		
		swap 	= a[i];
		a[i]	= a[j];
		a[j]	= swap;
	}
	
	public boolean mouseUp(Event event, int x, int y)
	{
		if ( (thread == null) || !thread.isAlive()){
			if (completed)	 { prepareArray(); repaint();}
			thread	= new Thread(this);
			thread.start();
		} 
		return true;
	}
	
	public void update(Graphics g) //do not clear the window before paint()
	{
		paint(g);
	}
	
	public void paint(Graphics g)
	{
		for(int i=0; i < N; i++){					
			g.setColor((Color)myOrange);
			g.drawLine(0,  3*i, 3*item[i], 3*i);
			g.setColor(Color.white);
			g.drawLine(3*item[i],  3*i, winWidth, 3*i);
		}
		
	}//paint
	
	void sleep(int period)
	{
		try  {Thread.sleep(period);}
		catch(InterruptedException e){};
	
	}
}//DemoSort