166 Ordenamiento, Búsqueda e Intercalación 7.1.6 Cantidad de comparaciones y operaciones efectuadas Cada partición de un arreglo de n componentes se realiza en a lo sumo n comparaciones e intercambios, dado que el arreglo se recorre una sola vez. En la segunda etapa, la partición de dos arreglos cuya suma de longitudes es n, requiere también una cantidad de operaciones del orden de n.¿Cuántas particiones son necesarias para ordenar el arreglo? Vamos a hacer un razonamiento muy simplificado, suponiendo que n es una potencia entera de 2, n=2 elevado k, p. ej. 2 elevado a 3 = 8 ó 2 elevado a 16 = 65536. Suponemos además que en cada partición el arreglo queda dividido en dos trozos de igual longitud. (arreglo original) ........ 2 elevado a 3 = 8 1a. partición .... | .... 2 x 2 elevado a 2 = 8 2a. partición .. | .. | .. | .. 4 x 2 elevado a 1 = 8 3a. partición . | . | . | . | . | . | . | . 8 x 2 elevado a 0 = 8 (arreglo ordenado) El esquema muestra que en cada partición, la longitud de los subarreglos se divide por 2, y esto lleva, considerando el conjunto de todos los subarreglos, a tener que efectuar k particiones, de n operaciones cada una para llegar a arreglos de una sola componente. Ahora bien, por definición de logaritmo, k = log2 n, por lo tanto, la cantidad de operaciones, donde cada una mueve n elementos, es del orden de n log2 n. Ejemplos de ejecución A modo de ilustración, se presentan los tiempos empleados por una PC corriente para ordenar 100000 enteros generados al azar, empleando programas codificados en Fortran basados en los algoritmos del presente capítulo. Método de selección: 53 segundos Método de la burbuja: 83 segundos Método de inserción: 54 segundos Método Quick sort: 1 segundo Al margen de alguna diferencia entre los tres primeros algoritmos, que puede estar relacionada con los datos, se nota claramente la enorme diferencia de velocidad que se obtiene con el método quick sort, la cual, según se probó, es válida para un caso general. No obstante, si hay que ordenar pequeñas cantidades de datos, o en ciertos casos particulares en que los datos ya están parcialmente ordenados, los tres primeros algoritmos pueden todavía lograr alguna ventaja.