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

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 //

Mi Arbol Genealogico General

Arbol Genealogico

Arbol en Java

Codigo de un arbol en JAVA




/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
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");
   DefaultMutableTreeNode mexi = new DefaultMutableTreeNode("Juarez ");
   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
  
      mexi.add(schi);
      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
   }
}



Agradecimiento especial a Fidel De la Crup  por su aportacion con este programa

!! Gracias Fidel !! jaja   .-.

Colas (Informatica)

Concepto

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Utilizacion

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.
Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.


Operaciones Básicas

• Crear: se crea la cola vacía.
• Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
• Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
• Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

Codificacion de Colas
Colas en C++

#ifndef COLA
  #define COLA // Define la cola
  template <class T>
  class Cola{
      private:
        struct Nodo{
            T elemento;
            struct Nodo* siguiente;  // coloca el nodo en la segunda posición
        }* primero;
        struct Nodo* ultimo;
        unsigned int elementos;
      public:
        Cola(){
            elementos = 0;
        }
        ~Cola(){
            while (elementos != 0) pop();
        }
        void push(const T& elem){
            Nodo* aux = new Nodo;
            aux->elemento = elem;
            if (elementos == 0) primero = aux;
            else ultimo->siguiente = aux;
            ultimo = aux;
            ++elementos;
        }
        void pop(){
            Nodo* aux = primero;
            primero = primero->siguiente;
            delete aux;
            --elementos;
        }
        T consultar() const{
            return primero->elemento;
        }
        bool vacia() const{
            return elementos == 0;
        }
        unsigned int size() const{
            return elementos;
        }
    };
    #endif

 

 Colas en JAVA

public void inserta(Elemento x) {
        Nodo Nuevo;
        Nuevo = new Nodo(x, null);
        if (NodoCabeza == null) {
            NodoCabeza = Nuevo;
        } else {
            NodoFinal.Siguiente = Nuevo;
        }
        NodoFinal = Nuevo;
    }
 
    public Elemento cabeza() throws IllegalArgumentException {
        if (NodoCabeza == null) {
            throw new IllegalArgumentException();
        } else {
            return NodoCabeza.Info;
        }
    }
 
    public Cola() {
    // Devuelve una Cola vacía
        NodoCabeza = null;
        NodoFinal = null;
    }

Vide de Programa  Colas en C++   (1/2)

 Parte  2

Arbol (informatica)

Arboles Binarios

    El árbol es una estructura de datos fundamental en la informática, muy utilizada en todos sus campos, por que se adapta a la representación natural de informaciones homogéneas organizadas y de una gran comodidad y rapidez de manipulación.

   

    Las estructuras tipo árbol se usan principalmente para representar datos con una relación jerárquica entre sus elementos, como son árboles genealógicos, tablas, etc.

   La definición de un árbol implica una estructura recursiva. Esto es, la definición del árbol se refiere a otros árboles. Un árbol con ningún nodo es un árbol nulo; no tiene raíz.

TERMINOLOGÍA Y REPRESENTACIÓN DE UN ÁRBOL GENERAL
La representación y terminología de los arboles se realiza con las típicas notaciones de las relaciones familiares en los árboles genealógicos: padre, hijo, hermano, ascendente, descendiente, etc. 


RAIZ: Todos loa árboles que no esta vacíos tienen un único nodo raíz. Todos los demás elementos o nodos derivan o descienden de el. El nodo Raíz no tiene Padre es decir no es hijo de ningún elemento


PADRE: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.

HIJO: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.

HERMANO: Dos nodos serán hermanos si son descendientes directos de un mismo nodo.

HOJA. Se le llama hoja o Terminal a aquellos nodos que no tienen ramificaciones (hijos).

NODO. Son los Vértices o elementos del Árbol.

NODO INTERIOR. Es un nodo que no es raíz ni Terminal.

GRADO. Es el número de descendientes directos de un determinado nodo.

GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol.

NIVEL. Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.

ALTURA. Es el máximo número de niveles de todos los nodos del árbol. Equivale al nivel más alto de los nodos más 1.

PESO. Es el número de nodos terminales del árbol

LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.

Operaciones de los Arboles Binarios

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel n + 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden, postorden e inorden:

• El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos en orden previo.
• El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A₁, luego la raíz y luego cada uno de los hijos en orden simétrico.
• El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos en orden posterior y por último la raíz.

Finalmente, puede decirse que esta estructura es una representación del concepto de árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico (ver también teoría de grafos y Glosario en teoría de grafos).


Codigo de Arbol
import java.io.*;

class TreeNode {
     String word;               // Word being stored.
     int count = 1;             // Count of words seen in text.
     TreeNode left;             // Left subtree reference.
     TreeNode right;            // Right subtree reference.

     public TreeNode (String word) {
            this.word = word;
            left = right = null;
     }

