Ordenamiento Shell sort

•Es un algoritmo de ordenación interna sencillo pero ingenioso, basado en comparaciones e intercambios.

 

•Sus resultados son radicalmente mejores que los que se pueden obtener con el método (la burbuja, selección directa  o inserción directa).

•Es un algoritmo que casi no se usa por las siguientes causas:

 

•Para su comprensión requiere un cierto esfuerzo y algo de tiempo, y se suele centrar la atención en los tres algoritmos más básicos (burbuja, selección e inserción).

•ShellSort, es el mejor algoritmo de ordenación, en los que la cantidad de memoria adicional que necesita (aparte de los propios datos a ordenar) es constante, sea cual sea la cantidad de datos a ordenar.

   

•Otros métodos de ordenación, como QuickSort, BinSort, HeapSort o RadixSort pueden pueden superar a ShellSort en cuanto al tiempo de ejecución, pero ninguno es algoritmo in-situ.

•

•Es necesario gestionar una cantidad adicional de memoria proporcional al tamaño de los datos a ordenar.

Caracteristicas 

• •Se trata de un algoritmo de ordenación interna. Al igual que cualquier otro de ordenación interna (los datos están en memoria principal)

• •Se basa en comparaciones e intercambios.

• •Necesita que el tiempo de acceso a cualquier dato sea constante,         Aplicado a otras estructuras, como listas enlazadas , etc. , el tiempo de acceso a un elemento no es constante, depende de la posición del elemento.

•

  Programa basado en C++

# include

void main (void)

{

int a[15];

int n, inc, i, j, tmp;

cout <<"De cuantos elementos es el arreglo? ";

cin >> n;

for (i=1; i<=n; i++)

{

cout <<"Introduce el elemento " <

cin >> a[i];

}

 

nc = n/2;

while (inc > 0)

{

for (i = inc +1; i<=n; i++)

{

tmp = a[i];

j=i;

while ( (j-inc) > 0 )

{

if (tmp < a[j-inc])

{

a[j]=a[j-inc];

j=j-inc;

} 

else

break;

} // fin del while //

a[j]=tmp;

} // fin del for //

inc = inc/2;

} // fin del while //

cout <

for (i=1; i<=n; i++)

cout << a[i] <

} // fin de shell sort //

 Video

•

 

•

Grafos

Un grafo es el principal objeto de estudio de la teoría de grafos. 

Es representado gráficamente como un conjunto de puntos (llamados vértices o nodos), unidos por líneas (llamadas aristas), los grafos permiten estudiar las interrelaciones entre unidades que se encuentran en interacción.

Grafo . Un grafo G consta de un conjunto de vértices o nodos V y un conjunto de arcos A, cada uno de los cuales une un vértice con otro.           

Arcos . También se llaman aristas del grafo y se representan por medio de un par de elementos , donde los elementos son los nodos que une el arco.

 Grafo Dirigido à Si los arcos tienen una dirección, se le llama grafo dirigido u orientado. En un grafo orientado cada arco se representado por un par ordenado (vi,vj)   donde el primer elemento es el nodo origen o fuente y el segundo es el nodo destino de ese arco, por lo tanto se puede decir que el arco va desde vi,  hasta vj y que vj es adyacente a vi.

 

Programa de Arbol en Java

package javaapplication3;












import java.awt.*;


import java.awt.event.*;


import javax.swing.*;


import javax.swing.tree.*;


import java.util.*;


public class SimpleTree


{ public static void main(String[] args)


{ JFrame frame = new SimpleTreeFrame();


frame.show();


}


}


class SimpleTreeFrame extends JFrame


