Ordenación por mezcla - Merge sort

Algoritmo:

Funcion Merge_sort ( a[] , inicio , fin)
    n = fin - inicio + 1
    Si n < 2
        Retornar
    mitad=( inicio + fin ) / 2
    Merge_sort ( a , inicio , mitad )
    Merge_sort ( a , mitad + 1 , fin )
    mezclar ( m , inicio , fin )

Funcion mezclar ( a[] , inicio , fin )
    aux[ fin - inicio + 1 ]
    mitad = ( inicio + fin ) / 2
    i = inicio
    j = mitad + 1
    k = 0
    Mientras i <= mitad  && j <= fin
        Si a[i] < a[j]
            aux[k++] = a[i++]
        Si No
            aux[k++] = a[j++]
    
    Mientras i <= mitad
        aux[k++] = a[i++]
    Mientras j <= fin
        aux[k++] = a[j++]
    k=0
    Para i = inicio Hasta fin
        a[i] = aux[k++]

Ordenación por mezcla - Merge sort

Combinaciones con factoriales

Combinaciones con factoriales

Problema:

Dado un conjunto de tamaño |A|, encontrar el número de formas de elegir un subconjuto de tamaño |K|.

Algoritmo:

    Funcion combinatoria ( n , r )
        a = factorial ( n )
        b = factorial ( n - r )
        c = factorial ( r )
        respuesta = a / ( b * c )
        Retornar respuesta

Combinaciones en forma recursiva

Problema:

Dado un conjunto de tamaño |A|, encontrar el número de formas de elegir un subconjuto de tamaño |K|.

Algoritmo:

    Funcion combinatoria ( n , r )
        Si ( r == 0 or r == n ) Retornar 1
        Si ( r > n ) Retornar 0
        a = combinatoria( n - 1 , r - 1 )
        b = combinatoria( n - 1 , r )
        Retornar a + b

Combinaciones en forma recursiva

Factorial de un número entero positivo

Factorial de un número entero positivo

Problema:

Dado un entero N calcular el factorial de ese número.

Solución:

El factorial de un número entero positivo es el producto de los N números 1 * 2 * 3 ... * N.

Algoritmo:

    solucion de forma iterativa
    Funcion factorial(n)
        respueta = 1
        Para i = 1 Hasta N Hacer
            respuesta = respueta * i
        Fin Para
        Retornar respueta

    solucion de forma recursiva
    Funcion factorial(n)
        Si n < 2 Hacer
            Retornar 1
        Si No
            respuesta = factorial(n-1) * n 
        Retornar respuesta

Algoritmos de ordenación

Los algoritmos de ordenación son la base para muchos problemas computacionales, entre ellos tenemos:
-Ordenamiento por selección
-Ordenamiento por inserción
-Ordenamiento burbuja
-Ordenamiento con mezcla (merge sort )
-Ordenamiento rápido (quicksort )