Unidad 1: Análisis de algoritmos

La presente sección está orientada al estudio de las técnicas de análisis de algoritmos, al estudio de la recursividad y al desarrollo de habilidades en el uso de la programación recursiva.

Contenidos:

1. Tipos abstractos de datos y algoritmos correctos
2. Análisis de algoritmos.

1.1. Tipos abstractos de datos y algoritmos correctos

La abstracción de datos es un tipo especial de abstracción que involucra una descripción abstracta o lógica de los datos y de las operaciones definidas para un sistema programado. Según G. Heileman [Heil-98], "el uso de la abstracción de datos durante el desarrollo de software permite al diseñador concentrarse en cómo son usados los datos en el sistema para resolver el problema que le ocupa, sin tener que preocuparse de cómo los datos son representados y tratados en la memoria de la computadora".

La especificación de los algoritmos del curso se realiza según la técnica de desarrollo de sistemas de objetos (TDSO) de I. Besembel en [Bes-95], que está basada en el método deductivo MEDEE [Duf-88] y en la técnica OMT [RBP-91]. La solución de los problemas se hace por refinamientos sucesivos e incluye los enunciados de solución del problema, acompañados de la especificación y de la implementación de los tipos de datos utilizados basados en la abstracción de datos y en la orientación por objetos.

Un tipo de dato T se define como una clase de valores y una colección de operaciones sobre estos valores.

Si las propiedades de esas operaciones son especificadas solamente con axiomas, entonces T es un tipo abstracto de datos (TAD) o una abstracción de datos. Una implantación correcta del TAD cumple con todos los axiomas especificados para él. Un TAD es una entidad matemática definida por su estructura y sus operaciones, que se basa en la separación clara entre su implantación y el uso del TAD a través de su interfaz. Un TAD tiene una interfaz y una o varias implantaciones. La definición de un TAD consta de: Especificación e implantación.

Ejemplo: el tipo Entero es una entidad con sus operaciones de adición, substracción, negación, multiplicación, división y comparaciones.

El uso del TAD, por parte de los usuarios o programadores, es independiente de la implantación de sus operaciones. El desarrollador del TAD es libre de escoger o experimentar con las alternativas de implantación posibles, lo que es importante es que el resultado obtenido sea el correcto. La especificación formal de un TAD es la acción de determinar o explicar en términos formales o matemáticos el TAD.

La especificación por axiomas algebraicos para el tipo T se compone de una especificación sintáctica y una especificación semántica. La sintáctica define los nombres, dominios y rangos de las operaciones sobre T. La semántica se compone de un conjunto de axiomas en forma de ecuaciones, que dice como opera cada una de las operaciones especificadas sobre las otras. La implementación se compone de: una representación que especifica como los valores del TAD serán almacenados en la memoria, es decir su estructura de datos, y los algoritmos que especifican cómo será usada y manipulada la estructura de datos, es decir las operaciones del TAD.

TAD:

• Especificación: Sintáctica y semántica
• Implementación: Estructura de datos y algoritmos

El acceso al TAD es hecho a través de su interfaz, que es visible para los que la usan. La implementación del TAD es invisible para el usuario y es visible para el que la desarrolló.

Algoritmo: es cualquier secuencia de pasos bien definidos que toma
algún conjunto de valores de entrada y produce algún conjunto de valores
como salida. (al-Khowârizmi, matemático persa, siglo IX)

Un algoritmo para un problema es un procedimiento paso a paso que toma cualquier instancia del problema y produce una respuesta correcta.

El estudio de la corrección de algoritmos se conoce como semántica axiomática, según Floyd [Flo-67] y Hoare [Hoa-69]. Con ella se puede probar si un algoritmo es o no correcto de forma rigurosa, como probar un teorema en lógica. Ya que la semántica axiomática es objeto de un curso completo, aquí se utiliza un enfoque menos riguroso que es compatible con ella y que es apropiado para el entendimiento, comparación y desarrollo de los algoritmos.
¿Por qué estudiar si un algoritmo es correcto?