{


DefaultMutableTreeNode root = new DefaultMutableTreeNode("Mundo");


DefaultMutableTreeNode arge = new DefaultMutableTreeNode("Argentina");


DefaultMutableTreeNode sant = new DefaultMutableTreeNode("Santa Fe");


DefaultMutableTreeNode rafa = new DefaultMutableTreeNode("Rafaela");


DefaultMutableTreeNode rosa = new DefaultMutableTreeNode("Rosario");


DefaultMutableTreeNode safe = new DefaultMutableTreeNode("Santa Fe");


DefaultMutableTreeNode vena = new DefaultMutableTreeNode("Venado Tuerto");


DefaultMutableTreeNode vill = new DefaultMutableTreeNode("Villa Constitucion");


DefaultMutableTreeNode cord = new DefaultMutableTreeNode("Cordoba");


DefaultMutableTreeNode codo = new DefaultMutableTreeNode("Cordoba");


DefaultMutableTreeNode cbro = new DefaultMutableTreeNode("Cura Brochero");


DefaultMutableTreeNode rcua = new DefaultMutableTreeNode("Rio Cuarto");


DefaultMutableTreeNode chac = new DefaultMutableTreeNode("Chaco");


DefaultMutableTreeNode resi = new DefaultMutableTreeNode("Resistencia");


DefaultMutableTreeNode vang = new DefaultMutableTreeNode("Villa Angela");


DefaultMutableTreeNode chil = new DefaultMutableTreeNode("Chile");


DefaultMutableTreeNode regi = new DefaultMutableTreeNode("Region Metropolitana");


DefaultMutableTreeNode schi = new DefaultMutableTreeNode("Santiago de Chile");


public SimpleTreeFrame()


{ setTitle("SimpleTree");


setSize(300, 200);


addWindowListener(new WindowAdapter()


{ public void windowClosing(WindowEvent e)


{ System.exit(0);


}


} );


root.add(arge); // Enlazado de nodos


arge.add(sant); // Enlazado de nodos


sant.add(rafa); // Enlazado de nodos


sant.add(rosa); // Enlazado de nodos


sant.add(safe); // Enlazado de nodos


sant.add(vena); // Enlazado de nodos


sant.add(vill); // Enlazado de nodos


arge.add(cord); // Enlazado de nodos


cord.add(codo); // Enlazado de nodos


cord.add(cbro); // Enlazado de nodos


cord.add(rcua); // Enlazado de nodos


arge.add(chac); // Enlazado de nodos


chac.add(resi); // Enlazado de nodos


chac.add(vang); // Enlazado de nodos


root.add(chil); // Enlazado de nodos


chil.add(regi); // Enlazado de nodos


regi.add(schi); // Enlazado de nodos


JTree tree = new JTree(root);


Container contentPane = getContentPane();


contentPane.add(new JScrollPane(tree));


Enumeration hijos = sant.children(); // Enumeracion de hijos


while ( hijos.hasMoreElements() ) // Enumeracion de hijos


{ // Enumeracion de hijos


System.err.println("Hijos de Santa Fe : "+hijos.nextElement()); // Enumeracion de hijos


} // Enumeracion de hijos


boolean hoja = vena.isLeaf(); // Consulta Hoja


System.err.println("Es Venado Tuerto hoja : "+hoja); // Consulta Hoja


Enumeration breadth = root.breadthFirstEnumeration(); // Enumeracion Nodos


while ( breadth.hasMoreElements() ) // Enumeracion Nodos


{ // Enumeracion Nodos


System.err.println("Breadth First : "+breadth.nextElement()); // Enumeracion Nodos


} // Enumeracion Nodos


Enumeration depth = root.depthFirstEnumeration(); // Enumeracion Nodos


while ( depth.hasMoreElements() ) // Enumeracion Nodos


{ // Enumeracion Nodos


System.err.println("Depth First : "+depth.nextElement()); // Enumeracion Nodos


} // Enumeracion Nodos


Enumeration preorder = root.preorderEnumeration(); // Enumeracion Nodos


while ( preorder.hasMoreElements() ) // Enumeracion Nodos


{ // Enumeracion Nodos


System.err.println("Pre Order : "+preorder.nextElement()); // Enumeracion Nodos


} // Enumeracion Nodos


Enumeration postorder = root.postorderEnumeration(); // Enumeracion Nodos

while ( postorder.hasMoreElements() ) // Enumeracion Nodos

{ // Enumeracion Nodos

System.err.println("Post Order : "+postorder.nextElement()); // Enumeracion Nodos


} // Enumeracion Nodos

}
}

 

 
 

 

Fuente: http://fideblog.blogspot.com/