REF-6J   Types of sort methods   by Dane Henry

import java.util.*;

public class SortTest
	{
		public static void bubbleSort(int[] sortArray)
			{
				int pass = 1;
				boolean exchanges = false;
				do
					{
						exchanges = false;
						for (int p = 0; p < sortArray.length - pass; p++)
							{
								if (sortArray[p] > sortArray[p + 1])
									{
										int temp = sortArray[p];
										sortArray[p] = sortArray[p + 1];
										sortArray[p + 1] = temp;
										exchanges = true;
									}
							}
							pass++;
					}
					while (exchanges);
			}

		public static void selectionSort(int[] sortArray)
			{
				int w = sortArray.length;
				for (int fill = 0; fill < w - 1; fill++ )
					{
						int posMin = fill;
						for (int next = fill + 1; next < w; next++)
							{
								if(sortArray[next] < sortArray[posMin])
									{
										posMin = next;
									}
							}
						int temp = sortArray[fill];
                                                sortArray[fill] = sortArray[posMin];
						sortArray[posMin] = temp;
					}
			}

		public static void heapSort(int[] sortArray)
			{
				buildHeap(sortArray);
				shrinkHeap(sortArray);
			}
		private static void buildHeap(int[] sortArray)
			{
				int a = 1;
				while (a < sortArray.length)
					{
						a++;
						int child = a - 1;
						int parent = (child - 1)/2;
						while (parent >= 0 && sortArray[parent] < sortArray[child])
							{
								swap(sortArray, parent, child);
								child = parent;
								parent = (child - 1)/2;
							}
					}
			}
		private static void shrinkHeap(int[] sortArray)
			{
				int n = sortArray.length;
				while (n > 0)
					{
						n--;
						swap(sortArray, 0, n);
						int parent = 0;
						while (true)
							{
								int leftChild = 2 * parent + 1;
								if (leftChild >= n)
									{
										break;
									}
								int rightChild = leftChild + 1;
								int maxChild = leftChild;
								if (rightChild < n && sortArray[leftChild] < sortArray[rightChild])
									{
										maxChild = rightChild;
									}
								if (sortArray[parent] < sortArray[maxChild])
									{
										swap (sortArray, parent, maxChild);
										parent = maxChild;
									}
								else
									{
										break;
									}
							}
					}
			}


		public static void quickSort(int[] sortArray)
			{
				quickSort(sortArray, 0, sortArray.length - 1);
			}
		private static void quickSort(int[] sortArray, int first, int last)
			{
				if (first < last)
					{
						int pivIndex = partition(sortArray, first, last);
						quickSort(sortArray, first, pivIndex - 1);
						quickSort(sortArray, pivIndex + 1, last);
					}
			}
		private static int partition(int[] sortArray, int first, int last)
			{
				int pivot = sortArray[first];
				int up = first;
				int down = last;
				do
					{
						while ((up < last) && (pivot >= sortArray[up]))
							{
								up++;
							}
						while (pivot < sortArray[down])
							{
								down--;
							}
						if (up < down)
							{
								swap(sortArray, up, down);
							}
					}
				while (up < down);
				swap(sortArray, first, down);
				return down;
			}
                public static void swap(int[] sortArray, int a, int b)
                    {
                        int temp = sortArray[a];
                        sortArray[a] = sortArray[b];
                        sortArray[b] = temp;
                    }

		public static void main(String[] args)
			{
				for (int counter = 1; counter < 11; counter ++)
					{
						int[] sortArray = new int[20000*counter];
                        int[] bubbleArray = new int[20000*counter];
                        int[] selectionArray = new int[20000*counter];
                        int[] heapArray = new int[20000*counter];
                        int[] quickArray = new int[20000*counter];
						for (int i = 0; i < 20000*counter; i++)
							{
								sortArray[i] = (int)(Math.random()*20000);
                                bubbleArray[i] = sortArray[i];
                                selectionArray[i] = sortArray[i];
                                heapArray[i] = sortArray[i];
                                quickArray[i] = sortArray[i];
							}


						long startTime = System.currentTimeMillis();
						Arrays.sort(sortArray);
						long stopTime = System.currentTimeMillis();
						System.out.println("N= " + 20000*counter + " The built in sort took " + (double)(stopTime-startTime) + " milliseconds.");

                                                startTime = System.currentTimeMillis();
                                                quickSort(quickArray);
                                                stopTime = System.currentTimeMillis();
                                                System.out.println("N= " + 20000*counter + " The Quick sort took " + (double)(stopTime-startTime)+ " milliseconds.");

                                                startTime = System.currentTimeMillis();
                                                heapSort(heapArray);
                                                stopTime = System.currentTimeMillis();
                                                System.out.println("N= " + 20000*counter + " The Heap sort took " + (double)(stopTime-startTime)+ " milliseconds.");

                                                startTime = System.currentTimeMillis();
						selectionSort(selectionArray);
						stopTime = System.currentTimeMillis();
						System.out.println("N= " + 20000*counter + " The selection sort took " + (double)(stopTime-startTime) + " milliseconds.");

                                                startTime = System.currentTimeMillis();
						bubbleSort(bubbleArray);
						stopTime = System.currentTimeMillis();
						System.out.println("N= " + 20000*counter + " The bubble sort took " + (double)(stopTime-startTime) + " milliseconds.");

                                                System.out.println("");
					}
			}
	}