• Porque hay algoritmos tan misteriosos que desafían la intuición.
• Porque cada algoritmo depende de las propiedades específicas del problema dado y su corrección debe basarse en la estrategia utilizada para lo colocación de dichas propiedades y hacer que el algoritmo trabaje.
  

Probar la corrección de un algoritmo es revelar la estrategia de inclusión de las propiedades del problema, por medio de una comparación con otros algoritmos o en el desarrollo de nuevos algoritmos.

Un problema se especifica mediante la descripción de la forma de dichos parámetros y la pregunta que se realiza acerca de ellos.

Eo: Encontrar una solución programada satisfactoria para el problema elemental de reducir una fracción dada a sus términos más pequeños.
2/3 en vez de 20/30 , 4/6 , 200/300 , 178468/267702

Una instancia de un problema es una asignación de valores a sus parámetros. Un algoritmo es correcto si se garantiza que producirá una respuesta correcta para cualquier instancia del problema. El problema equivalente al del enunciado cero (Eo) se describe en E1.

E1: Encontrar el máximo común divisor (mcd) de un numerador y denominador dado.

Solución: Dividir la fracción entre el mcd del numerador y del denominador.

La especificación de los problemas se basa en dos expresiones lógicas o condiciones: precondiciones y postcondiciones. La precondición enuncia lo que será cierto inicialmente. La postcondición determina lo verdadero para el resultado. Para el ejemplo 1 de la reducción de la fracción:

pre: numerador y denominador son enteros positivos y no nulos.
existe n, d / n, d pertenecen a los Enteros y n, d > 0
pos: la fracción está reducida a sus mínimos elementos.
n', d' pertenecen a los Enteros y n' < = n y d' < = d

El enunciado E1 se puede refinar con el enunciado E2 dado a continuación.

E2: Solución programada del ejemplo 1 por el método de la fuerza bruta. Comienza con el menor de los dos números y prueba cada entero decrementado en 1, hasta encontrar el que divide a ambos, numerador y denominador.

E3:

Modelo de memoria de la computadora

Recordemos que la memoria de la computadora está organizada en dos partes: la principal (MP) y la secundaria (MS). La MP tiene acceso directo y es mucho más rápida que la MS, que corresponde a las unidades de disco y cinta. Las estructuras de datos que se mantienen y manejas en MP se denominan estructuras de datos internas y las estructuras de datos externas son las que se mantienen en MS. Asimismo, las estructuras de datos pueden ser: estáticas o dinámicas. Las estáticas son aquellas a las que se le asigna una cantidad fija de memoria a tiempo de compilación, como por ejemplo los arreglos. Las dinámicas son aquellas que no tienen esa cantidad fija, sino que varian en tamaño durante la ejecución del programa, como por ejemplo las listas enlazadas. En este último caso se utiliza la asignación dinámica de memoria para aquellos problemas donde no se conoce de antemano la cantidad de memoria necesaria para la estructura de datos.

El modelo lógico de la MP es un arreglo unidimensional de bytes dividido en tres partes: la memoria estática, la memoria libre y la pila de ejecución. En la memoria estática, ubicada en la parte alta de la MP, se colocan las estructuras estáticas, en la memoria libre las estructuras de datos dinámicas y en la pila de ejecución, ubicada en la parte baja de la MP, se mantienen los registros de activación. Estos últimos contienen las variables declaradas en el subprograma y una copia de o una referencia a los parámetros que usa el subprograma. La memoria libre crece hacia la parte baja de la MP y la pila de ejecución crece hacia la parte alta de la MP, por ello se pueden producir errores si:

1. demasiada memoria es asignada dinámicamente sin ser devuelta, o
2. se invocan demasiados subprogramas (se crean demasiados registros de activación).

El manejo de la memoria libre depende del enfoque que utilice el lenguaje de programación, el cual puede ser explícito o implícito. En el primero, el programador es responsable de devolver la memoria solicitada que ya no necesita, y en el segundo, el sistema es responsable de dicha actividad. Los lenguajes que soportan el enfoque implícito son aquellos que poseen el recolector de basura.

Recursividad y programación recursiva