     public void insert (String word)  {
            int status = this.word.compareTo (word);

            if (status > 0) {    // word argument precedes current word

                    // If left-most leaf node reached, then insert new node as 
                    // its left-most leaf node. Otherwise, keep searching left.
                    if (left == null)
                            left = new TreeNode (word);
                    else
                            left.insert (word);
            }
            else
                if (status < 0) {    // word argument follows current word     

                    // If right-most leaf node reached, then insert new node as
                    // its right-most leaf node. Otherwise, keep searching right.

                    if (right == null)
                            right = new TreeNode (word);
                    else
                            right.insert (word);
                }
                else
                    this.count++;
     }
}

class WC {
     public static void main (String [] args) throws IOException  {
            int ch;

            TreeNode root = null;

            // Read each character from standard input until a letter
            // is read. This letter indicates the start of a word.

            while ((ch = System.in.read ()) != -1) {
                 // If character is a letter then start of word detected.

                 if (Character.isLetter ((char) ch)) {
                         // Create StringBuffer object to hold word letters.

                         StringBuffer sb = new StringBuffer ();

                        // Place first letter character into StringBuffer object.
                         sb.append ((char) ch);

                         // Place all subsequent letter characters into StringBuffer
                         // object.
                         do {
                                ch = System.in.read ();
                                if(Character.isLetter ((char) ch))
                                        sb.append((char) ch);
                                else
                                        break;
                         }
                         while (true);
                         // Insert word into tree.
                         if (root == null)
                                root = new TreeNode (sb.toString ());
                         else
                                 root.insert (sb.toString ());
                 }
            }
            display (root);
     }

     static void display (TreeNode root) {
            // If either the root node or the current node is null,
            // signifying that a leaf node has been reached, return.
            if (root == null)
                    return;

            // Display all left-most nodes (i.e., nodes whose words
            // precede words in the current node).
            display (root.left);

            // Display current node's word and count.
            System.out.println ("Word = " + root.word + ", Count = " +
                                                    root.count);

            // Display all right-most nodes (i.e., nodes whose words
            // follow words in the current node).
            display (root.right);
     }
}

Sintaxis de un arbol en Java

Pilas

Concepto


 Las pilas son estructuras de datos que tienes dos operaciones básicas:
push (para insertar un elemento) y  pop (para extraer un elemento). Su
característica fundamental es que al extraer se obtiene siempre el último
elemento que acaba de insertarse. Por esta razón también se conocen como
estructuras de datos LIFO (del inglés  Last  In  First  Out).

Aplicaciones

Las pilas se utilizan en muchas  aplicaciones que utilizamos con
frecuencia. Por ejemplo, la gestión de ventanas en Windows (cuando cerramos
una ventana siempre recuperamos la que teníamos detrás). Otro ejemplo es la
evaluación general de cualquier expresión matemática para evitar tener que
calcular el número de variables temporales que hacen falta. Por ejemplo:

                                         3 + 4 * (8 – 2 * 5)


  5                
 -2                           -10            
  8                              8                               - 2    
  4                              4                                 4                             -8  
  3                              3                                 3                               3                   -5

Operaciones básicas de las pilas

Vamos a estudiar las principales operaciones a realizar sobre una pila, insertar y borrar.

Insertar

En primer lugar hay que decir que esta operación es muy comúnmente denominada push.
La inserción en una pila se realiza en su cima, considerando la cima como el último elemento insertado. Esta es una de las particularidades de las pilas, mientras el resto de estructuras de datos lineales se representan gráficamente en horizontal, las pilas se representan verticalmente. Por esta razón es por lo que se habla de cima de la pila y no de cola de la cima. Aunque en el fondo sea lo mismo, el último elemento de la estructura de datos.
Las operaciones a realizar para realizar la inserción en la pila son muy simples, hacer que el nuevo nodo apunte a la cima anterior, y definir el nuevo nodo como cima de la pila.
Vamos a ver un ejemplo de una inserción:

Al insertar sobre esta pila el elemento 0, la pila resultante sería:

Borrar

Esta operación es normalmente conocida como pop.
Cuando se elimina un elemento de la pila, el elemento que se borra es el elemento situado en la cima de la pila, el que menos tiempo lleva en la estructura.
Las operaciones a realizar son muy simples, avanzar el puntero que apunta a la cima y extraer la cima anterior.
Si aplicamos la operación pop a la pila de 4 elementos representada arriba el resultado sería:

Listas Circulares

Listas Circulares

Definicion

Una lista circular es una lista lineal en la que el último nodo a punta al primero.

-- Los tipos de datos que definiremos normalmente para manejar listas son:

*tipoNodo: es el tipo para declarar nodos
*pNodo: declarar punteros a un nodo.

Operaciones basicas

Insertar elemento en la lista vacía

• lista apunta a nodo.

• lista->siguiente apunte a nodo.

Insertar elemento en una lista no vacía

1.Hacemos que nodo = siguiente apunte a lista = siguiente.

2.Después que lista = siguiente apunte a nodo.

Eliminar el único nodo de la lista.

1.lista = siguiente mientras lista = siguiente sea distinto de nodo.

2.Hacemos que lista = siguiente apunte a nodo = siguiente.

3.Eliminamos el nodo.