import java.util.Scanner;
public class Tarea3 {
	public static void main(String []args){
		int n=0,opcion;
		int a[]= new int[10];int b[]=new int[10];
		Scanner lector = new Scanner(System.in);
		do{
			System.out.println("Vectores 
1.Lectura
2.Listado
3.Bubble sort
4.Insertion sort.
5.Merge sort.
6.Quick sort.7.Seleccion sort.
8.Shell sort.
9.Salir.");
			opcion= lector.nextInt();
			switch(opcion)
			{
			case 1: do{System.out.println("Total de elementos");
						n=lector.nextInt();}while((n>=10)||(n<=0));
						a=lectura(n);
						break;
		    case 2:	listado(a,n);
		    		break;
		    case 3: a=bubblesort(a,n);
		    		break;
		    case 4: a=insertion(a,n);
		    		break;
		    case 5: mergeSort(a,b,0,(n-1));
		    		break;
		    case 6: quickSort(a,0,(n-1));
		    		break;
		    case 7: seleccionDirecta(a);
		    		break;
		    case 8: shellSort(a);
		    		break;
			}
		}while(opcion!=9);
	}
	public static int[] lectura(int x){
		Scanner lector = new Scanner(System.in);int b[]= new int[x];int f;
		for(int i=0;i<x;i++){
			f=i+1;
			System.out.println("Ingresando dato ["+f+"]");
			b[i]= lector.nextInt();
		}
		return (b);
	}
	public static void listado(int[] w,int d)
	{
		System.out.println("El vector es: ");
		for(int x:w){
			System.out.print(x+"	");
		}
		System.out.println();
 
	}
	public static int[] bubblesort(int[]a,int n){
		for(int i=1;i<a.length;i++){
			for(int j=0;j<a.length-i;j++){
				if(a[j]>a[j+1]){
					int aux=a[j];
					a[j]=a[j+1];
					a[j+1]=aux;
				}
			}
		}
		return(a);
	}
	public static int[] insertion(int[]a,int n){
		for(int i=1;i<a.length;i++){
			int aux=a[i];
			int j=i-1;
			while(j>=0&&aux<a[j]){
				a[j+1]=a[j];
				j--;
			}
			a[j+1]=aux;
		}
		return(a);
	}
	public static void mergeSort(int a[],int tmpArray[],int left,int right){
		if(left<right){
			int center=(left+right)/2;
			mergeSort(a,tmpArray,left,right);
			mergeSort(a,tmpArray,center+1,right);
			merge(a,tmpArray,left,center+1,right);
		}
	}
	private static void merge(int a[],int tmpArray[],int leftPos,int rightPos,int rightEnd){
		int leftEnd=rightPos-1;
		int tmpPos=leftPos;
		int numElements=rightEnd-leftPos+1;
		while(leftPos<=leftEnd&&rightPos<=rightEnd){
			if(a[leftPos]<(a[rightPos]))
				tmpArray[tmpPos++]=a[leftPos++];
			else
				tmpArray[tmpPos++]=a[rightPos++];
		}
		while(leftPos<=leftEnd)
			tmpArray[tmpPos++]=a[leftPos++];
		while(rightPos<=leftEnd)
			tmpArray[tmpPos++]=a[rightPos++];
		for(int i=0;i<numElements;i++,rightEnd--)
			a[rightEnd]=tmpArray[rightEnd];
	}
	public static void quickSort(int[]a,int izq,int der){
		int i=izq;
		int j=der;
		int pivote=a[(izq+der)/2];
		do{
			while(a[i]<pivote)i++;
			while(a[j]>pivote)j--;
			if(i<=j){
				int aux=a[i];
				a[i]=a[j];
				a[j]=aux;
				i++;
				j--;
			}
		}while(i<=j);
		if(izq<j)quickSort(a,izq,j);
		if(i<der)quickSort(a,i,der);
	}
	public static void seleccionDirecta(int[]a){
		for(int i=0;i<a.length;i++){
			int menor=a[i];
			int pos=i;
			for(int j=i+1;j<a.length;j++){
				if(a[j]<menor){
					menor=a[j];
					pos=j;
				}
			}
			a[pos]=a[i];
			a[i]=menor;
		}
	}
	public static void shellSort(int a[]){
		for(int gap=a.length/2;gap>0;gap=gap==2?1:(int)(gap/2.2)){
			for(int i=gap;i<a.length;i++){
				int tmp=a[i];
				int j;
				for(j=i;j>=gap&&tmp<a[j-gap];j-=gap){
					a[j]=a[j-gap];
				}
				a[j]=tmp;
			}
		}
	}
}