La recursividad es una técnica fundamental en el diseño de algoritmos eficientes, que está basada en la solución de versiones más pequeñas del problema, para obtener la solución general del mismo. Una instancia del problema se soluciona según la solución de una o más instancias diferentes y más pequeñas que ella. Un programa recursivo es aquel que se invoca a sí mismo en al menos una de sus instrucciones. Todo programa recursivo debe tener una condición de finalización. Para probar la corrección de los algoritmos recursivos se utiliza la inducción sobre el tamaño de las instancias.

Ejemplo: Calcular n! = 1 si n = 0, n! = n (n - 1)! si n > 0

Un algoritmo recursivo que calcula el factorial de un número positivo se muestra a continuación. La complejidad de este algoritmo depende del valor de n, ya que la función se llama a sí misma n veces.

No todos los ambientes de programación proveen las facilidades necesarias para la recursión y adicionalmente, a veces su uso es una fuente de ineficiencia inaceptable. Por lo cual se prefiere eliminar la recursión. Para ello, se sustituye la llamada recursiva por un lazo, donde se incluyen algunas asignaciones para recolocar los parámetros dirigidos a la función.

Remover la recursión es complicado cuando existe más de una llamada recursiva, pero una vez hecha ésta, la versión del algoritmo es siempre más eficiente.

E2: Algoritmo Euclidiano: El método de Euclides se basa en que si n > d, entonces el mcd de n y d es el mismo de d y n-d. Se aplica esta regla sucesivamente, restando los múltiplos de d y n, hasta tener un número menor que d y este número es exactamente igual al resto de n dividido por d.

Eliminando la recursión de la función mcd( ) del enunciado E2 se obtiene E3.

1.2. Análisis de algoritmos

La eficiencia de un programa tiene dos ingredientes fundamentales: espacio y tiempo. La eficiencia en espacio es una medida de la cantidad de memoria requerida por un programa. La eficiencia en tiempo se mide en términos de la cantidad de tiempo de ejecución del programa. Ambas dependen del tipo de computador y compilador, por lo que no se estudiará aquí la eficiencia de los programas, sino la eficiencia de los algoritmos. Asimismo, este análisis dependerá de si trabajamos con máquinas de un solo procesador o de varios de ellos. Centraremos nuestra atención en los algoritmos para máquinas de un solo procesador que ejecutan una instrucción luego de otra.

La eficiencia de los algoritmos está basada en una operación característica que el algoritmo repite y que define su complejidad en Tiempo (T(n)).

T(n) es el número de operaciones características que el algoritmo desarrolla para una entrada N dada.

El máximo tiempo de ejecución de un algoritmo para todas las instancias de tamaño N, se denomina la complejidad en tiempo para el peor caso W(n). Asimismo, la complejidad promedio en tiempo es A(n), donde pj es la probabilidad de que esta instancia ocurra.

W(n) = MAX _{1 <= j <= n} T _j(n)
A(n) = Sumatoria con j = 1 hasta k ( p_j T_j(n) )

Normalmente se tendrán muchos algoritmos diferentes para resolver un mismo problema, por lo que debe existir un criterio para seleccionar el mejor. El interés principal del análisis de algoritmos radica en saber cómo crece el tiempo de ejecución, cuando el tamaño de la entrada crece. Esto es la eficiencia asintótica del algoritmo.
La notación asintótica se describe por medio de una función cuyo dominio es los números naturales (N). Se consideran las funciones asintóticamente no negativas.

Notación O, límite asintótico superior O(g(n)) = { f(n) / existen las constantes positivas c y n_o / 0 <= f(n) <= c g(n) para todo n >= n_o}, tanto f(n) como g(n) son de Z⁺ --> R⁺.

Ejemplo: an² + bn + c con a > 0 tiene O(n²)

Notación Omega grande, sean dos funciones f(n) y g(n) de Z⁺ --> R⁺. Se dice que f(n) es omega grande de g(n) si existen las constantes positivas c y n_o tales que f(n) >= c g(n) para todo n >= n_o.

Para cualesquiera de las dos funciones f(n) y g(n) definidas anteriormente se tiene que f(n) = Omega grande( g(n) ) si y sólo si g(n) = O( f(n) ).

