Diagrama de Voronoi

Estos diagramas permiten encontrar el vecino más cercano a un punto para cada punto principal en el diagrama, o sea los puntos sobre los cuales se creó el diagrama, el cual también forma puntos propios. El nombre viene del matemático ruso que lo definió, Georgi Voronoi.

El siguiente gráfico muestra un diagrama de Voronoi de una nube de puntos:

           

Como concepto teórico: Sea P = {p₁,p₂,...,p_n} un conjunto de n puntos distintos en el plano. Definimos el diagrama de Voronoi de P como la subdivisión del plano en n regiones, cada una correspondiente a un punto deP, cumpliendo, que un punto q pertenece a la región correspondiente al punto p_isi y solamente sidist(q,p_i) < dist(q,p_j) para cada punto p_j P, con j distinto de i. Denotamos el diagrama de Voronoi de P como Vor(P). La región correspondiente al punto p_i es llamada V(p_i).

Podemos notar que no todos los puntos tiene un sitio más cercano: Todos
los puntos que tienen más de un sitio igual de cerca forman el
Diagrama de Voronoi V(P).

Inicialmente el diagrama de Voronoi fue creado para el análisis de datos meteorológicos (estaciones pluviométricas) aunque en la actualidad también se aplica en estudios en los que hay que determinar áreas de influencia (centros hospitalarios, estaciones de bomberos, bocas de metro, centros comerciales, control del tráfico aéreo, telefonía móvil, análisis de poblaciones de especies vegetales, etc.).

Aquí un video tutorial de cómo funciona el diagrama, en inglés:

Referencias:

• http://www.soygik.com/algoritmo-de-voronoi-diagrama-de-voronoi/
• http://buhoz.net/articles/2008/04/28/diagramas-de-voronoi

Complejidad Computacional

Vamos a analizar lo que es la complejidad computacional. Una de las cosas más importantes a tomar en cuenta al momento de seleccionar un algoritmo es el tiempo que se va a tardar en arrojar una salida. En ves de calcular el tiempo exacto que se puede tardar nuestro algoritmo, se calcula la cantidad de operaciones en función del tamaño de la entrada (n). Para estimar el tiempo de ejecución, esta función de crecimiento se multiplica por una constante c que representa una estimación del tiempo que una computadora se tarda en realizar una operación.

Los problemas de decisión son los problemas en donde las dos respuestas posibles sin “si” y “no”. También se puede definir como el problema de decidir si una cierta frase pertenece a un conjunto dado de frases, o lenguaje formal. El conjunto contiene exactamente las frases para las cuales la respuesta a la pregunta es positiva. Si existe un algoritmo que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje, entonces se dice que el problema es decidible, de otra forma se dice que es un problema indecidible.

Los problemas de decisión se pueden clasificar en clases de complejidad, las cuales son:

• La clase de complejidad P, la cual está formada por todos aquellos problemas de decisión para los cuales se tiene un algoritmo de solución que se ejecuta en tiempo polinomial en una máquina determinista.
• La clase de problemas NP la cual está formada por todos aquellos problemas de decisión para los cuales existe un algoritmo de solución que se ejecuta en tiempo polinomial en una máquina no determinista. Dicho de otro modo, no se ha encontrado un algoritmo determinista que lo resuelva en tiempo polinomial.

La relación entre la clase P y la clase NP es estrecha: . Cualquier problema de decisión resuelto por un algoritmo determinístico en tiempo polinomial también es resuelto por un  algoritmo no determinístico en tiempo polinomial.

*Este diagrama muestra la teoría de que todos los problemas P y NP-Completo son problemas NP, aunque no ha sido probada es la mas aceptada como probable.

 

 

Algunas clases

• TIME: o DTIME, es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(f(n)), y espacio ilimitado.
• E: es el conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing determinista en tiempo 2^O(n), y es por lo tanto igual a la clase de complejidad DTIME(2^O(n)).
• NC: es el conjunto de los problemas de decisión que pueden ser resueltos mediante computación paralela con un número polinómico de procesadores en tiempo polilogarítmico.
• NTIME: la clase de complejidad NTIME(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no-determinista en tiempo O(f(n)) y espacio ilimitado.
• PP: es una clase de problema de decisión, resoluble por una máquina de Turing probabilística, diferente de la máquina de Turing general o determinística en que las transiciones entre estados tienen la misma probabilidad de ocurrencia.
• DSPACE: es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en espacio O(f(n)) y tiempo ilimitado. Es la contrapartida determinista de la clase NSPACE.
• EXPSPACE:es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2^p(n)), donde p(n) es una función polinomial sobre n.
• L: es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing determinista tal que la solución si existe es única.
• NSPACE: es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no-determinista en espacio O(f(n)) y tiempo ilimitado. NSPACE es la contrapartida no-determinista de DSPACE.

 

Esta es la página de la organización que da 1 millón de dólares a quien resuelva el problema de P vs NP: http://www.claymath.org/millennium/P_vs_NP/

Referencias:

• http://www.di.uniovi.es/~dani/asignaturas/transparencias-leccion19.PDF
• http://es.wikipedia.org/wiki/EXPTIME

Grafos

Aquí un poco de información acerca de los grafos!

Empezamos con la definición… Un grafo se define como un conjunto de puntos, o vértices, que están conectados por un conjunto de líneas, o aristas. Los vértices son objetos que contienen información y las aristas son las conexiones entre esos vértices. Son muy utilizados en computación por que permiten resolver problemas muy complejos.

Hay dos tipos de grafos, los dirigidos y no dirigidos:

• No dirigidos:son aquellos en los cuales los lados no están orientados, o sea, no son flechas. Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).

            

• Dirigidos:son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.

           

Grafos bipartitos:un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V₁y V₂ y las aristas siempre unen vértices de un conjunto con vértices de otro:  

• 
• 
• 

Ejemplo de grafos Bipartitos:

Un grafo bipartido completo si V=V1yV2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,s al grafo bipartido completo donde V1 tiene r vértices yV2 tiene s vértices.

Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.

Gafos bipartitos completos:

****************************************************************************************************

Árboles

Los árboles son estructuras de datos que se pueden definir de forma recursiva como una estructura vacía o un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol, llamados subárboles.

