//ORDENACIONES

import java.io.*;

public class Ordenaciones
{
//I N S E R C I O N
public static void Insercion(int[] arreglo)
{
int x,j;
for(int i=1; i<=arreglo.length-1; i++)
{
x=arreglo[i];
j=i-1;
while(j>=0 && x<arreglo[j])
{
arreglo[j+1]=arreglo[j];
j--;
}
arreglo[j+1]=x;
}
}

//S E L E C C I O N
public static void Seleccion(int[] arreglo)
{
int minj,minx;
for(int i=0;i<=arreglo.length-2;i++)
{
minj=i;
minx=arreglo[i];
for(int j=i+1; j<=arreglo.length-1;j++)
{

if(arreglo[j]<minx)
{
minj=j;
minx=arreglo[j];
}
}
arreglo[minj]=arreglo[i];
arreglo[i]=minx;
}
}

//M E R G E S O R T O F U S I O N
public static void mergeSort(int[] a, int[] temp, int izq, int der)
{
if(izq<der)
{
int centro=(izq+der)/2;
//System.out.println("izq= "+izq+"centro= "+centro+"der= "+der);
mergeSort(a,temp,izq,centro);
mergeSort(a,temp,centro+1,der);
mezclar(a,temp,izq,centro+1,der);
}
}

public static void mergeSort(int[] a)
{
int[] temp= new int[a.length];
mergeSort(a,temp,0,a.length-1);
}

private static void mezclar(int[] a, int[] aux, int posizq, int posder, int posfin)
{
int finizq=posder-1;
int posaux=posizq;
int numelementos=posfin-posizq+1;
while(posizq<=finizq&&posder<=posfin)
{
if(a[posizq]<a[posder++])
aux[posaux++]=a[posizq++];
else
aux[posaux++]=a[posder++];
}
while(posizq<=finizq)
aux[posaux++]=a[posizq++];
while(posder<=posfin)
aux[posaux++]=a[posder++];
for(int i=0; i<numelementos;i++,posfin--)
a[posfin]=aux[posfin];
}

//B U R B U J A O B U B L E S O R T
public static void burbuja(int [] arreglo)
{
int i, j;
int temp;
boolean sorted=false;
for(i=0; i<arreglo.length-1 && !sorted; i++)
{
sorted=true;
for(j=arreglo.length-1; j>i; j--)
{
if(arreglo[j]<arreglo[j-1]);
{
temp=arreglo[j];
arreglo[j]=arreglo[j-1];
arreglo[j-1]=temp;
sorted=false;
}
}
}
}

//Q U I T S O R T
public static void Sort(int[] a)
{
Sort(a,0,a.length-1);
}

public static void Sort(int [] a, int inicio, int fin)
{
int pivote;

int nuevo_inicio,aux;
if (inicio<fin)
{

pivote=a[inicio];
nuevo_inicio=inicio;
for (int i=(inicio+1);i<=fin; i++)
{
if (a[i]<=pivote)
{
nuevo_inicio=nuevo_inicio+1;
aux=a[i];
a[i]=a[nuevo_inicio];
a [nuevo_inicio]=aux;
}
}
aux=a[inicio];
a[inicio]=a[nuevo_inicio];
a[nuevo_inicio]=aux;
Sort(a,inicio,nuevo_inicio);
Sort(a,nuevo_inicio+1,fin);
}
}

//METODO AUXILIAR PARA IMPRIMIR EN PANTALLA
public static void muestra(int[] arreglo,String cad)
{
System.out.print(cad);
for (int i=0; i<arreglo.length; i++)
System.out.print(arreglo[i]+" ");
System.out.print("\n\n");
}

//METODO PRINCIPAL MAIN
public static void main(String []args)
{
int[] nums={5,6,1,9,0,3,7,20,-1,2};
int[] num2={8,3,6,15,1,9};
int[] num3={24,13,26,1,2,27,38,15};
int[] num4={3,1,4,1,5,9,2,6,5,4};
int[] num5={24,13,26,1,2,227,38,15};
Ordenaciones.muestra(nums,"datos en desorden: ");
Ordenaciones.Insercion(nums);
Ordenaciones .muestra (nums, "Datos en orden \n (metodo de insercion):");
System.out.println(" ");
Ordenaciones.muestra(num2,"datos en desorden: ");
Ordenaciones.Seleccion(num2);
Ordenaciones .muestra (num2, "Datos en orden \n (metodo de seleccion):");
System.out.println(" ");
Ordenaciones .muestra (num3, "datos en desorden: ");
Ordenaciones.mergeSort(num3);
Ordenaciones.muestra(num3,"Datos en orden \n (metodo de merge sort) :");
System. out .println (" ") ;
Ordenaciones .muestra (num4, "datos en desorden: ");
Ordenaciones.burbuja(num4);
Ordenaciones.muestra(num4,"Datos en orden \n (metodo de la burbuja) :");
System.out.println(" ");
Ordenaciones.muestra(num5,"datos en desorden: ");
Ordenaciones.Sort(num5);
Ordenaciones.muestra(num5, "Datos en orden \n (metodo de Quick Sort)");
System.out.println(" ");
}

}