Notación Theta grande, sean dos funciones f(n) y g(n) de Z⁺ --> R⁺. Se dice que f(n) es theta grande de g(n) si existen las constantes positivas c1, c2 y n_o tales que c1 g(n) >= f(n) >= c2 g(n) para todo n >= n_o.

Un ejemplo de algunas de las funciones más comunes en análisis de algoritmos son:

La mejor técnica para diferenciar la eficiencia de los algoritmos es el estudio de los órdenes de complejidad. El orden de complejidad se expresa generalmente en términos de la cantidad de datos procesados por el programa, denominada n, que puede ser el tamaño dado o estimado.

Ejemplo: Un algoritmo que procese un vector V(n) tendrá un orden de complejidad de n, ya que si n crece, en esa misma proporción crece el orden de complejidad del algoritmo.

La cantidad de tiempo de procesamiento de un algoritmo (T(n)), por lo general viene dado en función de n, y puede expresarse según los casos típicos de ese n, caso promedio A(n), o basándose en casos extremos no deseables, como el peor de los casos W(n).

El orden de complejidad se define como una función que domina la ecuación que expresa en forma exacta el tiempo de ejecución del programa.

g(x) domina a f(x), si dada una constante C cualquiera, C*g(x) >= f(x) para todo x
g(x) domina asintóticamente a f(x), si g(x) domina a f(x) para valores muy grandes de x.

f(n) = n² + 5n + 100, y g(n) = n² entonces g(n) domina a f(n)

El orden de complejidad se denota con una o mayúscula, O(g(n)) , O(n²), O(n). Un orden O(n) indica que el tiempo de ejecución decrece suavemente en proporción al decrecimiento de n. Aunque dos algoritmos tengan el mismo orden O(n), ellos pueden tener diferentes tiempos de ejecución para iguales valores de n. Reglas para determinar el orden de complejidad:
1.- O(C*g) = O(g)
2.- O(f * g) = O(f) * O(g) y O(f/g) = O(f) / O(g)
3.- O(f+g) = función dominante entre O(f) y O(g)

Ejemplos: O(2456 * n) = O(n)
O((20 * n) * n) = O(20 * n) * O(n) = O(n²)

Algunas de las funciones de dominación más comunes son:

Un algoritmo de O(1) tiene complejidad constante y por ello son los más eficientes y los preferidos. La mayoría de los programas tienen complejidad polinomial O(n^a), donde n es la variable y a es una constante mayor que 1. O(n), O(n²), O(n³), O(log n). La complejidad no polinomial (NP) o exponencial es aquella que tiene un orden mayor que la polinomial. Ejemplo: La complejidad exponencial O(aⁿ). Los nombres de las más usadas:

log n complejidad logarítmica (log₂ n = lg n)
n complejidad lineal
n ² complejidad cuadrática
n ³ complejidad cúbica
2n complejidad exponencial

Una comparación entre diferentes complejidades se muestra en la figura 1.1.

Los algoritmos sin lazos y sin recursión tienen complejidad constante. La determinación del orden de complejidad de un algoritmo se inicia por los lazos y las recursiones. Los lazos anidados tendrán complejidad polinómica. La correspondencia entre la estructura de programación y el orden de complejidad puede observarse en la figura 1.2.

Ejemplo: [ [ m( i, j ) = 0 ] j = 1, n] i = 1, n tiene O(n²)
[ a = a + bi ] i = 3,8 tiene O(1)

Técnicas algorítmicas:

