Algoritmos divide y vencerás


Teoría de Algoritmos


Práctica de Algoritmos Divide y Vencerás




















































Práctica Divide yVencerás

Objetivo:

El objetivo de esta primera práctica es el de diseñar e implementar algoritmos basados en la técnica de divide y vencerás para resolver el problema de ordenación de un array deelementos en este caso.

Introducción:

Este guión está estructurado en dos partes. En la primera, en la que utilizamos el algoritmo de ordenación por mezcla o más conocido como mergesort, enesta parte se realizará el análisis para la determinar los umbrales en forma teórica, híbrida y por tanteos o empírica.
En la segunda, se implementará el algoritmo de ordenación quicksort, estealgoritmo será implementado con tres alternativas ya que tendremos diferentes formas de escoger el pivote, y se realizará el análisis de eficiencia teórico, empírico y híbrido, así como la determinación delos umbrales.


Algoritmo: Mergesort

Principio:

El método de ordenación por mezcla o Mergesort, es un método basado en la técnica
Divide y Vencerás para realizar la ordenación de un vector. Suestrategia, es sencilla y puesto que se basa en la técnica de divide y vencerás, podemos distinguir tres etapas diferenciadas :
1. Debemos descomponer el problema original en subproblemas de menortamaño y del mismo tipo.
2. Esta operación debemos realizarla hasta llegar a un caso en el cual el problema sea lo suficientemente pequeño como para poder resolverlo de manera directa, esto es lo queconocemos como caso base.
3. Por último hay que combinar todos los subproblemas para obtener lo que será nuestra solución final del problema, esta fase será la mas costosa del algoritmo.Eficiencia Teórica:

Determinar la eficiencia de una algoritmo mediante un enfoque teórico ( o a priori) consiste en determinar matemáticamente la cantidad de recursos necesarios...