import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.border.*;

public class SortSampleApplet extends JApplet {
	private JComboBox cboSort;
	private JLabel lblTitle;
	private Graphics g;
	private int[] sortList;
	private int height, width;

	private void drawLine(int index, boolean visible) {
	    if (visible) {
    	    g.setColor(Color.BLACK);
	    } else {
    	    g.setColor(Color.LIGHT_GRAY);
	    }
    	g.drawLine(index, height, index, height - sortList[index]);
	}

	private void swap(int index1, int index2) {
    	drawLine(index1, false);
	    drawLine(index2, false);
		
	    int index3 = sortList[index1];
	    sortList[index1] = sortList[index2];
    	sortList[index2] = index3;
		
	    drawLine(index1, true);
    	drawLine(index2, true);
	}

	public SortSampleApplet() {
		JPanel pnlContent = (JPanel) getContentPane();
		pnlContent.setLayout(new BorderLayout());
		
		cboSort = new JComboBox();
    	cboSort.addItem("Quick Sort");
	    cboSort.addItem("Bubble Sort");
    	cboSort.addItem("Selection Sort");
	    cboSort.addItem("Insersion Sort");
    	cboSort.addItem("Heap Sort");
	    cboSort.addItem("Shell Sort");
	    
    	pnlContent.add(cboSort, BorderLayout.NORTH);
		
		final JPanel pnlGraphics = new JPanel();
		pnlGraphics.setBorder(new BevelBorder (BevelBorder.LOWERED));
		pnlContent.add(pnlGraphics, BorderLayout.CENTER);
		
		JPanel pnlButton = new JPanel();
		pnlContent.add(pnlButton, BorderLayout.SOUTH);
		
		JButton btnRandomize = new JButton("Randomize");
		btnRandomize.addActionListener (new ActionListener() {
      		public void actionPerformed(ActionEvent e) {
				java.util.Random r = new java.util.Random();
				g = pnlGraphics.getGraphics();
				width = pnlGraphics.getWidth();
				height = pnlGraphics.getHeight();
				sortList = new int[width];
	    	    g.setColor(Color.LIGHT_GRAY);
		    	g.clearRect(0, 0, width - 1, height - 1);
		    	
		    	for (int index = 0; index < width; index++) {
		        	sortList[index] = r.nextInt(height);
		        	drawLine(index, true);
		    	}
      		}
	    });
		pnlButton.add(btnRandomize);
		
		JButton btnSort = new JButton("Sort");
		btnSort.addActionListener (new ActionListener() {
      		public void actionPerformed(ActionEvent e) {
      		
      			String data = "Height - " + height + ", Width - " + width;
      			
      			java.util.Date dt1 = new java.util.Date();
      			long tm1 = dt1.getTime();

		    	int index = cboSort.getSelectedIndex();
			    if (index == 0) {
		    	    quickSort(0, sortList.length - 1);
			    } else if (index == 1) {
			        bubbleSort();
			    } else if (index == 2) {
			        selectionSort();
			    } else if (index == 3) {
			        insersionSort();
			    } else if (index == 4) {
			        heapSort();
			    } else if (index == 5) {
			        shellSort();
			    }
			    
      			java.util.Date dt2 = new java.util.Date();
      			long tm2 = dt2.getTime();
      			
      			long tm3 = tm2 - tm1;
      			
      			data = "Height - " + height + ", Width - " + width + ", Time - " + tm3 + " ms";
      			lblTitle.setText(data);
      			
      		}
	    });
		pnlButton.add(btnSort);
		
		lblTitle = new JLabel();
		pnlButton.add(lblTitle);
	}
	
	//#############################################################
	private void bubbleSort() {
	    for (int index1 = 0; index1 <= sortList.length - 2; index1++) {
	        for (int index2 = 1; index2 <= sortList.length - 1 - index1; index2++) {
	            if (sortList[index2 - 1] > sortList[index2]) {
	                swap(index2 - 1, index2);
	            }
	        }
	    }
	}
	
	private void quickSort(int start, int finish) {
	    if (start < finish) {
	        int first = start;
	        int last = finish;
	        int pivot = sortList[first];
	        while (first <= last) {
	            while (first <= last && sortList[first] <= pivot) {
	                first = first + 1;
	            }
	            while (first <= last && sortList[last] > pivot) {
	                last = last - 1;
	            }
	            if (first < last) {
	                swap(first, last);
	            }
	        }
	        swap(start, last);
	        quickSort(start, last - 1);
	        quickSort(last + 1, finish);
	    }
	}
	
	private void selectionSort() {
	    for (int index1 = 0; index1 <= sortList.length - 2; index1++) {
	        int index3 = index1;
	        for (int index2 = index1 + 1; index2 <= sortList.length - 1; index2++) {
	            if (sortList[index3] > sortList[index2]) {
	                index3 = index2;
	            }
	        }
	        if (index1 != index3) {
	            swap(index1, index3);
	        }
	    }
	}
	
	private void insersionSort() {
	    for (int index1 = 1; index1 <= sortList.length - 1; index1++) {
	        for (int index2 = index1; index2 >= 1; index2--) {
	            if (sortList[index2 - 1] > sortList[index2]) {
	                swap(index2 - 1, index2);
	            } else {
	                break;
	            }
	        }
	    }
	}
	
	private void heapSort() {
	    //Sorts array in place using a heap data structure
	    int heapsize = sortList.length;
	    for (int index = heapsize / 2; index >= 1; index--) {
	        heapify(index, heapsize);
	    }
	    for (int index = heapsize; index >= 2; index--) {
	        swap(0, index - 1);
	        heapsize = heapsize - 1;
	        heapify(1, heapsize);
	    }
	}
	
	private void heapify(int index, int heapsize) {
	    // SortList(index) may be smaller than its children, so let SortList(index) "float down"
	    // in the heap so that the subtree rooted at index becomes a heap
	    int l = 2 * index;
	    int r = 2 * index + 1;
	
	    int largest = index; //becomes the largest of SortList(index), SortList(2 * index), & SortList(2 * index + 1)
	
	    if (l <= heapsize) {
	        if (sortList[l - 1] > sortList[index - 1]) {
	            largest = l;
	        }
	    }
	
	    if (r <= heapsize) {
	        if (sortList[r - 1] > sortList[largest - 1]) {
	            largest = r;
	        }
	    }
	
	    if (largest != index) {
	        swap(index - 1, largest - 1);
	        heapify(largest, heapsize);
	    }
	}
	
	private void shellSort() {
		int block = 0;
		
	    // find the best value for block
        do {
	        block = block * 3 + 1;
		} while (block <= sortList.length - 1);
	
	    do { // Until block = 1
	        block = block / 3;
	        for (int blockindex = 1; blockindex <= block; blockindex++) {
	            for (int index1 = blockindex; index1 <= sortList.length - 1; index1 = index1 + block) {
	                for (int index2 = index1; index2 >= 1; index2 = index2 - block) {
	                    if (index2 - block >= 0) {
	                        if (sortList[index2 - block] > sortList[index2]) {
	                            swap(index2 - block, index2);
	                        } else {
	                            break;
	                        }
	                    } else {
	                        break;
	                    }
	                }
	            }
	        }
	    } while (block > 1);
	}
	//#############################################################
}