1. Algoritmos de fuerza bruta: son los algoritmos que resuelven el problema con la estrategia más obvia de solución, que no siempre es la mejor según el número de operaciones que se requieren.
2. Algoritmos divide-y-vencerás: es una técnica descendente que resuelve el problema descomponiendolo en varios subproblemas, no necesariamente similares al original, pero que tienen un tamaño más pequeño. Cada subproblema se resuelve separadamente y luego se combinan los resultados para obtener la solución al problema original. Estos algoritmos tienen tiempos de ejecución que se describen con recurrencias de la forma T(n) = a T(n/b) + f(n), donde a y b son constantes.
3. Programación dinámica: son similares al anterior, sólo que la solución obtenida de los subproblemas más pequeños se utilizan para resolver los subproblemas más grandes. Por ello es una técnica ascendente, que se inicia con la resolución de subproblemas más pequeños, para guardar esos resultados y utilizarlos en la resolución de los subproblemas de niveles superiores. Sólo es posible utilizarla cuando existe un cierto grado de solapamiento entre los subproblemas.
4. Algoritmos voraces: seleccionan la opción de solución (solución local) que tenga un costo menor en la etapa de solución en la que se encuentran, sin considerar si esa opción es parte de una solución óptima para el problema completo (solución global).
5. Algoritmos probabilistas: su entrada depende también de un generador de números aleatorios, para evitar que se presente el peor de los casos en las entradas del algoritmo.

Recurrencias:

El tiempo de ejecución de los algoritmos de tipo divide y vencerás viene determinado por el tamaño y el número de subproblemas, así como por el costo de la composición de las subsoluciones.

Recurrencias básicas:

1. T( n ) = T( n - 1 ) + n, para n >= 2 con T( 1 ) = 1.
   Solución: T( n ) es del orden de O(n²)
2. T( n ) = 2 T( n - 1 ) + 1, para n > 1 y T( 1 ) = 1.
   Solución: T( n ) es 2ⁿ - 1 con n >= 1
   
3. T( n ) = T( n/2 ) + 1 para n >= 2 con T( 1 ) = 0.
   Solución: T( n ) es del orden de lg n, suponiendo n de la forma 2^k. T( n ) = Theta grande( lg n ).
   
4. T( n ) = T( n/2 ) + n para n >= 2 con T( 1 ) = 0.
   Solución: T( n ) es del orden de 2n, suponiendo n de la forma 2^k. T( n ) = Theta grande( n ).
   
5. T( n ) = 2 T( n/2 ) + n para n >= 2 con T( 1 ) = 0.
   Solución: T( n ) es del orden de n lg n, suponiendo n de la forma 2^k. T( n ) = Theta grande( n lg n ).
   
6. T( n ) = 2 T( n/2 ) + 1 para n >= 2 con T( 1 ) =0.
   Solución: T( n ) es del orden de 2n. T( n ) = Theta grande( n ).
   

Pasos generales para el cálculo de recurrencias

1. Calcular los primeros valores de la recurrencia.
2. Buscar una regularidad
3. Inventar una forma general adecuada
4. Demostrar por inducción matemática que esta forma es correcta.

Ordenamiento:

Ordenar una colección de elementos en forma creciente o decreciente (ascendente o descendente). Puede ser: interno o externo, según sea en MP o en MS. Formulación del problema:

E0: Se tiene una colección de n elementos A1, A2, ..., An, donde cada Ai tiene una clave asociada clave[Ai]. Se supone que existe una relación de orden total sobre las claves, tal que para cualquier tripleta de valores de la clave, clave[Ai], clave[Aj] y clave[Ak] se cumple:

1. exactamente una de las posibilidades: clave[Ai] < clave[Aj], clave[Ai] = clave[Aj] o clave[Ai] > clave[Aj]; y
2. si clave[Ai] < clave[Aj] y clave[Aj] < clave[Ak] entonces clave[Ai] < clave[Ak]

El problema de ordenamiento consiste en reorganizar la colección A de forma que sus claves formen una secuencia creciente ( clave[A1] <= clave[A2] <= ... <= clave[An] )o decreciente ( clave[A1] >= clave[A2] >= ... >= clave[An] ).

Ordenamiento por inserción: Método usado cuando se ordenan las cartas de la baraja, Se suponen los n elementos iniciales ya ordenados, el n+1 elemento se inserta simplemente moviendo los elementos mayores que él una posición a la derecha e insertando el elemento nuevo en la posición vacante.

void insercion(TipoEle A[], int n)
{ int i, j;
  TipoEle v;
  for (i = 2; i <= n; i++)
  {	v = A[i]; 
    j = i; 
  	while ( A[j-1] > v )
	{ A[j] = A[j-1]; 
      j--;
    }
    A[j] = v;
  }
} 

