Algoritmo Shell Short

El ordenamiento Shell Short fue publicado en la revista Communications of the ACM en el año 1959, y se llamo así por el Ingeniero matemático Donald Shell.

¿Como se define el algoritmo?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.

- ž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)

-l al-El algoritmo QuickSort (desarrollado por Hoare en 1962) puede dar mejores resultados pero puede “perjudicar” un poco en la programación básica. 

ž- ž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.

-žEl algoritmo de la burbuja, el de selección directa, el de inserción directa y el de Shell son todos in-situ.

-ž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.

  

Características:  

ž-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.


Video del algoritmo shell short: 

Programa en C++: 

include <iostream.h>

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 " <<i<<" : ";

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 <<endl;

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

cout << a[i] <<endl;

} // fin de shell sort //

Grafos

Concepto de grafo: Es un conjunto de puntos llamados vértices, en el espacio que están concectados por un conjunto de lineas  llamándolas aristas. Otro tipo de diferenciar a los grafos es  por ejemplo cuando tenemos dos vértices adyacentes que comparten la misma arista, que los extremos de una arista son los vértices que comparten dicha arista.








Tipos de grafos: 
Grafo dirigido: Es cuando tenemos flechas que indican la unión de un nodo. 
                                                           
Grafo no dirigido: Es aquel que no tiene marcado con flechas el camino de un nodo a otro. 
                                       
Aplicaciones de grafos: 
Para orientar los viajes  de una aerolínea.
                                   
Caminos:  Un camino en un grafo es una sucesion finita en la que aparecen alternadamente vertices y aristas de dicho grafo. 


                            
Tipos de caminos: 
Camino eureliano:  Es el camino que tiene todas las aristas mencionadas en el camino, tiene grado 2.
Camino Hamiltoniano: Aqui tambien aparecen todos las aristas mencionadas.

Programa de Arboles en java

package estructura;
/**
 *
 * @author alumno
 */
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;
import java.util.*;
public class ejemplo { 
    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
   }
}

•Preorden:  Ale, mama, Abuela Esther, Bisabuela Amelia, Tatarabuela Amelia, Tatarabuelo Ernesto, Bisabuelo Gerónimo, Tatarabuela María,  Tatarabuelo José, Abuelo Vicente, Bisabuela Cruz, Tatarabuela Lupita, Tatarabuela Fernanda, Bisabuelo Carmelo, Tatarabuela Carmela, Tatarabuelo René,  Papa Benito , Abuela María Eugenia,  Bisabuela Sofía, Tatarabuela Rocio, Tatarabuelo Felipe, Bisabuelo Jose, Tatarabuela Margarita, Tatarabuelo Meny, Abuelo José, Bisabuela María Eugenia, Tatarabuela Cintia,  Tatarabuelo Juan, Bisabuelo Benito, Tatarabuela Ale, Tatarabuelo José.

•Inorden: Tatarabuela Amelia, Bisabuela Amelia, Tatarabuelo Ernesto, Abuela Esther, Bisabuelo Geromino, Tatarabuela Maria, Tatarabuelo Jose, Mama, Tatarabuela Lupita, Bisabuela Cruz, Tatarabuela Fernanda, Abuelo Vicente, Tatarabuela Carmela, Bisabuelo Carmelo, Tatarabuelo Rene, Ale, Tatarabuela Rocio, Bisabuela Sofia, Tatarabuelo Felipe, Abuela Maria Eugenia, Tatarabuela Margarita, Bisabuelo Jose, Tatarabuelo Meny, Papa, Tatarabuela Cintia, Bisabuela Eugenia, Tatarabuelo Juan , Abuelo Jose, Tatarabuela  Ale, Bisabuelo Benito, Tatarabuelo Jose.

•Postorden:

•Nivel:  6

•Altura: 6

•Grado del árbol: todos son grado 2.

•Raiz:  Yo (Ale).

•Hijos: mama es hijo de yo, papa es hijo de yo, abuela Esther es hija de mama, abuelo vicente es hijo de mama, Bisabuela es hija de Abuela Esther, Bisabuelo Gerónimo es hijo de Abuela Esther, tatarabuela Amelia es hija de Bisabuela Amelia, Tatarabuelo Ernesto es hijo de Abuela Amelia, Bisabuelo Gerónimo es hijo de Abuela Esther.

•Padres:  Yo es padre de mama y papa.

              mama es padre de abuela Esther y Abuelo Vicente.

              Bisabuela Amelia es Padre de Tatarabuela Amelia y Tatarabuelo Ernesto.

              Abuelo Vicente es padre de Bisabuela Cruz y Bisabuelo Jose  Carmelo.

              Bisabuelo Gerónimo es padre de tatarabuela María y tatarabuelo José.

•Hermanos:  Papa y Mama son hermanos.

                                Abuela Esther y Abuelo Vicente son  hermanos.

                               Bisabuela Amelia y Bisabuelo Gerónimo son hermanos.

•Hojas: Tatarabuela Amelia, Tatarabuelo Ernesto, puros tatarabuelos.

•Longitud de camino interno.

•LCI= (1)(1)+(2)(2)+(3)(4)+(4)(8)+(5)(16)=129