Bueno este es solo un dato interesante que quize compartir con ustedes

Comparación de tiempos en ordenamientos

Se han ordenado una cantidad determinada de elementos aleatorios en una lista mediante distintos métodos de ordenamiento. (En segundos)

Ejemplo:

256 elementos

Burbuja: 0.0040

Seleccion: 0.0030

Insercion: 0.0040

Rapido: 0.0010

Shell: 0.0010

Merge: 0.0040

Otro ejemplo:

2048 elementos

Burbuja: 0.022

Seleccion: 0.015

Insercion: 0.013

Rapido: 0.0010

Shell: 0.0060

Merge: 0.0050

Complejidad

Cada algoritmo de ordenamiento por definición tiene operaciones y cálculos mínimos y máximos que realiza (complejidad), a continuación una tabla que indica la cantidad de cálculos que corresponden a cada método de ordenamiento:

Algoritmo        Operaciones maximas

Burbuja               Ω(n2)

Insercion             Ω(n2/4)

Seleccion             Ω(n2)

Shell                 Ω(n log2n)

Merge                 Ω(n logn)

Quick                Ω(n2) en peor de los casos y Ω(n logn) en el

                             promedio de los casos

A continuación una breve explicación de algunos métodos de ordenación ya mencionados.

ORDENAMIENTO BURBUJA

La idea básica del ordenamiento de la burbuja es recorrer el conjunto de elementos en forma secuencial varias veces. Cada paso compara un elemento del conjunto con su sucesor (x[i] con x [i+i]), e intercambia los dos elementos si no están en el orden adecuado. El algoritmo utiliza una bandera que cambia cuando se realiza algún intercambio de valores, y permanece intacta cuando no se intercambia ningún valor, pudiendo así detener el ciclo y terminar el proceso de ordenamiento cuando no se realicen intercambios, lo que indica que este ya está ordenado. Este algoritmo es de fácil comprensión y programación pero es poco eficiente puesto que existen n-1 pasos y n-i comprobaciones en cada paso.

void ordenar(int arreglo[], int n)
{

 

int temporal, i = 0, j, cambio = 1;
while (i<n-1 && cambio == 1)
{

  cambio=0;
for (j=0; j<n-1, j++)
{   if (arreglo[j]>arreglo[j+1])
{   cambio=1;
temporal = arreglo[j];
arreglo[j] = arreglo[j+1];
arreglo[j+1] = temporal;   }   }
i++;

}

}

ORDENAMIENTO POR INSERCCION

La estrategia del ordenamiento por inserción consiste en crear un nuevo arreglo vacío e irle insertando en la posición correcta cada uno de los elementos del arreglo original, hasta tener el arreglo ordenado. La desventaja de este método radica en su normal implementación mediante vectores ya que cuando se desea insertar un nuevo elemento en el vector, es necesario desplazar todos los elementos que hay desde ese punto hasta el final del arreglo, para así crear un espacio para el nuevo elemento.

algoritmo insertSort( A : lista de elementos ordenables )

    para i=1 hasta longitud(A) hacer

         index=A[i]

         j=i-1

         mientras j>=0 y A[j]>index hacer

              A[j+1] = A[j]

              j = j - 1

         fin mientras

         A[j+1] = index

    fin para

fin algoritmo

septima sesion

Arreglo

Un arreglo es una colección finita, homogénea y ordenada de elementos.

Finita, porque todo arreglo tiene un límite, es decir, se debe determinar cuál es el número máximo de los elementos del arreglo. Homogénea, porque todos los elementos del arreglo deben ser del mismo tipo. Ordenada, porque se puede determinar cuál es el primer elemento, cual es el segundo, y así sucesivamente.

 

Algoritmos de búsqueda

Para buscar en un arreglo ordenado por un elemento, usamos un procedimiento recursivo para lograr mayor eficiencia  Comparamos el valor con el elemento en el medio Según si es mayor o menor a los que buscamos, seguimos recursivamente con la mitad que corresponde Si es igual, ya terminamos y devolvemos “verdad”.

Datos de entrada:

  vec: vector en el que se desea buscar el dato

  tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive.

  dato: elemento que se quiere buscar.

Variables

  pos: posición actual en el array

pos = 0

Mientras pos < tam:

 Si vec[pos] == dato devolver verdadero y/o pos, de lo contrario:

 pos = pos + 1