Análisis del algoritmo de ordenamiento por inserción: Número de comparaciones: n (n - 1) / 2 lo que implica un T(n) = Theta grande (n²). La ordenación por inserción utiliza aproximadamente n²/4 comparaciones y n²/8 intercambios en el caso medio y dos veces más en el peor de los casos. La ordenación por inserción es lineal para los archivos casi ordenados.

Ordenamiento por selección: Se busca el elemento más pequeño del arreglo y se intercambia con el que está en la primera posición; luego se busca el segundo más pequeño y se intercambia con el que está en segunda posición; asi sucesivamente.

void   intercambio(TipoEle A[ ], int  i, int j)
{ TipoEle t;
  t = A[i];
  A[i] = A[j];
  A[j] = t; 
}   
void seleccion(TipoEle A[], int n)
{ int i, j, min = 1;
  for (i = 1; i < N; i++)
  {	min = i;
  	for ( j = i+1; j <= N; j++)
        if ( A[j] < A[min]) 	min = j;
    intercambio(A, min, j);
  }
} 

Análisis del algoritmo de ordenamiento por selección: La ordenación por selección utiliza aproximadamente n²/2 comparaciones y n intercambios, por lo cual T(n) = O( n² ).

Método de la burbuja: Se comparan los elementos adyacentes, intercambiandolos cuando el elemento n sea mayor al elemento n + 1.

void burbuja(TipoEle A[ ], int n)
{ int i, j;
  for (i = n; i >= 1; i--) 
      for (j = 2; j <= i; j++)
      { if (A[j-1] > A[j])	intercambio(A, j-1, j);
      }
} 

Análisis: La ordenación de burbuja tanto en el caso medio como en el peor de los casos utiliza aproximadamente n²/2 comparaciones y n²/2 intercambios, por lo cual T(n) = O( n² ).

Método Shell u ordenamiento por incrementos decrecientes: Es una generalización del ordenamiento por inserción donde se gana rápidez al permitir intercambios entre elementos que se encuentran muy alejados. La idea es reorganizar la secuencia de datos para que cumpla con la propiedad siguiente: si se toman todos los elementos separados a una distancia h, se obtiene una secuencia ordenada. Se dice que la secuencia h-ordenada está constituida por h secuencias ordenadas independendientes, pero entrelazadas entre sí. Se utiliza una serie decreciente h que termine en 1.

void OrdShell(TipoEle A[], int n)
{  int i, j, h;
   TipoEle v;
   for ( h = 1; h <= n/9; h = 3*h + 1 );
   for ( ; h > 0; h/= 3 )
     for ( i = h + 1; i <= N; i+= 1 )
     {  v = A[i]; 
        j = i; 
        while ( j > h && A[j-h] > v )
        {  A[j] = A[j-1]; 
           j -= h;
        }
        A[j] = v;
     }
} 

Análisis: Esta sucesión de incrementos es fácil de utilizar y conduce a una ordenación eficaz. Hay otras muchas sucesiones que conducen a ordenaciones mejores. Es difícil mejorar el programa anterior en más de un 20%, incluso para n grande. Existen sucesiones desfavorables como por ejemplo: 64, 32, 16, 8, 4, 2, 1, donde sólo se comparan elementos en posiciones impares cuando h=1. Nadie ha sido capaz de analizar el algoritmo, por lo que es difícil evaluar analíticamente los diferentes incrementos y su comparación con otros métodos, en consecuencia no se conoce su forma funcional del tiempo de ejecución. Para la sucesión de incrementos anterior se tiene un T(n) = n( log n)² y n^1,25. La ordenación de Shell nunca hace más de n^3/2 comparaciones (para los incrementos 1,2,13, 40.....)

Usando la secuencia de Hirbbard ( 2k - 1 ), el tiempo en el peor de los casos W(n) = Theta grande( n^3/2 ) y el tiempo en el caso promedio A(n) = Theta grande( n^5/4).

Usando la secuencia de Sedgewick ( 9 *4ⁱ - 9*2ⁱ + 1 ) o ( 4i - 3 * 2ⁱ + 1 ), el tiempo en el peor de los casos W(n) = Theta grande( n^4/3) y el tiempo en el caso promedio A(n) = ( n^7/6).

