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]);
}
}
}

LISTAS ENLAZADAS

Lista doblemente enlazada.

Una lista doblemente enlazada es una lista enlazada de nodos, donde cada nodo tiene un par de campos de enlace. Un campo de enlace permite atravesar la lista hacia adelante, mientras que el otro permite atravesar la lista haca atrás. Para la dirección hacia adelante, una variable de referencia contiene una referencia al primer nodo. Cada nodo se enlaza con el siguiente mediante el campo de enlace next, excepto el último nodo, cuyo campo de enlace next contiene null para indicar el final de la lista (en direccion hacia adelante). De forma similar, para la dirección contraria, una variable de referencia contiene una referencia al último nodo de la dirección normal (hacia adelante), lo que se interpreta como el primer nodo. Cada nodo se enlaza con el anterior mediante el campo de enlace previous, y el primer nodo de la direccion hacia adelante, contiene null en su campo previous para indicar el fin de la lista. La siguiente figura representa una lista doblemente enlazada de tres nodos, donde topForward referencia el primer nodo en la direccion hacia adelante, y topBackward referencia el primero nodo la dirección inversa.

LISTASSIMPLES

LISTAS ENLAZADAS SIMPLES
Una lista de enlace simple es una lista enlazada de nodos, donde cada nodo tiene un único campo de enlace. Una variable de referencia contiene una referencia al primer nodo, cada nodo (excepto el último) enlaza con el nodo siguiente, y el enlace del último nodo contiene null para indicar el final de la lista. Aunque normalmente a la variable de referencia se la suele llamar top, usted puede elegir el nombre que quiera. La siguiente figura presenta una lista de enlace simple de tres nodos, donde top referencia al nodo A, A conecta con B y B conecta con C y C es el nodo final:



Un algoritmo común de las listas de enlace simple es la inserción de nodos. Este algoritmo está implicado de alguna forma porue tiene mucho que ver con cuatro casos: cuando el nodo se debe insertar antes del primer nodo; cuando el nodo se debe insertar después del último nodo; cuando el nodo se debe insertar entre dos nodos; y cuando la lista de enlace simple no existe. Antes de estudiar cada caso consideremos el siguiente pseudocódigo:

DECLARE CLASS Node
DECLARE STRING name
DECLARE Node next
END DECLARE

DECLARE Node top = NULL

Este pseudocódigo declara una clase auto-referenciada llamada Node con un campo no de enlace llamado name y un campo de enlace llamado next. También declara una variable de referencia top (del tipo Node) que contiene una referencia al primer Node de una lista de enlace simple. Como la lista todavía no existe, el valor inicial de top es NULL. Cada uno de los siguientes cuatro casos asume las declaraciones de Node y top:

La lista de enlace simple no existe:: Este es el caso más simple. Se crea un Node, se asigna su referencia a top, se inicializa su campo no de enlace, y se asigna NULL a su campo de enlace. El siguiente pseudocódigo realiza estas tareas:
top = NEW Node

top.name = "A"
top.next = NULL
En la siguiente imagen se puede ver la lista de enlace simple que emerge del pseudocódigo anterior:




El nodo debe insertarse antes del primer nodo:.
Se crea un Node, se inicialia su campo no de enlace, se asigna la referencia de top al campo de enlace next, y se asigna la referencia del Node recien creado a top. El siguiente pseudocódigo (que asume que se ha ejecutado el pseudocódigo anterior) realiza estas tareas:
DECLARE Node temp

temp = NEW Node
temp.name = "B"
temp.next = top
top = temp
El resultado del listado anterior aparece en la siguiente imagen:



El nodo debe insertarse detrás del último nodo:
Se crea un Node, se inicializa su campo no de enlace, se asigna NULL al campo de enlace, se atraviesa la lista de enlace simple hasta el último Node, y se asigna la referencia del Node recien creado al campo next del último nodo. El siguiente pseudocódigo realiza estas tareas:
temp = NEW Node
temp.name = "C"
temp.next = NULL

DECLARE Node temp2

temp2 = top

¿Que es java?

Java es un lenguaje de programación con el que podemos realizar cualquier tipo de programa. En la actualidad es un lenguaje muy extendido y cada vez cobra más importancia tanto en el ámbito de Internet como en la informática en general. Está desarrollado por la compañía Sun Microsystems con gran dedicación y siempre enfocado a cubrir las necesidades tecnológicas más punteras. Una de las principales características por las que Java se ha hecho muy famoso es que es un lenguaje independiente de la plataforma. Eso quiere decir que si hacemos un programa en Java podrá funcionar en cualquier ordenador del mercado. Es una ventaja significativa para los desarrolladores de software, pues antes tenían que hacer un programa para cada sistema operativo, por ejemplo Windows, Linux, Apple, etc. Esto lo consigue porque se ha creado una Máquina de Java para cada sistema que hace de puente entre el sistema operativo y el programa de Java y posibilita que este último se entienda perfectamente. La independencia de plataforma es una de las razones por las que Java es interesante para Internet, ya que muchas personas deben tener acceso con ordenadores distintos. Pero no se queda ahí, Java está desarrollándose incluso para distintos tipos de dispositivos además del ordenador como móviles, agendas y en general para cualquier cosa que se le ocurra a la industria.

programas de Colas

import java.io.*;
public class Colas {
public static class ClaseColas { // Declaracion de la clase de Colas
static int max=10; // Tamano maximo de la Cola
static int cola[]= new int[max]; // Declaracion del arreglo
static int frente, fin; // Indicadores de inicio y fin de la Cola

ClaseColas() { // Constructor que inicializa el frente y el final de la Cola
frente=0; fin=0;
System.out.println("Cola inicializada !!!");
}
public static void Insertar(int dato) {
if(fin==max) { // Esta llena la Cola?
System.out.println("\nCola llena !!!");
return;
}
cola[fin++]=dato;
System.out.println("Dato insertado !!!");
}
public static void Eliminar() {
System.out.println("\n\n<<<>>>");
if(frente==fin) { // Esta vacia la Cola?
System.out.println("\nCola vacia !!!");
return;
}
System.out.println("Elemento eliminado: "+cola[frente++]); //elimina el primer elemento insertado en la cola
}
public static void Mostrar() {
int i=0;
System.out.println("\n\n<<<>>>");
if(frente==fin)
System.out.println("\nCola vacia !!!"); //declara que la cola esta vacia
for(i=frente; i System.out.println("cola["+i+"]="+" "+cola[i]);
}
System.out.println("\nFrente= "+frente);
System.out.println("Final = "+fin);
System.out.println("Max = "+max);
}
}
}

¿Que es estructura de datos?

Las estrucutras de datos varian en como permiten el acceso del grupo algunas permiten tanto accesos como operaciones de borrado arbitrarios. Otras imponen restricciones, tales como permitir el acceso solo al elemento mas recientemente insertado o al menos resientemente insertado del grupo.

Se discute 7 de las mas comunes estructuras de datos: pilas, colas, listas enlazadas, arboles, arboles binarios de busqueda, tablas hash y colas de prioridad. El objetivo es definir cada estructura de datos asi como dar una idea intuitiva de la complejidad en tiempo de las operaciones de insercion, borrado y acceso.

Las estrucutras de datos nos permiten lograr un importante objetivo de la programacion orientada a objetos: reutilizacion de componentes. Una vez que la estructura de datos a sido implementada, puede ser utilizada una y otra vez en diversas aplicaciones.