Fin (Mientras)

Devolver falso,

Algoritmos de ordenamiento

Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar. En este caso, nos servirán para ordenar vectores o matrices con valores asignados aleatoriamente. Nos centraremos en los métodos más populares, analizando la cantidad de comparaciones que suceden, el tiempo que demora y revisando el código de cada algoritmo.

Tipos de ordenamiento

·         Ordenamiento de burbuja

·         Ordenamiento por montículos

·         Ordenamiento por inserción

·         Ordenamiento por mezcla

·         Ordenamiento rápido

·         Ordenamiento por selección

·         Ordenamiento de Shell

ejemplo de programa de recursion

#include <iostream.h>
#include <stdlib.h>
int factorial(int numero);
int main()
{   int num,f;
 cout<<"ingrese el numero para sacar factorial ";cin>>num;
 f = factorial(num);
 cout<<"el factorial es :"<<f<<endl;
      system("PAUSE");
      return 0;
}
int factorial(int numero){
if(numero==1){
return 1;
}else{
return numero*factorial(numero-1);  // aqui se hace la llamada recursiva.
}
}

Recursion como herramienta en resolucion de problemas computacionales

Modularidad

Se denomina Modularidad a la propiedad que permite subdividir una aplicación en partes más pequeñas (llamadas módulos), cada una de las cuales debe ser tan independiente como sea posible de la aplicación en sí y de las restantes partes.

"Modularidad  consiste en dividir un programa en módulos que pueden ser compilados de forma separada, pero que tienen conexiones con otros módulos"

Estos se  publican bibliotecas de tales módulos, que Se llaman “librerías” y se conoce que el módulo más pequeño es una subrutina.

Subrutina

Se presenta como un sub algoritmo que forma parte del algoritmo principal, el cual permite resolver una tarea específica. Toman uno o varios parámetros de tipos predefinidos y ejecutan su propio código a base de los parámetros recibidos

Ejemplos:

Usamos subrutinas de las bibliotecas estándares de ANSI-C para las siguientes funciones:

-Impresión en el terminal que es la biblioteca (stdio.h)

-Lectura de datos del teclado que es la biblioteca (stdio.h)

-Operaciones matemáticas en la biblioteca (math.h)

-Manipulación de cadenas de caracteres en la biblioteca(string.h)

 

Encadenados

Se  podría decir que como un método principal que llama a otro submetodo y ese a otro submetodo a si infinitamente.

Ejemplo:

-El método principal (main) puede llamar a subrutinas. Luego, esas subrutinas pueden llamar a otras subrutinas. Esas luego a otras, etcétera y no hay un límite fijo de “profundidad” de llamadas.

Flujo de control

Se dice que la (sub)rutina en ejecución “tiene control” de la computadora y al terminar su ejecución, una subrutina devuelve el control de la computadora a la rutina principal.

Iteración

 Llamas repetidas de una subrutina o la ejecución de un bloque de código en un ciclo se conoce como iteración.

Recursión

 Cuando una (sub)rutina llama a sí misma, se dice que es recursivo.

Análisis de algoritmos recursivos

Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.

Típicamente hay que escribir una ecuación recursiva para poder correctamente caracterizar la cantidad de llamadas que se hará a la rutina recursiva.

Aqui presento un ejercicio de una grfica

sexta sesion

Bueno en la primera expresion explica quef(n) pertenece a o(g(n)) si existe una constante mayor que cero tal que el valor absoluto de f(n) se menor que cg(n). Esto quiere decir que la función f es inferior a g.
En la segunda expresion explica una función f(n) pertenece a Ω(g(n)) cuando existe una constante positiva c tal que a partir de un valor absoluto  cg(n) no supera f(n). Quiere decir que la función f es superior a g.
En la tercera expresion  Una función f(n) pertenece a Θ(g(n)) cuando existen constantes positivas c₁ y c₂ tales que a partir de un valor  f(n) se encuentra atrapada entre c₁g(n) y c₂g(n). Quiere decir que las funciones f y g son iguales.

Propiedades 

 En la primera explica que si f(n) es superior  que g(n) y g(n) es superior a h(n) entonces f(n) e superior a h(n).
En la segunda explica que si f(n) es inferior que g(n) y g(n) es inferior a h (n) entonces f (n) es inferior a h(n).