Metodo de Shell-Sort

Metodo de Shell-Sort

Es una version mejorda del metodo de insercion directa.
En el metodo de ordenaion por insercion directa cada elemento s compara para su ubicacion correcta en el arreglo con los elementos que se encuentra en la parte izquierda del mismo. Si el elemento a insertar es mas pequeño que el grupo de elementos que se encuentra a su izquierda, es necesario efectuar entonces varias comparaciones antes de su ubicacion.

CODIGO:

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

public class shell extends JFrame{
int a[]=new int[10];
int i, n, j;
int max, mayor;
String salida1="", salida2="";
JTextArea areaSalida=new JTextArea(6,6);
JTextArea areaSalida2=new JTextArea(6,6);
JTextField numero=new JTextField(15);

public shell(){
super("Ordenamiento tipo shell");
JLabel etiqueta=new JLabel("Cuantos numeros quieres?");
JLabel etiqueta1=new JLabel("Los numeros son:");

JButton capturar=new JButton("Capturar");
capturar.addActionListener(
new ActionListener(){
public void actionPerformed(ActionEvent evento){
captura();
}
}
);
JButton ordenar=new JButton("Ordenar");
ordenar.addActionListener(
new ActionListener(){
public void actionPerformed(ActionEvent evento){
ordena(a,n);
}
}
);
Container contenedor=getContentPane();
contenedor.setLayout(new FlowLayout());
contenedor.add(etiqueta);
contenedor.add(numero);
contenedor.add(capturar);
contenedor.add(etiqueta1);
contenedor.add(areaSalida);
contenedor.add(ordenar);
contenedor.add(areaSalida2);
setSize(300,300);
setVisible(true);
}

public void captura(){
if (numero.getText().equals("")){
JOptionPane.showMessageDialog(null,"Escriba un nombre");
numero.setText("");
}
else{
a[i]=Integer.parseInt(numero.getText());
salida2+=a[i]+"\n";
i++;
numero.setText("");

if (i==5){
n=i;
JOptionPane.showMessageDialog(null,"Fin de la captura");
}
areaSalida.setText(salida2);
}
}

public void muestra(int nn,int a3[]){
for(int k=0;k salida1+=a3[k]+"\n";
areaSalida2.setText(salida1);
}

public int mayores(int ultimo,int a[]){
max=0;
for(i=0;i if(a[i]>=a[max]){
max=i;
mayor=max;
}
return (mayor);
}

public void ordena(int lista[], int n){
int inter=(n/2),x=0,i=0,j=0,k=0,aux;
while(inter>0){
for(i=inter;i x++;
j=i-inter;
while(j>=0){
k=j+inter;
if(lista[j]<=lista[k]){
j--;
}
else{
aux=lista[j];
lista[j]=lista[k];
lista[k]=aux;
j=j-inter;
}
}
}
inter=inter/2;
}
muestra(n,lista);
}

public static void main(String[] args) {
shell aplicacion5 = new shell();
aplicacion5.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
}

RadixSort

RadixSort
el algoritmo oredena una secuencia de pares, por esjemplo S, aplicandole dos veces un oredenamiento estable por cubetas: primero usando un componente del par como clave del ordenamiento y despues el segundo comportamiento, pero el correcto es el que se oredena se deve oredenar primero con la K y despues con las L el segundo componente al reves.

CODIGO:

import java.lang.*;
import java.io.*;

public class RadixSort{

public static void radixSort(int[] arr){
if(arr.length == 0)
return;
int[][] np = new int[arr.length][2];
int[] q = new int[0x100];
int i,j,k,l,f = 0;
for(k=0;k<4;k++){
for(i=0;i<(np.length-1);i++)
np[i][1] = i+1;
np[i][1] = -1;
for(i=0;i q[i] = -1;
for(f=i=0;i j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
if(q[j] == -1)
l = q[j] = f;
else{
l = q[j];
while(np[l][1] != -1)
l = np[l][1];
np[l][1] = f;
l = np[l][1];
}
f = np[f][1];
np[l][0] = arr[i];
np[l][1] = -1;
}
for(l=q[i=j=0];i<0x100;i++)
for(l=q[i];l!=-1;l=np[l][1])
arr[j++] = np[l][0];
}
}

public static void main(String[] args){
int i;
int[] arr = { 1212, 117, 839, 1382, 741, 1357, 1293, 899, 1202, 1227, 982, 1153,
15, 831 ,1202, 287, 417, 329, 674, 1375, 142, 1368, 1395, 1317, 810, 471, 288, 117, 1285,........................, 1313, 5};

System.out.print("original: ");
for(i=0;i System.out.print(arr[i] + " ");
}

System.out.print("\nsorted: ");
for(i=0;i System.out.print(arr[i] + " ");
System.out.println("\nDone ;-)");
}
}

ARBOL BINARIO

Metodo De Arbol binario

es aquel en el cual las ramas de los nodos del arbol estan ordenadas. Los arboles ordenados de grado 2 son de especial interes puesto que representa una dxe las estructiras de datos mas importantes en computacion.
Un arbol binario cada nodo puede tener como maximo dos subarboles y siempre es necesario distinguir entre el subarbol izquierdo y el subarbol derecho.
se define un arbol binario tipo T como una estructura homogenea que es la concatenacion de un elemento de tipo T, llamada raiz, con dos arboles binarios dijuntos, llamados subarbol izquierdo y subarbol derecho de la raiz.

CODIGO:
class NodoArbol{
NodoArbol li,ld;
int dato;

public NodoArbol(int d){
dato=d;
li=ld=null;
}

public synchronized void insertar(int d){

if(d if(li==null){
li=new NodoArbol(d);
}
else{
li.insertar(d);
}
}

if(d>dato){
if(ld==null){
ld=new NodoArbol(d);
}
else{
ld.insertar(d);
}
}

}//fin insertar

public int retornadato(){
return(dato);
}//end retornadato

}

public class Arbol {

private NodoArbol raiz;

public Arbol() {
raiz=null;
}
public NodoArbol retornaraiz(){
return(raiz);
}


public synchronized void insertarNodo(int d){
if(raiz==null){
raiz=new NodoArbol(d);
//primero=raiz;
}
else{
raiz.insertar(d);
}
}//fin insertarNodo

public synchronized String preorden(){
String pre=ayudantepreorden(raiz);
return(pre);
}

private String ayudantepreorden(NodoArbol nodo){
String cadena=new String();
if(nodo!=null){
//return;

//System.out.print(nodo.dato+" ");
cadena=cadena+String.valueOf(nodo.dato+" ");
cadena=cadena+ayudantepreorden(nodo.li);
cadena=cadena+ayudantepreorden(nodo.ld);
}
else{
cadena="";
}
return(cadena);
}

public synchronized String inorden(){
String inor=ayudanteinorden(raiz);
return(inor);
}

private String ayudanteinorden(NodoArbol nodo){
String cadena=new String();
if(nodo!=null){
// return;

cadena=cadena+ayudanteinorden(nodo.li);
cadena=cadena+nodo.dato+" ";
cadena=cadena+ayudanteinorden(nodo.ld);
}
else{cadena="";}
return(cadena);
}

public synchronized String posorden(){
String pos=ayudanteposorden(raiz);
return(pos);
}

private String ayudanteposorden(NodoArbol nodo){
String cadena=new String();
if(nodo!=null){



cadena=cadena+ayudanteposorden(nodo.li);
cadena=cadena+ayudanteposorden(nodo.ld);
cadena=cadena+nodo.dato+" ";
}
else{cadena="";}
return(cadena);
}

public synchronized int altura(NodoArbol R){
NodoArbol p=R;
int altizq=p.li==null ? 1:1+altura(p.li);
int altder=p.ld==null ? 1:1+altura(p.ld);
return(Math.max(altizq,altder));
}//end altura

public synchronized int hojas(NodoArbol R){
NodoArbol p=R;
int hojas=0;
if(p.li==null & p.ld==null){
hojas=1;
}
else{
if(p.li!=null){
hojas=hojas+hojas(p.li);
}
if(p.ld!=null){
hojas=hojas+hojas(p.ld);
}
}
return(hojas);
}//end hojas

public synchronized String ancestros(NodoArbol R,int d){
NodoArbol p=R;

String h=new String();

if (p.dato==d){
return(String.valueOf(" --> "+d));
}//end if

if (d>p.dato){
h=h+" --> "+p.dato+ancestros(p.ld,d);
}
else{
h=h+" --> "+p.dato+ancestros(p.li,d);
}
return(h);
}




}

Metodo De Quick-Sort

Metodo De Quick-Sort

Se basa en el paradigma de divide y venceras, pero usa esta tecnica en forma algo contraria por que todo el trabajo duro se hace antes de las llamadas recursivas.
El ordenamiento rapido ordena una secuencia s en subsecuencias, se hace recursion para ordenar cada subsecuencia y a continuacion se combinan las secuencias ordenada sin mediante una simple concatenacion.


CODIGO DE QUICK-SORT (enteros y flotantes)


ENTEROS

public class quicksort {
public static void qsort(Comparable [] c, int inicio, int fin) {

if(fin<=inicio) return;
Comparable comp=c[inicio];
int i=inicio, j=fin+1;
for(;;){
do i++;while(i do j--;while(j>inicio && c[j].compareTo(comp)>0 );
if (j<=i) break;
Comparable tmp=c[i];
c[i]=c[j];
c[j]=tmp;

}
c[inicio]=c[j];
c[j]=comp;
qsort(c, inicio, j-1);
qsort(c, j+1, fin);
}

public static void qsort(Comparable[] c){
qsort(c, 0, c.length-1);
}
public static void main(String[] args){
int i;
Integer[] arr=new Integer [100];
System.out.println("Elementos aleatorios:");
for(i=0; i arr[i]=new Integer((int)(Math.random()*99));
System.out.print(arr[i]+"");
}

quicksort.qsort(arr);
System.out.println("\nelementos ordenados:");
for(i=0; i System.out.print(arr[i]+"");

}
}

metodo de burbuja

Metodo de Burbuja
Es otro algoritmo de metodo ordenacion secuencial que utiliza dos bucles anidados. En estes metodo, se ordena los valores comparando repetivamente los elementos adyasentes de la lista intercambiando su posicion si no se encuentran en orden relativo corecto.
Cada pasada del algorimo de la burbuja hace que se desplace el valor mas grande hasta su posicion final a lo largo de esa pasada, tambien pueden reposicionarse otros elementos.




CODIGO DE BURBUJA (con numeros enteros y flotantes)


class Main {
public static float izquierda,derecha,ultimo; //variables para ordenamiento
public static double arreglo[] = {10.2,23.53,1.8,2.3,3.2,4.5,5.39,6.9,7.9,6.7,8.1,678.3,57.3,4.6,3.56,5.56,3.4,5.67,89.6,67.8,9.6,4.5,7.7,6.89,....................., 4.5,7.7,6.89,8.7};
public static void main(String[] args) {
izquierda = 1;
derecha = arreglo.length;
ultimo = arreglo.length-1;
do{
for(int i=arreglo.length-1;i>0;i--){
//Burbuja hacia la izquierda
//Los valores menores van a la izquierda
if (arreglo[i-1] > arreglo[i]){
double aux = arreglo[i]; // variable auxiliar para poder hacer intercambio de
arreglo[i] = arreglo[i-1]; // posicion
arreglo[i-1] = aux;
ultimo = i;
}
}
izquierda = ultimo+1;
for(int j=1;j if(arreglo[j-1] > arreglo[j]){
double aux = arreglo[j];
arreglo[j] = arreglo[j-1];
arreglo[j-1] = aux;
ultimo = j;
}
}
derecha = ultimo-1;
}while(derecha >= izquierda);
for(int i=0;i System.out.println(arreglo[i]);
}
}
}