/*
 * Copyright (C) 2000-2007 Wang Pengcheng <wpc0000@gmail.com>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 *
 *Sort.java
 *
 *******************************************************************************
 *This sort object has many sort algorithms,such as insertionsort and so on.
 *Sorts the specified list into ascending order, according to the natural
 * ordering of its elements.All elements in the list must implement the <I>Comparable</I> interface. 
 *Furthermore, all elements in the list must be mutually comparable (that is, e1.compareTo(e2)
 * must not throw a ClassCastException for any elements e1 and e2 in the list).
 *******************************************************************************
 *Remember:all the elements in the list must be sorted by the Comparable interface.
 *So you need to add the Comparable method in the list.
 *@author WPC
 *@version 1.0
 */
package cn.edu.whu.iss.algorithm.unit02;

import java.util.*;
import java.math.*;
import mypackage.tools.print.P;
/**
 * Sort set with many sort methods.
 * And many of them are from Algorithm unit 2.
 * @author wpc
 * @version 1.0.0
 */
public class Sort{
	
	/**
	 *InsertionSort
	 *The time limit of this sort is O(n^2)
	 *<strong>O(n^2)</strong>
	 *@param  element will be sorted
	 */
	public static <Type extends Comparable> void insertionSort(Type element[]){
		for(int j=1;j<element.length;j++){
			Type	key	=	element[j];
			int i	=	j-1;
			
			while( (i>=0)&&(element[i].compareTo(key)>0)){
				element[i+1]	=	element[i];
				i--;
			}
			element[i+1]	=	key;
		}
	}
	
	/**
	 *SelectionSort
	 *The time limit of this sort is o(n^2)
	 *<strong>O(n^2)</strong>
	 *@param  element will be sorted
	 */
	public static <Type extends Comparable> void selectionSort(Type element[]){
		for(int j=0;j<element.length-1;j++){
			int index	=	j;
			for(int i=j+1;i<element.length;i++){
				if(element[i].compareTo(element[index])<0){
					index	=	i;
				}
			}
			Type temp		=	element[j];
			element[j]		=	element[index];
			element[index]	=	temp;
		}
	}
	
	/**
	 *Merge used in the mergeSort
	 *<strong>O(n)</strong>
	 *@param element Type[] the elements to be merged
	 *@param p int the begin of the  first elements
	 *@param q int the end of the first elements
	 *@param r int the end of the second elements
	 */
	private static <Type extends Comparable> void merge(Type element[],int p,int q,int r){
		int nl	=	q-p+1;
		int nr	=	r-q;
		
		Type[] lElement,rElement;
		lElement	=	(Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nl);
		rElement	=	(Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nr);
				
		for(int i=0;i<nl;i++){
			lElement[i]	=	element[p+i];
		}
		for(int i=0;i<nr;i++){
			rElement[i]	=	element[q+i+1];
		}
		
		int i=0,j=0;
		int k	=	p;
		while((i<nl)&&(j<nr)){
			if(lElement[i].compareTo(rElement[j])<=0){
				element[k]	=	lElement[i];
				i++;
			}else{
				element[k]	=	rElement[j];
				j++;
			}
			k++;
		}
		
		while(i<nl){
			element[k]	=	lElement[i];
			i++;
			k++;
		}
		while(j<nr){
			element[k]	=	rElement[j];
			j++;
			k++;
		}
	}
	
	/**
	 *mergeSort
	 *Sort the elements by the compareTo method
	 *<strong>O(nlgn)</strong>
	 *@param  element Type[] that will be sorted
	 *@param p the begin of the list will be sorted
	 *@param r the end of the list will be sorted
	 */
	public static <Type extends Comparable> void mergeSort(Type element[],int p,int r){
		if(p<r){
			int q	=	(p+r)/2;
			mergeSort(element,p,q);
			mergeSort(element,q+1,r);
			merge(element,p,q,r);
		}
	}
	public static <Type extends Comparable> void mergeSort(Type element[]){
		mergeSort(element,0,element.length-1);
	}
	
	/**
	 *binaryInsertSort
	 *Sort the elements by the compareTo method
	 *<strong>O(n^2)</strong>
	 *@param  element Type[] that will be sorted
	 */
	public static <Type extends Comparable> void binaryInsertSort(Type element[]){
		for(int j=1;j<element.length;j++){
			Type key	=	element[j];
			int l	=	0,r	=	j-1;
			while(l<=r){
				int mid	=	(l+r)>>1;
				if(key.compareTo(element[mid])<0){
					r	=	mid-1;
				}else{
					l	=	mid+1;
				}
			}
			for(int i=j-1;i>=l;i--){
				element[i+1]	=	element[i];
			}
			element[l]	=	key;
		}
	}
	
	/**
	 *bubbleSort
	 *Sort the elements by the compareTo method
	 *<strong>O(n^2)</strong>
	 *@param element Type[] that will be sorted
	 */
	public static <Type extends Comparable> void bubbleSort(Type element[]){
		for(int i=0;i<element.length;i++){
			for(int j=element.length-1;j>=i+1;j--){
				if(element[j].compareTo(element[j-1])<0){
					Type temp		=	element[j];
					element[j]		=	element[j-1];
					element[j-1]	=	temp;
				}
			}
		}
	}

	/***************************************************************************
	 *Check method
	 **************************************************************************/
	public static void main(String[] args){
		final int MAX	=	15;
		Integer[] a	=	new Integer[MAX];
		Integer[] b	=	new Integer[MAX];
		Integer[] c	=	new Integer[MAX];
		Integer[] d	=	new	Integer[MAX];
		Integer[] f	=	new	Integer[MAX];

		for(int i=0;i<MAX;i++){
			a[i]=MAX-i;
			b[i]=MAX-i;
			c[i]=MAX-i;
			d[i]=MAX-i;
			f[i]=MAX-i;
		}
		for(int i=0;i<MAX;i++){
			P.rint(a[i]+",");
		}
		P.rintln();
		
		Sort.insertionSort(a);
		for(int i=0;i<MAX;i++){
			P.rint(a[i]+",");
		}
		P.rintln();
		
		Sort.selectionSort(b);
		for(int i=0;i<MAX;i++){
			P.rint(b[i]+",");
		}
		P.rintln();
		
		Sort.mergeSort(c);
		for(int i=0;i<MAX;i++){
			P.rint(c[i]+",");
		}
		P.rintln();
		
		Sort.binaryInsertSort(d);
		for(int i=0;i<MAX;i++){
			P.rint(d[i]+",");
		}
		P.rintln();
		
		Sort.bubbleSort(f);
		for(int i=0;i<MAX;i++){
			P.rint(f[i]+",");
		}
		P.rintln();
	}
}