En cuanto a grafos, un árbol es un grafo acíclico, conexo y no dirigido, o sea un grafo no dirigido en el que existe un camino entre cualquier par de nodos.

En los árboles: la raíz es aquel elemento que no tiene antecesor; una rama es una arista entre dos nodos; un nodo x es antecesor de un nodo y si por alguna de las ramas de x se puede llegar a y; un nodo x es sucesor de un nodo y si por alguna de las ramas de y se puede llegar a x; el grado de un nodo es el número de descendientes directos que tiene; una hoja es un nodo que no tiene descendientes; el nivel es el número de ramas que hay que recorrer para llegar a la raíz de un nodo; la altura es el nivel más alto del árbol;  por último, la anchura es el mayor valor del número de nodos que hay en un nivel.

Así se ve un árbol binario:

A es la raíz; G, H, I, K, son hojas.

Un árbol binario de búsqueda auto-balanceable es un árbol de búsqueda binaria que que intenta mantener su altura, tan pequeña como sea posible en todo momento de forma automática. Esto se realiza por lo general realizando transformaciones en el árbol, como la rotación de árboles.

Aquí una lista de tiempos asintóticos en términos de nodos en algún árbol n:

• Para búsqueda, O(log n)
• Para inserción, O(log n)
• Para eliminación, O(log n)
• Para iteración en orden, O(n)

Una liga para un código en C de árbol binario: http://www.elrincondelc.com/nuevorincon/index.php?pag=codigos&id=4

Hay dos estructuras de datos populares que implementan este tipo de datos:

• Árbol AVL: es un árbol binario de búsqueda que cumple con la condición de que la diferencia en las alturas de los subárboles de cada uno de sus nodos es máximo 1. El nombre viene de sus creadores, Adelson-Velskii y Landis. La propiedad de equilibrio que debe cumplir un árbol para ser AVL asegura que la profundidad del árbol sea O(log(n)), por lo que las  operaciones sobre estas estructuras no deberán recorrer mucho para hallar el elemento deseado. El tiempo de ejecución de las operaciones sobre estos árboles es, a lo sumo O(log(n)) en el peor caso, donde n es la cantidad de elementos del árbol.

     Este es un árbol binario no equilibrado, o sea que no es AVL                

 

 

 

        Este es un árbol binario equilibrado, o sea que si es AVL.

Un ejemplo de operación que se pueden hacer con estos árboles son las rotaciones, en las cuales el reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden ser simples o dobles, y a la derecha o a la izquierda.

Aquí muestro un ejemplo de rotación simple a la derecha:

• De un árbol de raíz (y) y de hijos izquierdo (x) y derecho (c), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de x (a) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (y), el hijo derecho de x (b) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (c).

Así se vería gráficamente:

Aquí unos ejemplos de árboles AVL en C: http://c.conclase.net/edd/?cap=008e

• Árbol rojo-negro: es un tipo de árbol que está balanceado de tal manera que el tiempo de realizar operaciones sea O(log n) en el peor de los casos. En estos el nodo contiene un campo extra el cual llamamos color, y el árbol se recorre ya sea por color rojo o negro. Cada nodo puede tener uno de estos colores. Cada apuntador de hoja es de color negro, y cada camino desde cualquier nodo hasta una hoja contiene el mismo numero de nodos negros.

Un ejemplo:

El método de rotación es básicamente el mismo que se usa en los árboles AVL.

Aquí una página con diferentes operaciones en código C que se pueden hacer en con el árbol rojo-negro. Está en inglés.

Referencias: 

• http://www.algoritmia.net/articles.php?id=18
• http://www.matediscreta.8k.com/grafos.htm
• http://www.mitecnologico.com/Main/TiposDeGrafos
• http://hgv9651etica.blogspot.com/2008/02/grafo-bipartito.html
• http://www.algoritmia.net/articles.php?id=17
• http://es.tldp.org/Tutoriales/doc-programacion-arboles-avl/avl-trees.pdf
• http://es.wikipedia.org/wiki/%C3%81rbol_AVL

Tablas de Dispersión

Primero empecemos por ver qué son las funciones de dispersión. Las funciones de dispersión consisten en la elección de una clave para el buen funcionamiento de la estructura, es la relación entre la llave y la posición en la tabla. Estas tienen las siguientes características:

• Ser una función sencilla y por tanto rápida.
• Distribuir uniformemente los elementos en el espacio de almacenamiento
• Evitar en lo posible la aparición de sinónimos
• Para dos claves muy similares, generar posiciones distantes.

Ahora, las tablas de dispersión se pueden definir como estructuras de datos que se usan en aplicaciones que manejan una secuencia de elementos, de tal forma que cada elemento tiene asociado un valor clave, que es un numero entero positivo perteneciente a un rango de valores, relativamente pequeños. En estas organizaciones, cada uno de los elementos ha de tener una clave que identifica de manera univoca el elemento.

Son estructuras de datos que tienen como finalidad realizar las operaciones fundamentales de búsqueda y eliminación de un registro.
La organización ideal de una tabla es de tal forma que el campo clave de los elementos se corresponda directamente con el índice de la tabla.

En esta imagen se puede ver lo que se le llama una tabla de dispersión ideal, que significa que cada llave está en una celda distinta.

 

****************************************************************************************************

Tablas Hash

Las tablas hash se usan para conseguir una búsqueda e inserción muy rápidas. Para eso usamos un array, con lo que volvemos a la estructura básica
de almacenamiento, aunque hay una diferencia importante que es lo que
hace que sea mejor que el array en cuanto a rapidez: a cada dato se le asigna,
mediante una fórmula matemática llamada función hash, una posición única
en la tabla, con lo que la búsqueda, la inserción y el borrado son inmediatos: O(1).

Los inconvenientes de una tabla hash son:

• Al tratarse de un array, el tamaño de la tabla está limitado y debe fijarse
  desde el principio.
• Como las posiciones ocupadas no tienen por qué ser consecutivas, no se
  puede recorrer el contenido de una tabla hash.
• Como la posición de una palabra se calcula de forma matemática, los datos no pueden almacenarse ordenados.
• Si permitimos datos duplicados se produce lo que se denomina “colisión”,
  que consiste en que a dos palabras se les asigna la misma posición en el
  array.