Ordenamiento por mezclas sucesivas (merge): Se aplica la técnica divide-y-vencerás, dividiendo la secuencia de datos en dos subsecuencias hasta que las subsecuencias tengan un único elemento, luego se ordenan mezclando dos subsecuencias ordenadas en una secuencia ordenada, en forma sucesiva hasta obtener una secuencia única ya ordenada. Si n = 1 solo hay un elemento por ordenar, sino se hace una ordenación de mezcla de la primera mitad del arreglo con la segunda mitad. Las dos mitades se ordenan de igual forma. Ejemplo: Se tiene un arreglo de 8 elementos, se ordenan los 4 elementos de cada arreglo y luego se mezclan. El arreglo de 4 elementos, se ordenan los 2 elementos de cada arreglo y luego se mezclan. El arreglo de 2 elementos, como cada arreglo sólo tiene n = 1 elemento, solo se mezclan.

void ordenarMezcla(TipoEle A[], int izq, int der)
{  if ( izq < der )
   {  centro = ( izq + der ) % 2; 
      ordenarMezcla( A, izq, centro );
      ordenarMezcla( A, centro+1, der);
      intercalar( A, izq, centro, der ); 
   }
}
void intercalar(TipoEle A[], int a, int c, int b )
{  k = 0;
   i = a;
   j = c + 1;
   n = b - a;
   while ( i < c + 1 ) && ( j < b + 1 )
   {  if ( A[i] < A[j] )
      {  B[k] = A[i];
         i = i + 1;
      }
      else
      {  B[k] = A[j];
         j = j + 1;
      }
      k = k + 1;
   };
   while ( i < c + 1 )
   {  B[k] = A[i];
      i++;
      k++;
   };
   while ( j < b + 1 )
   {  B[k] = A[j];
      j++;
      k++;
   };
   i = a;
   for ( k = 0; k < n; i++ )
   {  A[i] = B[k];
      i++;
   };
};

Análisis: La relación de recurrencia del algoritmo es T(1) = 1, T(n) = 2 T(n/2) + n, cuya solución es T(n) = n lg n.

Método rápido (quicksort): Fue inventado en 1960 por C.A.R Hoare y es el método de ordenamiento más utilizado, dado que es fácil de implementar y proporciona buenos resultados generales. Utiliza solamente n lg n comparaciones en promedio para ordenar n elementos y tiene un bucle interno extremadamente corto. Usa la técnica divide y vencerás, dividiendo la secuencia de datos en dos partes y ordenando cada parte separadamente. El punto exacto de la partición depende de la secuencia.

void quicksort(TipoEle A[], int izq, int der)
{  int i;
   if ( izq < der ) 
   {  i = particion( A, izq, der );
      quicksort( A, izq, i - 1);
      quicksort( A, i + 1, der);
   }
}

Lo esencial de este algoritmo es el método partición, que debe reordenar el arreglo para que se verifiquen las siguientes condiciones:

void quicksort(TipoEle A[], int izq, int der)
{  int i, j;
   TipoEle piv;
   if ( izq < der ) 
   {  piv = A[der]; 
      i = izq - 1; 
      j = der;
      while( A[++i] < piv );
         while( A[--j] > piv );
            if ( i >= j ) break;
            intercambio( A, i, j);
   }
   quicksort( A, izq, i - 1 );
   quicksort( A, i + 1, der);
}

Rendimiento del Quicksort: Si se supone que en cada etapa se divide exactamente por la mitad cada arreglo, se diría que el método de ordenamiento satisface la recurrencia de divide y vencerás. T(n) = 2T(n/2) * n cuya solución es n lg n. Este método se puede mejorar si se elimina la recursión, no se hacen las llamadas recursivas en secuencias pequeñas y se escoge el elemento pivote aleatoriamente. Entre sus desventajas se encuentran: en el peor de los casos necesita aproximadamente n² operaciones y es frágil, ya que si durante la implementación pasa un error puede causar serios daños.

Ir al programa