Aquí hice un ejemplo para explicar una tabla hash, y también una función hash.

En ésta tabla, la función hash genera un índice basado en el dígito colocado en el extremo derecho del valor ASCII de la segunda letra del nombre de la persona.

Por ejemplo, en el nombre “Jessica”, la segunda letra es una “e”. El valos ASCII de “e” es 101. El dígito colocado en el extremo derecho de 101 es 1, por lo tanto el registro para “Jessica” es almacenado en el índice 1 de la tabla hash.

La tabla hash en la figura anterior muestra cada nombre en su posición asignada.

Las implantaciones de tablas hash con complicadas por que deben manejar colisiones potenciales. Básicamente, las colisiones disminuyen el desempeño de las operaciones de la tabla hash. La mejor manera de reducir el número de colisiones e incrementar la eficiencia de la tabla hash, es usar una buena función hash, la cual distribuye equitativamente la asignación de claves a través de las posiciones de la tabla hash.

Referencias:

• http://www.ganimides.ucm.cl/haraya/doc/Tablas_de_Dispersion.pdf
• http://www.ie.uia.mx/acad/atortole/progra2/hash.html
• http://www.creationexus.tk/component/kunena/50-Programaci%C3%B3n/400-Tablas-de-Dispersion-o-Funciones-Hash.html
• http://www.iuma.ulpgc.es/users/jmiranda/docencia/programacion/Tema8_ne.pdf
• http://www.slideshare.net/lcahuich/15-tablas-hash

Listas Doblemente Enlazadas

Ahora escribiré un poco sobre las listas doblemente enlazadas, las cuales son similares a las simplemente enlazadas, con la diferencia en que el enlace entre los elementos se hace gracias a dos punteros, uno que apunta al anterior y otro que apunta al elemento siguiente.

El puntero anterior del primer elemento debe apuntar hacia NULL (el inicio de la lista).
El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).
Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos: Comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento. Comenzando por el final, el puntero anterior permite el desplazamiento hacia el elemento anterior.

A continuación algunas acciones que se pueden llevar a cabo con las listas, junto con un ejemplo en C.

I. Inserción en una lista vacía

1. Asignación de memoria para el nuevo elemento
2. Rellenar el campo de datos del nuevo elemento
3. El puntero anterior del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía utilizamos la dirección del puntero inicio que vale NULL)
4. El puntero siguiente del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía se utiliza la dirección del puntero fin que vale NULL)
5. Los punteros inicio y fin apuntaran hacia el nuevo elemento
6. El tamaño es actualizado

Ejemplo gráfico:

Código en C:

int insercion_en_lista_vacia (dl_Lista * lista, char *dato){
  dl_Elemento *nuevo_elemento;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  nuevo_elemento->anterior = lista->inicio;
  nuevo_elemento->siguiente = lista->fin;
  lista->inicio = nuevo_elemento;
  lista->fin = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

II. Inserción al inicio de la lista:

1. Asignación de memoria al nuevo elemento
   
2. Rellenar el campo de datos del nuevo elemento
   
3. El puntero anterior del nuevo elemento apunta hacia NULL
   
4. El puntero siguiente del nuevo elemento apunta hacia el 1er elemento
   
5. El puntero anterior del 1er elemento apunta hacia el nuevo elemento
   
6. El puntero inicio apunta hacia el nuevo elemento
   
7. El puntero fin no cambia
   
8. El tamaño es incrementado

Ejemplo gráfico:

Código en C:

int ins_inicio_lista(dl_Lista * lista, char *dato){
  dl_Elemento *nuevo_elemento;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  nuevo_elemento->anterior = NULL;
  nuevo_elemento->siguiente = lista->inicio;
  lista->inicio->anterior = nuevo_elemento;
  lista->inicio = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

III. Inserción al final de la lista

1. Asignación de memoria al nuevo elemento
   
2. Rellenar el campo de datos del nuevo elemento
   
3. El puntero siguiente del nuevo elemento apunta hacia NULL
   
4. El puntero anterior del nuevo elemento apunta hacia el ultimo elemento (es el puntero fin que contiene por ahora su dirección)
   
5. El puntero siguiente del ultimo elemento apuntará hacia el nuevo elemento
   
6. El puntero fin apunta hacia el nuevo elemento
   
7. El puntero inicio no cambia
   
8. El tamaño es incrementado

Ejemplo gráfico:

Código en C:

int ins_fin_lista(dl_Lista * lista, char *dato){
  dl_Elemento *nuevo_elemento;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  nuevo_elemento->siguiente = NULL;
  nuevo_elemento->anterior = lista->fin;
  lista->fin->siguiente = nuevo_elemento;
  lista->fin = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

IV. Inserción antes de un elemento de la lista.

1. Asignación de memoria al nuevo elemento
   
2. Rellenar el campo de datos del nuevo elemento
   
3. Elegir una posición en la lista (la inserción se hará después de la posición elegida)
   
4. El puntero siguiente del nuevo elemento apunta hacia el elemento actual.
   
5. El puntero anterior del nuevo elemento apunta hacia la dirección hacia la que apunta el puntero anterior del elemento actual.
   
6. El puntero siguiente del elemento que precede al elemento actual apuntará hacia el nuevo elemento
   
7. El puntero anterior del elemento actual apunta hacia el nuevo elemento
   
8. El puntero fin no cambia
   
9. El puntero inicio cambia si la posición elegida es la posición 1
   
10. El tamaño se incrementa en una unidad

Ejemplo gráfico:

La función

int ins_antes (dl_Lista * lista, char *dato, int pos){
  int i;
  dl_Elemento *nuevo_elemento, *actual;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  actual = lista->inicio;
  for (i = 1; i < pos; ++i)
    actual = actual->siguiente;
  nuevo_elemento->siguiente = actual;
  nuevo_elemento-> anterior = actual->anterior;
  if(actual->anterior == NULL)
    lista->inicio = nuevo_elemento;
  else
    actual->anterior->siguiente = nuevo_elemento;
  actual->anterior = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

V. Inserción después de un elemento

1. Asignación de memoria al nuevo elemento
   
2. Rellenar el campo de datos del nuevo elemento
   
3. Elegir una posición en la lista (la inserción se hará después de la posición elegida)
   
4. El puntero siguiente del nuevo elemento apunta hacia la dirección hacia la que apunta el puntero siguiente del elemento actual.
   
5. El puntero anterior del nuevo elemento apunta hacia el elemento actual.
   
6. El puntero anterior del elemento que va después del elemento actual apuntará hacia el nuevo elemento.
   
7. El puntero siguiente del elemento actual apunta hacia el nuevo elemento
   
8. El puntero inicio no cambia
   
9. El puntero fin cambia si la posición elegida es la posición del ultimo elemento (el tamaño de la lista)
   
10. El tamaño se incrementa en una unidad

Ejemplo gráfico:

Código en C:

int ins_después (dl_Lista * lista, char *dato, int pos){
  int i;
  dl_Elemento *nuevo_elemento, *actual;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  actual = lista->inicio;
  for (i = 1; i < pos; ++i)
    actual = actual->siguiente;
  nuevo_elemento->siguiente = actual->siguiente;
  nuevo_elemento->anterior = actual;
  if(actual->siguiente == NULL)
    lista->fin = nuevo_elemento;
  else
    actual->siguiente->anterior = nuevo_elemento;
  actual->siguiente = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

VI. Eliminación en la lista:

Para esta función podemos tener diferentes situaciones:

• Eliminación en la posición 1 en una lista con un solo elemento
  
• Eliminación en la posición 1 en una lista con varios elementos
  
• Eliminación en la ultima posición (el ultimo elemento)
  
• Eliminación en otra parte de la lista en cierta posición

 

• La posición elegida es 1 (el caso de eliminación del 1er elemento de la lista)




1. El puntero sup_elemento contendrá la dirección del 1er elemento
   
2. El puntero inicio contendrá la dirección contenida por el puntero siguiente del 1er elemento que deseamos eliminar (si este puntero vale NULL entonces actualizamos el puntero fin ya que estamos en el caso de una lista con un solo elemento, si no hacemos apuntar el puntero anterior del 2do elemento hacia NULL)

• la posición elegida es igual al numero de elementos de la lista




1. El puntero sup_elemento contendrá la dirección del ultimo elemento
   
2. Hacemos apuntar al puntero siguiente del penúltimo elemento (es el elemento hacia el que apunta el puntero <anterior> del ultimo elemento), hacia NULL
   
3. Actualizamos el puntero fin

• la posición elegida es aleatoria en la lista




1. El puntero sup_elemento contendrá la dirección del elemento a eliminar
   
2. El puntero siguiente del elemento que antecede al elemento a eliminar apunta hacia la dirección contenida en el puntero siguiente del elemento a eliminar
   
3. El puntero anterior del elemento que va después del elemento a eliminar apunta hacia la dirección contenida en el puntero anterior del elemento a eliminar.
   
4. El tamaño de la lista será disminuida en 1 elemento

Código en C:

int supp(dl_Lista *lista, int pos){
  int i;
  dl_Elemento *sup_elemento,*actual;

  if(lista->tamaño == 0)
    return -1;

  if(pos == 1){ /* eliminación del 1er elemento */
    sup_elemento = lista->inicio;
    lista->inicio = lista->inicio->siguiente;
    if(lista->inicio == NULL)
      lista->fin = NULL;
    else
      lista->inicio->anterior == NULL;
  }else if(pos == lista->tamaño){ /* eliminación del último elemento */
    sup_elemento = lista->fin;
    lista->fin->anterior->siguiente = NULL;
    lista->fin = lista->fin->anterior;
  }else { /* eliminación en otra parte */
    actual = lista->inicio;
      for(i=1;i<pos;++i)
        actual = actual->siguiente;
    sup_elemento = actual;
    actual->anterior->siguiente = actual->siguiente;
    actual->siguiente->anterior = actual->anterior;
  }
  free(sup_elemento->dato);
  free(sup_elemento);
  lista->tamaño--;
  return 0;
}

VII. Visualización de la lista:

Para mostrar la lista entera podemos posicionarnos al inicio o al final de la lista.
Luego utilizando el puntero siguiente o anterior de cada elemento, la lista es recorrida del 1er al ultimo elemento o del ultimo al 1er elemento.
La condición para detener es dada por el puntero siguiente del ultimo elemento que vale NULL en el caso de la lectura del inicio hacia el fin de la lista, o por el puntero anterior del 1er elemento que vale NULL, en el caso de una lectura del final hacia el inicio de la lista.

Código en C:

void affiche(dl_Lista *lista){ /* visualización hacia adelante */
  dl_Elemento *actual;
  actual = lista->inicio; /* punto de inicio el 1er elemento */
  printf("[ ");
  while(actual != NULL){
    printf("%s ",actual->dato);
    actual = actual->siguiente;
  }
  printf("]\n");
}

void mustra_inv(dl_Lista *lista){ /* visualización hacia atrás */
  dl_Elemento *actual;
  actual = lista->fin; /* punto de inicio el ultimo elemento */
  printf("[ ");
  while(actual != NULL){
    printf("%s : ",actual->dato);
    actual = actual->anterior;
  }
  printf("]\n");
}

Como en la entrada anterior, dejo un archivo con todo el código en C del ejemplo de las listas doblemente enlazadas.

http://www.mediafire.com/?b26u6uf887xcdjn

Referencias:

• http://es.kioskea.net/faq/2872-listas-doblemente-enlazadas


• http://c.conclase.net/edd/?cap=005

Listas Simplemente Enlazadas

Les escribiré un poco acerca de las listas enlazadas.

La lista enlazada es un tipo de estructura de datos que permite almacenar datos de forma organizada de igual manera que los vectores, con la diferencia de que ahora la estructura es dinámica, queriendo decir que no tenemos que saber los elementos que pueda contener. En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.

Este es un ejemplo gráfico de lo que es una lista simplemente enlazada:

Una lista simplemente enlazada tiene las siguientes características:

• Los elementos son contiguos en cuanto al enlazado.
• Los elementos están dispersos en la memoria.
• El enlace entre los elementos se hace por medio de un puntero.
• En la memoria la representación es aleatoria en función al espacio asignado.
• El puntero “siguiente” del último elemento debe apuntar hacia NULL (el fin de la lista)
• Para acceder a un elemento, la lista es recorrida comenzando por el inicio, el puntero “siguiente” permite el desplazamiento hacia el próximo elemento.
• El desplazamiento se hace en una sola dirección, del primer al último elemento.
  

A continuación algunas acciones que se pueden llevar a cabo con las listas, junto con un ejemplo en C.

I. Inserción en una lista vacía:

1. Se asigna memoria para el nuevo elemento
2. Se rellena el campo de datos del nuevo elemento
3. El puntero siguiente del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía se utiliza la dirección del puntero inicio que vale NULL)
4. Los punteros inicio y fin apuntaran hacia el nuevo elemento
5. El tamaño es actualizado

Aquí un ejemplo gráfico:

Código en C:

int ins_en_lista_vacia (Lista * lista, char *dato){
  Element *nuevo_elemento;
  if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nuevo _elemento->dato = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);

  nuevo_elemento->siguiente = NULL;
  lista->inicio = nuevo_elemento;
  lista->fin = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

II. Inserción al inicio:

1. Se asigna memoria al nuevo elemento
   
2. Rellenar el campo de datos del nuevo elemento
   
3. El puntero siguiente del nuevo elemento apunta hacia el primer elemento
   
4. El puntero inicio apunta hacia el nuevo elemento
   
5. El puntero fin no cambia
   
6. El tamaño es incrementado

Ejemplo gráfico:

Código en C:

int ins_inicio_lista (Lista * lista, char *dato){
  Element *nuevo_elemento;
  if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);

  nuevo_elemento->siguiente = lista->inicio
  lista->inicio = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

III. Inserción al final:

1. Asignación de memoria al nuevo elemento
   
2. Rellenar el campo de datos del nuevo elemento
   
3. El puntero siguiente del ultimo elemento apunta hacia el nuevo elemento
   
4. El puntero fin apunta hacia el nuevo elemento
   
5. El puntero inicio no cambia
   
6. El tamaño es incrementado

Ejemplo gráfico:

El código en C:

/*inserción al final de la lista */
int ins_fin_lista (Lista * lista, Element * actual, char *dato){
  Element *nuevo_elemento;
  if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);

  actual->siguiente = nuevo_elemento;
  nuevo_elemento->siguiente = NULL;

  lista->fin = nuevo_elemento;

  lista->tamaño++;
  return 0;
}

IV. Inserción en otra parte de la lista:

1. Asignación de memoria al nuevo elemento
   
2. Rellenar el campo de datos del nuevo elemento
   
3. Elegir una posición en la lista (la inserción se hará después de haber elegido la posición)
   
4. El puntero siguiente del nuevo elemento apunta hacia la dirección a la que apunta el puntero siguiente del elemento actual.
   
5. El puntero siguiente del elemento actual apunta al nuevo elemento
   
6. Los punteros inicio y fin no cambian
   
7. El tamaño se incrementa en una unidad

Ejemplo gráfico:

Código en C:

int ins_lista (Lista * lista, char *dato, int pos){
  if (lista->tamaño < 2)
    return -1;
  if (pos < 1 || pos >= lista->tamaño)
    return -1;

  Element *actual;
  Element *nuevo_elemento;
  int i;

  if ((nuevo_elemento = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;

  actual = lista->inicio;
  for (i = 1; i < pos; ++i)
    actual = actual->siguiente;
  if (actual->siguiente == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);

  nuevo_elemento->siguiente = actual->siguiente;
  actual->siguiente = nuevo_elemento;
  lista->tamaño++;
  return 0;

V. Eliminación al inicio de la lista:

1. el puntero sup_elem contendrá la dirección del 1er elemento
   
2. el puntero inicio apuntara hacia el 2do elemento
   
3. el tamaño de la lista disminuirá un elemento

Ejemplo gráfico:

int sup_inicio (Lista * lista){
  if (lista->tamaño == 0)
    return -1;
  Element *sup_elemento;
  sup_element = lista->inicio;
  lista->inicio = lista->inicio->siguiente;
  if (lista->tamaño == 1)
    lista->fin = NULL;
  free (sup_elemento->dato);
  free (sup_elemento);
  lista->tamaño--;
  return 0;
}

VI. Eliminación en otra parte:

1. el puntero sup_elem contendrá la dirección hacia la que apunta el puntero siguiente del elemento actual
   
2. el puntero siguiente del elemento actual apuntara hacia el elemento al que apunta el puntero siguiente del elemento que sigue al elemento actual en la lista 

*Si el elemento actual es el penúltimo elemento, el puntero fin debe ser actualizado

Ejemplo gráfico:

Código en C:

int sup_en_lista (Lista * lista, int pos){
  if (lista->tamaño <= 1 || pos < 1 || pos >= lista->tamaño)
    return -1;
  int i;
  Element *actual;
  Element *sup_elemento;
  actual = lista->inicio;

  for (i = 1; i < pos; ++i)
    actual = actual->siguiente;

  sup_elemento = actual->siguiente;
  actual->siguiente = actual->siguiente->siguiente;
  if(actual->siguiente == NULL)
          lista->fin = actual;
  free (sup_elemento->dato);
  free (sup_elemento);
  lista->tamaño--;
  return 0;
}

VI. Visualización de la lista

• Para mostrar la lista entera hay que posicionarse al inicio de la lista (el puntero inicio lo permitirá). Luego utilizando el puntero siguiente de cada elemento la lista es recorrida del 1ero al último elemento.
  La condición para detener es dada por el puntero siguiente del ultimo elemento que vale NULL.

Código en C:

void visualización (Lista * lista){
  Element *actual;
  actual = lista->inicio;
  while (actual != NULL){
      printf ("%p - %s\n", actual, actual->dato);
      actual = actual->siguiente;
  }
}

Aquí les dejo una liga que encontré en dónde se puede descargar en un archivo .txt un código bastante completo en C de listas simplemente enlazadas, en dónde se pueden hacer las acciones anteriores:http://www.mediafire.com/?s6vab8x0sk4c7h8

Referencias:

• http://es.kioskea.net/faq/2842-la-lista-enlazada-simple


• http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/ldoble.html

Tutorial Wine

Ya anteriormente les escribí un tutorial para instalar Ubuntu dentro de Windows, ahora este es un tutorial para hacer algo parecido desde Ubuntu. Se llama Wine, y no instala Windows en sí, mas bien es un programa que permite correr aplicaciones de Windows.
Definición según Wikipedia: es una re implementación de la interfaz de programación de aplicaciones de Win16 y Win32 para sistemas operativos basados en Unix. Permite la ejecución de programas diseñados para MS-DOS, y las versiones de Microsoft Windows 3.11, 95, 98, Me, NT, 2000, XP, Vista y 7.
Para una información completa en inglés, pueden visitar esta liga: http://wiki.winehq.org/
Aquí el paso a paso para instalar y sacar lo mejor de Wine dese Ubuntu 11.04 (Natty Narwhal):
Abrir Terminal, y añadir los repositorios de wine:
sudo add-apt-repository ppa:ubuntu-wine/ppa
Instalar la actualización o nueva versión de wine con:
sudo apt-get update
sudo aptitude install wine

Para saber que version de wine tienes instalada puedes ejecutar:
wine --version (doble guion)

Al estar recien instalado no tenemos el directorio .wine así que ejecutamos:
winecfg
Se abre el asistente de configuración de wine, donde podemos seleccionar si queremos ejecutar wine a pantalla completa o como una ventana mas del escritorio, o el tipo de sonido que utilizamos. Al pulsar “Aceptar” se aplican los cambios de configuración y se crea nuestro directorio “.wine”.
Instalaremos un script llamado winetricks que nos instala muchas cosas que necesita el Windows.
Para usarlo, nos descargamos el script (para tenerlo a mano lo instalaremos en .wine):
cd
cd .wine
wget wget http://www.kegel.com/wine/winetricks
le damos  permisos de ejecución:
chmod +x ./winetricks
Se instala de manera automática.
Se recomienda instalar las siguientes librerías:
DirectX 9 (imprescindibles para jugar a juegos):

./winetricks d3dx9
Las fuentes de texto droid que mejoran mucho la legibilidad en pantalla:
./winetricks droid
PhysX, el motor de fisicas PhysX (si dispones de alguna tarjeta Nvidia):
./winetricks physx
Metapaquete que instala un fuentes de texto (como Arial, Sans Serif, etc utilizadas en Windows):
./winetricks allfonts
Metapaquete que instala un montón de codecs para reproducir video y audio.
./winetricks allcodecs
- Fijo la version de sistema que emulo como Windows XP (esto también se hace desde winecfg):
./winetricks winxp
./winetricks sound=alsa
Renombrar la carpeta drive_c como harddiskvolume0 (que a veces es necesario en muchos instaladores):
./winetricks volnum
Deshabilitar GLSL usado por Direct3D:
./winetricks glsl-disable
Instalar librerías de Visual C 2008 (necesarias por algunos juegos):
./winetricks vcrun2008
Las librerias dcom (si dispones de la licencia de Windows 98):
./winetricks dcom98
Se puede instalar el framework NET 2.0 (requiere licencia):
./winetricks dotnet20
Puede que falte alguna DLL si eso pasa se muestra un error en la consola diciendo que te falta una DLL (nombre) y tendrás que bajarla y copiarla en tu
.wine/drive_c/windows/System32

Para facilitar la instalación, puede que necesites quitar o añadir alguna:
./winetricks d3dx9 droid winxp sound=alsa volnum vcrun2008 dotnet20 ie6 corefonts
Se ha añadido ie6 (internet explorer 6) y corefonts (fuentes de Windows).

Para la configuración de tarjeta 3D, hay 2 métodos:
Método 1: Para añadir claves al registro (lo harías exactamente igual que en Windows) ejecutando:
wine regedit


se abre el editor de registro y ya se puede cambiar las claves o añadir nuevas.
Una vez nos ha abierto el programa regedit , buscamos en la siguiente dirección:
HKEY_CURRENT_USER\Software\Wine\Direct3D
Las claves a añadir el caso de tener una tarjeta Nvidia para la key DIRECT3D son:
“DirectDrawRenderer”=”opengl”
“Nonpower2Mode”=”repack”
“OffscreenRenderingMode”=”fbo”
“RenderTargetLockMode”=”auto”
“UseGLSL”=”readtex”
“VertexShaderMode”=”hardware”
“VideoDescription”=”NVIDIA GeForce 8500 GT”
“VideoDriver”=”nv4_disp.dll”
“VideoMemorySize”=”256″
Las entradas que aparecen en negritas son las que cambiarían, dependiendo del modelo de la tarjeta. Las demás quedarían igual en todas las tarjetas Nvidia.

Método 2: Tambien se puede hacer de manera más rápida, ir al directorio .wine y editar un fichero llamado “user.reg”, en ese fichero se van almacenando las claves del registro que va creando el usuario. Se edita el fichero, al final del mismo se pega el contenido:
sudo gedit  /home/"usuario ubuntu"/.wine/user.reg
en usuario ubuntu hay que poner el nombre de nuestro usuario en el sistema
[Software\\Wine\\Direct3D] 1258821033
"DirectDrawRenderer"="opengl"
"Nonpower2Mode"="repack"
"OffscreenRenderingMode"="fbo"
"RenderTargetLockMode"="auto"
"UseGLSL"="readtex"
"VertexShaderMode"="hardware"
"VideoDescription"="NVIDIA GeForce 8500 GT"
"VideoDriver"="nv4_disp.dll"
"VideoMemorySize"="256"
Para cualquier otra duda ó cambiar más parámetros,lo mejor es consultar la página web de wine: Wine HQ
Referencias:
http://wiki.winehq.org/FAQ
http://wiki.winehq.org/Debunking_Wine_Myths
http://morfeox69.blogspot.com/2011/05/instalar-wine-correctamente-en-ubuntu.html
http://wiki.winehq.org/ListofCommands

Pilas y Colas

Las pilas y colas son estructuras de datos que se generalmente simplifican ciertas operaciones de programación. Estas estructuras pueden implementarse mediante “arrays” o mediante listas enlazadas.

Pilas

Las pilas son estructuras de datos a las cuales se les puede acceder por un solo extremo de la misma. Las operaciones de inserción y extracción se realizan a través del tope, por lo cual no se puede acceder a cualquier elemento de la pila. Tienen dos operaciones básicas: “push” para insertar elementos, y “pop” para extraer elementos. Son conocidas también como estructuras de datos LIFO, que en inglés quiere decir “last in, first out”, o último en entrar, primero en salir. La pila se considera un grupo ordenado de elementos, teniendo en cuenta que el orden de los mismos depende del tiempo que lleven "dentro" de la estructura. Una posible
implementación mediante listas enlazadas sería insertando y extrayendo
siempre por el principio de la lista. Gracias a las pilas es posible el uso de la
recursividad. La variable que llama al mismo procedimiento en el q está, habrá que guardarla así como el resto de variables de la nueva llamada, para a la vuelta de la recursividad ir sacándolas, esto es posible a la implementación de pilas.

Aquí una representación gráfica de cómo es una pila, mostrando como de apila y desapila siempre en el tope.

Y aquí un ejemplo del código escrito en Python:

>>> pila = [6,7,8]
>>> pila.append(9)
>>> pila
[6, 7, 8, 9]
>>> pila.pop()
9
>>> pila.pop()
8
>>> pila[-1]
7

**************************************************************

Colas

Las colas también son llamadas FIFO (First In First Out), que quiere
decir “el primero que entra es el primero que sale”. Tanto el frente como el final de la cola, son los únicos indicados para retirar e insertar elementos, respectivamente. Esto significa que no podemos acceder directamente a cualquier elemento de la cola, sino solo al primero, o sea el que está o se encuentra en el frente, y no se pueden insertar elementos en cualquier posición sino solo por el final, así el elemento insertado queda como último.

Colas simples:
Se inserta por un sitio y se saca por otro, en el caso de la cola simple se
inserta por el final y se saca por el principio. Para realizar este tipo de cola
hay que recordar siempre cual es el siguiente elemento que se va a leer  y cual
es el último elemento que se ha introducido.

Colas circulares:
En las colas circulares se considera que después del último elemento se
accede de nuevo al primero. De esta forma se reutilizan las posiciones
extraídas, el final de la cola es a su  vez el principio, creándose un circuito
cerrado.

Aquí un ejemplo:

Lo que sucedió en esta tabla fue que se insertó un 5, se sacó un 1 y se insertó un 8.

Colas con prioridad:
Las colas con prioridad se implementan mediante listas o arrays
ordenados. No nos interesa en este caso que salgan en el  orden de entrada
sino con una prioridad que le asignemos. Puede darse el caso que existan
varios elementos con la misma prioridad, en este caso saldrá primero aquel
que primero llego (FIFO).

Aquí un ejemplo de cola en Python:

>>> queue = ["Erick", "Juan", "Miguel"]

>>> queue.append("Tomás") # llega Tomás

>>> queue.append("Gerardo") # llega Gerardo

>>> queue.pop(0)

'Erick'

>>> queue.pop(0)

'Juan'

>>> queue

Y aquí una liga donde se muestra una cola de prioridades en código Python:

http://es.w3support.net/index.php?db=so&id=407734

 

Referencias:

• http://www.iuma.ulpgc.es/users/jmiranda/docencia/programacion/Tema4_ne.pdf


• http://html.rincondelvago.com/pilas-y-colas.html


• http://www.juanjoconti.com.ar/2010/07/22/pilas-y-cola-en-python/

Búsqueda Binaria

La búsqueda binaria, también llamada dicotómica,  es de los algoritmos de búsqueda más eficientes que hay. Para poder llevarla a cabo, es necesario que los elementos del vector estén ordenados previamente, ya sea de forma ascendente o descendente.

Estos son los pasos que se llevan a cabo en este tipo de búsqueda:

1. Se divide el vector en dos partes iguales.
2. Si el elemento en el centro del vector es mayor que el del elemento buscado, busca en la primera mitad.
3. Si el elemento en el centro del vector es menor que el elemento buscado, busca en la segunda mitad.
4. Se repiten los pasos hasta llegar al elemento que es buscado. En caso de no encontrarlo, el valor regresado es falso.

Aquí un muy breve video en donde se puede ver gráficamente lo que sucede cuando se ejecuta la búsqueda binaria, en dónde se busca el valor 17 en un vector de 40 valores.

Y aquí una liga para ver el código en C, en donde se aplica de forma recursiva: http://mygnet.net/codigos/c/metodos_de_busqueda/busqueda_binaria_de_forma_recursiva_sobre_un_vector_ordenado_dot_muy_completo.2936

Referencias:

http://www.programacionfacil.com/estructura_datos_csharp:busqueda_binaria

Instalar Ubuntu dentro de Windows

Aquí les escribiré un pequeño tutorial para aquellos que quieren instalar Ubuntu dentro de Windows, para tener la opción de elegir con que sistema operativo quieres trabajar desde que enciendes el computador.
La manera mas sencilla es usando un programa llamado WUBI (Windows Ubuntu Installer)
 
Lo primero que deben hacer es entrar a esta liga: http://www.ubuntu.com/download/ubuntu/windows-installer. Después dar click donde dice Start Download, como se muestra en la imagen.

Después se debe aparecer el ejecutable en la carpeta de descargas:
Abrimos el ejecutable y nos aparecen diferentes opciones como en que disco se va a instalar y el tamaño, el escritorio de Ubuntu que deseamos, y el idioma. El tamaño de instalación de Ubuntu es de 17GB, pero es recomendable seleccionar un poco mas espacio para tus archivos.

Después de poner dos veces la contraseña que deseen, simplemente den click en instalar y el programa se pondrá rápidamente a trabajar. Dependiendo de tu computadora y conexiones es lo que se va a tardar. En mi caso no fueron mas de 3 minutos.

Después que Ubuntu está instalado, se debe reiniciar la computadora. Al arranque (boot) una pantalla negra aparecerá preguntando con qué sistema operativo deseas empezar. Con las flechas y el enter se selecciona Ubuntu, y desde ahí podemos empezar a descubrir sus funcionalidades. Natty Narwal, que es la versión actual, determina en automático si tu computadora puede soportar la interfaz Unity. En caso de que no, se presenta la interfaz clásica parecida a GNOME.
Aquí una liga, en inglés, con 5 cosas que querrás hacer recién instales Ubuntu: http://www.pcworld.com/businesscenter/article/209202/5_things_to_do_first_with_ubuntu.html
Ojalá les sirva este aporte!

Métodos de Ordenamiento

Los algoritmos de ordenamiento nos permite, como su nombre lo dice, ordenar. En
este caso, nos servirán para ordenar vectores o matrices con valores asignados
aleatoriamente.

Para poder ordenar una cantidad determinada de números almacenadas en un vector o
matriz, existen distintos métodos (algoritmos) con distintas características y
complejidad. Existe desde el método mas simple, como el Bubblesort (o Método Burbúja), que son simples iteraciones, hasta el Quicksort (Método Rápido), que al estar optimizado usando recursión, su tiempo de ejecución es menor y es más efectivo.

Existen dos tipos de métodos de ordenamiento, los cuáles son:

- Iterativos: Estos métodos son simples de entender y de programar ya que son iterativos, simples ciclos y sentencias que hacen que el vector pueda ser ordenado.

-Recursivos: Estos métodos son aún mas complejos, requieren de mayor atención y conocimiento para ser entendidos. Son rápidos y efectivos, utilizan generalmente la técnica Divide y vencerás, que consiste en dividir un problema grande en varios pequeños para que sea más fácil resolverlos. Mediante llamadas recursivas a si mismos, es posible que el tiempo de ejecución y de ordenación sea más optimo.

Aquí resumiré y explicaré brevemente algunos de los más importantes métodos de ordenamiento:

• Burbuja: También llamado “bubble sort” es el más sencillo de los métodos, pero muy ineficiente. Lo que hace es que recorre el arreglo intercambiando los valores adyacentes que estén ordenados. Se recorre una y otra ves dicho arreglo hasta que sea imposible realizar cambios. Concretamente lo que hace es que agarra el valor mayor y lo recorre de posición en posición hasta ponerlo en su lugar.

• Complejidad:

1. O(n²)
2. Peor caso n(n-1)/2
• Aquí un pequeño gif explicando el método:

                         

• Liga para códico en ANSI C: http://www.ajpdsoft.com/modules.php?name=Content&pa=showpage&pid=236
• Ordenamiento por inserción: En este método, también llamado insertion sort, cuando hay n elementos, se toma el elemento n+1 y se compara con los elementos previamente ordenados, deteniéndose al detectar un elemento menor, y es aquí cuando se inserta el elemento k+1 desplazando así a los demás elementos.

• Complejidad:

1. O(n²) 
2. Peor caso: Ω(n)
• Gif explicando el método:

                         

•   Liga para código en ANSI C: http://www.cs.auckland.ac.nz/~jmor159/PLDS210/niemann/s_ins.txt
• Shell sort: . Ordena subgrupos de elementos separados K unidades del arreglo original. El valor K es llamado incremento. Después de que los primeros K subgrupos han sido ordenados), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K. Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado. Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.
• Complejidad:
• O(n^1.25)
• Peor caso: O(n²)
• Aquí un ingenioso video que explica cómo funciona:
  
•   Código en ANSI C: http://www.java2s.com/Code/C/Data-Structure-Algorithm/TheShellSort.htm
• Quick Sort: Este método se basa en la filosofía de “divide y vencerás”. Tiene dos fases, una de particiones y la otra de ordenamiento. En la fase de particiones, listas de dos o mas elementos son divididas en listas mas pequeñas. Todos los objetos menores al valor que fue asignado como pivote se van a una lista, y los que son mayores a otra. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
• Complejidad:

• Promedio: O(n log n),

• Peor caso: O(n²)

• Gif del método:

  
• Código en ANSI C: http://www.daniweb.com/software-development/c/code/216793
• Merge Sort: Es otro ejemplo del principio de “divide y vencerás”. Si el vector tiene mas de dos elementos se lo divide en dos mitades, se invoca recursivamente al algoritmo y luego se hace un merge de las dos mitades ordenadas. Primero se divide en dos sublistas de aproximadamente la mitad del tamaño, se ordena cada lista recursivamente utilizando el ordenamiento por mezcla y al final las dos sublistas en una sola lista ordenada.
• Complejidad:
• O(n log n)
• Peor caso: O(n log n)
• Gif explicativo:

                             

• Código en ANSI C: http://www.rs.io/msort.c/
• Heap sort: Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo, y luego extraer el nodo que queda como nodo raíz del montículo en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento de todos los almacenados en él.
• Complejidad: O(n log n)
• peor caso:
• Gif explicativo:

             

• Código en C: http://www.algorithmist.com/index.php/Heap_sort.c
• Radix Sort: Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan. Se empieza en el dígito más significativo y se avanza por los dígitos menos significativos mientras coinciden los dígitos correspondientes en los dos números. El número con el dígito más grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos (por supuesto sí coinciden todos los dígitos de ambos números, son iguales).
• Complejidad: O(nk)
• Aquí un video con la representación gráfica y con audio de cómo sería la implementación:
  
• Aquí el código en C: http://www.dreamincode.net/code/snippet2030.htm

 

Ya viendo cada uno de éstos métodos es posible comparar la eficiencia de algunos en ésta liga: http://www.sorting-algorithms.com/ en dónde te muestran gráficamente como se comportan con datos arreglados de diferentes maneras.

 

Referencias:

• blog.zerial.org/ficheros/Informe_Ordenamiento.pdf

• http://www.monografias.com/trabajos/algordenam/algordenam.shtml

• http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm

• http://latecladeescape.com/con-nombre-propio/ordenacion-por-el-metodo-de-shell-shellsort.html

• http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento

• www.cs.toronto.edu/~neto/teaching/238/16/mergesort.html

• http://es.wikipedia.org/wiki/Ordenamiento_por_mont%C3%ADculos

• http://ict.udlap.mx/people/ingrid/Clases/IS211/Radix.html