Universidad
Tecnológica
Nacional
TFI
Algoritmos y Estructura de Datos
Presentan:
Ordoñez Nadra, Rodrigo (58366)
Nicoloff, Máximo (58436)
Orellana, Ignacio (57995)
Profesores:
Cruz Pedro Alejandro
Valla Sandra Fabiana
Fecha de Presentación:
15/10/2023
Índice
Análisis Algorítmico………………………………………………………………………….2
Definición de Algoritmo
Definición de Análisis Algorítmico
Orden de un Algoritmo……………………………………………………………………...5
Análisis de los Métodos de Ordenamiento……………………………………………….6
Método de la Burbuja o Bubblesort
Método de la Baraja, Inserción o Insertionsort
Método de Selección, Simple o Selectionsort
Método Rápido o Quicksort
Método de Mezcla o Mergesort
Diferencia entre los Métodos de Ordenamiento………………………………………..21
Eficiencia
Uso de Memoria
Adaptabilidad
Bibliografía………………………………………………………………………………….23
1
Análisis Algorítmico
Definición de Algoritmo:
Un algoritmo es un conjunto de instrucciones o pasos finitos y bien definidos que se
utilizan para realizar una tarea específica o resolver un problema.
Se entiende por problema a toda situación novedosa que requiere de procesos de
razonamientos más o menos complejos para resolverse, teniendo una situación
inicial, un objetivo a alcanzar y restricciones o pautas respecto de métodos,
actividades, tipos de operaciones, etc., sobre los cuales hay acuerdos previos
(definición dada por la profesora de la U.B.A. Herminia Azinián).
Este conjunto de instrucciones forma una secuencia lógica y sistemática que toma
una entrada (input), realiza operaciones precisas en esa entrada y genera una
salida (output) deseada.
Según Donald Knuth (científico de la computación), para que un algoritmo sea
considerado informático, debe ser:
● Secuencial: pasos dispuestos en un orden definido, siguiendo un flujo lógico y
secuencial.
● Definido: las operaciones que se deben realizar deben estar especificadas de
manera rigurosa y sin ambigüedades.
● General: debe ser aplicable a la generalidad de los casos que pueden surgir
dentro del ámbito de validez de esa solución.
● Finito: debe finalizar después de un número finito de pasos
Definición de Análisis Algoritmo:
El análisis algorítmico es un proceso esencial en la ciencia de la computación que
se centra en evaluar, comparar y entender el rendimiento de los algoritmos
utilizados para resolver problemas computacionales. Este análisis busca
proporcionar una visión teórica de los recursos que un algoritmo necesita para llevar
a cabo una tarea específica.
Esto se hace para responder preguntas clave, como:
● ¿Cuánto tiempo (en términos de tiempo de ejecución) lleva un algoritmo para
resolver el problema?
● ¿Cuánta memoria o espacio de almacenamiento requiere el algoritmo?
2
● ¿Cómo se comporta el algoritmo a medida que aumenta el tamaño de la
entrada?
Tipos de análisis para evaluar cómo se comporta un algoritmo en diversos
escenarios:
1. Peor Caso (Worst-Case): implica evaluar el tiempo de ejecución o la
eficiencia de un algoritmo en la situación más desfavorable posible. Es decir,
se considera cuánto tiempo podría llevar el algoritmo si todo sale mal y se
requieren la mayoría de los recursos posibles. El análisis del peor caso
proporciona una cota superior para el tiempo de ejecución del algoritmo, lo
que significa que el algoritmo nunca tomará más tiempo que el peor caso.
Esto es útil para garantizar que el algoritmo funcione dentro de límites
aceptables, incluso en situaciones adversas.
a. Por ejemplo: En un algoritmo de ordenamiento, el peor caso podría ser
cuando la lista está ordenada en orden inverso, lo que requiere el
mayor número de comparaciones y movimientos de elementos.
2. Caso Medio (Average-Case): implica evaluar el tiempo de ejecución promedio
esperado de un algoritmo cuando se consideran todas las posibles instancias
del problema. Este tipo de análisis puede requerir establecer una distribución
estadística de los casos de entrada y calcular el tiempo promedio en función
de esta distribución. Es útil cuando se espera que los datos de entrada sigan
una distribución probabilística específica.
a. Por ejemplo: En un algoritmo de búsqueda, se puede calcular el caso
medio considerando diferentes distribuciones de datos de entrada y la
3
probabilidad de que cada dato se encuentre en una posición
específica.
3. Mejor Caso (Best-Case): implica evaluar el tiempo de ejecución más rápido o
eficiente que un algoritmo podría lograr. Sin embargo, este tipo de análisis a
veces puede ser engañoso, ya que generalmente se basa en suposiciones
optimistas y no refleja necesariamente el rendimiento real del algoritmo en
situaciones reales. Se utiliza principalmente para ilustrar un límite inferior en
la eficiencia de un algoritmo.
a. Por ejemplo: En un algoritmo de búsqueda lineal, el mejor caso sería
cuando el elemento que se busca está en la primera posición de la
lista. En este caso, el algoritmo podría encontrar el elemento en el
primer paso.
Usualmente, los recursos a los cuales se hace referencia son el tiempo (complejidad
temporal) y el almacenamiento (complejidad espacial). Mientras que la complejidad
temporal involucra determinar una función que relaciona la longitud o el tamaño de
la entrada del algoritmo con el número de pasos que realiza, la complejidad espacial
busca la cantidad de ubicaciones de almacenamiento que utiliza. Distintos
algoritmos pueden utilizarse para resolver un mismo problema y a su vez los
algoritmos pueden estudiarse de forma independiente del lenguaje de programación
a utilizar y de la máquina donde se ejecutará. Esto significa que se necesitan
técnicas que permitan comparar la eficiencia de los algoritmos antes de su
implementación.
Sin embargo, ¿para qué emplear tiempo en diseñar algoritmos eficientes si las
computadoras tienen cada vez más recursos computacionales?
Es importante entender que aunque las computadoras son cada vez más potentes,
los problemas que surgen también pueden volverse más complejos. Diseñar
algoritmos eficientes sigue siendo fundamental por varias razones:
➔ Economía de recursos: al usar algoritmos más eficientes, se pueden ahorrar
recursos como energía y espacio de almacenamiento, lo que puede ser
crucial en entornos empresariales y móviles.
➔ Tiempo de respuesta: los algoritmos eficientes permiten respuestas más
rápidas, lo que es esencial en aplicaciones en tiempo real como la
navegación GPS, la transmisión de video y los juegos.
4
➔ Escalabilidad: es la capacidad de un sistema para manejar un crecimiento en
el número de usuarios, la cantidad de datos o el volumen de operaciones sin
experimentar una degradación significativa del rendimiento. A medida que los
datos y las operaciones aumentan, los algoritmos eficientes siguen siendo
clave para garantizar un rendimiento adecuado. Esto es fundamental en
aplicaciones, páginas web y en la gestión de grandes conjuntos de datos.
Orden de un Algoritmo:
El orden de un algoritmo es una medida que se usa en la ingeniería del software
para ordenar los algoritmos del más eficiente al menos eficiente. Describe cómo
cambia el tiempo de ejecución o el uso de recursos (generalmente memoria) de un
algoritmo a medida que el tamaño de la entrada crece. En otras palabras, el orden
de un algoritmo es una manera de expresar su complejidad en términos de tiempo o
espacio.
La notación "Big O" (O grande) es una herramienta importante en el análisis
algorítmico para describir la eficiencia o complejidad temporal de un algoritmo en
términos de cómo crece en función del tamaño de la entrada. En otras palabras,
ayuda a entender cómo el tiempo de ejecución de un algoritmo se comporta a
medida que el problema se hace más grande. Se utiliza para dar una estimación del
peor caso (en términos de tiempo) que podría tomar el algoritmo. Se denota como
O(f(n)), donde "f(n)" es una función matemática que describe el crecimiento del
tiempo de ejecución en función del tamaño de la entrada, "n". Algunos ejemplos
comunes de notaciones "Big O" incluyen O(1) (constante), O(log n) (logarítmico),
O(n) (lineal), O(n log n) (n logarítmico), O(n²) (cuadrático), O(2ⁿ) (exponencial), entre
otros.
Ejemplo de su aplicación:
Supongamos que se está desarrollando un programa de búsqueda que debe
encontrar un elemento específico en una lista de “n” elementos. Hay dos algoritmos
diferentes para realizar esta tarea: el algoritmo A y el algoritmo B.
Algoritmo A: Recorre la lista elemento por elemento hasta encontrar el que se
busca.
Algoritmo B: Divide la lista por la mitad repetidamente hasta encontrar el elemento.
5
Para determinar cuál de estos algoritmos es más eficiente en términos de tiempo a
medida que la lista de elementos crece, se puede utilizar la notación "Big O". En
este caso:
Para el algoritmo A, el tiempo de ejecución podría ser proporcional a “n”, si tiene que
recorrer toda la lista. Por lo tanto, se escribiría como O(n).
Para el algoritmo B, el tiempo de ejecución es proporcional al número de veces que
puede dividir la lista por la mitad, lo cual se puede representar como O(log₂ 5).
El logaritmo en base 2 (logaritmo binario) se utiliza en este contexto porque cada
paso de la búsqueda binaria divide el conjunto de elementos en dos, y da como
resultado cuántas veces se puede dividir el número “n” en partes iguales hasta
llegar a 1. Entonces, el número de pasos que toma la búsqueda binaria crece de
manera logarítmica en relación con el tamaño de la lista.
En este ejemplo, a medida que la lista de elementos crece, el algoritmo B sería
mucho más rápido que el algoritmo A.
Por norma general, siempre se busca elegir los algoritmos con un orden menor,
para poder garantizar un rendimiento óptimo en una variedad de aplicaciones
informáticas.
Análisis de los métodos de ordenamiento:
Definición de métodos de ordenamiento de vectores:
Los métodos de ordenamiento de vectores son aquellas técnicas y algoritmos que
se utilizan para organizar los elementos de un vector (también llamado arreglo o
lista) en un orden específico, como de menor a mayor (ascendente) o de mayor a
menor (descendente). Estos métodos se aplican comúnmente en programación y
ciencia de la computación para facilitar la búsqueda y recuperación de datos, así
como para mejorar la eficiencia de las operaciones de procesamiento de datos.
Método de la Burbuja o Bubblesort:
Se parte de una lista de elementos desordenados:
6
Se seleccionan los primeros dos números y si no están ordenados (según el tipo de
orden elegido: ascendente o descendente) se intercambian los lugares:
Se repite el proceso con los siguientes dos números:
El proceso continúa hasta llegar al final:
Finalmente, el último número ya queda ordenado, por lo que en la siguiente iteración
ya no se evalúa, acortando el proceso:
7
En la tercera iteración no se evalúan los últimos dos valores:
La cuarta iteración finaliza sin que se haya realizado un intercambio, por lo que el
algoritmo termina y el resultado es la lista ordenada:
En cuanto a su codificación, el método se compone de los siguientes elementos:
Variables Utilizadas:
● Índice i: Esta variable se utiliza como índice para recorrer el arreglo.
Comenzamos desde el primer elemento (índice 0) y avanzamos, en cada
pasada, hasta el penúltimo elemento (índice n-2). El índice i nos permite
comparar elementos consecutivos en el arreglo.
● BANDERA b: La variable 'b' se utiliza como una bandera booleana para
determinar si se deben realizar más pasadas de ordenamiento. Inicialmente,
se establece en 1 para asegurarse de que se realice al menos una pasada
inicial.
● AUXILIAR aux: Esta variable se utiliza para realizar el intercambio de
elementos en el arreglo. Cuando encontramos dos elementos que están fuera
de orden, almacenamos temporalmente uno de ellos en 'aux' antes de
realizar el intercambio.
8
Ciclo do-while:
● El algoritmo utiliza un ciclo "do-while" para controlar las pasadas de
ordenamiento. La condición de repetición es que la bandera 'b' sea igual a 1.
Inicialmente, 'b' se establece en 1, por lo que el ciclo se ejecutará al menos
una vez.
Ciclo for:
● Dentro del ciclo "do-while", hay un ciclo "for" controlado por la variable 'i'. El
ciclo "for" recorre el arreglo desde el primer elemento hasta el penúltimo
elemento (índice en n-2). Esto se debe a que en cada iteración, comparamos
el elemento actual (en la posición 'i') con el siguiente elemento (en la posición
'i+1').
Condición if:
● Dentro del ciclo "for", hay una condición "if" que compara los elementos en
las posiciones 'i' e 'i+1'. Si estos elementos están en el orden incorrecto (es
decir, el elemento en 'i' es mayor/menor, según el ordenamiento que se
quiera hacer, que el elemento en 'i+1'), se realiza un intercambio.
Intercambio de elementos:
● El intercambio de elementos se realiza utilizando la variable 'aux'. El valor en
'aux' se establece en el elemento en la posición 'i', luego el valor en la
posición 'i' se actualiza con el elemento en 'i+1', y finalmente, el valor en 'i+1'
se actualiza con el valor en 'aux'. Esto asegura que los elementos estén
ordenados correctamente después de cada iteración.
Actualización de la bandera:
● Después de realizar el intercambio, la bandera 'b' se establece en 1
nuevamente. Esto garantiza que se realice al menos otra pasada si todavía
hay elementos fuera de orden.
Finalización del algoritmo:
● El ciclo "do-while" continúa ejecutándose mientras la bandera 'b' sea igual a
1. Una vez que no se realicen más intercambios durante una pasada
completa del ciclo "for", la bandera 'b' se establecerá en 0, y el algoritmo
concluirá, ya que se considera que el arreglo está ordenado.
9
Método de la Baraja o InsertionSort:
Se parte de una lista de elementos no ordenados:
Se selecciona el segundo valor como clave y se lo compara con los valores
ubicados a su izquierda. Si el valor es menor (suponiendo que se quiere ordenar de
forma descendente) entonces se inserta en el lugar correspondiente.
Se selecciona el siguiente número como clave y se repite el proceso para todos los
valores anteriores. En el siguiente caso la clave 4 se compara primero con 5 y luego
con 2. Al ser menor que el primer caso comparado y mayor que el segundo se lo
inserta entre ambos números.
Se selecciona la siguiente clave. Se sigue comparando con cada número a su
izquierda hasta encontrar uno que sea menor o llegar al principio de la lista.
10
Finalmente, se selecciona la última clave y se repite el proceso.
Al finalizar el algoritmo tenemos como resultado la lista ordenada.
En cuanto a su codificación, el método se compone de los siguientes elementos:
Variables Utilizadas:
● ÍNDICE i: Esta variable se utiliza como índice principal para recorrer el
arreglo. Comenzamos desde el segundo elemento (índice 1) y avanzamos
hasta el último elemento (índice n-1) en el arreglo. El índice i nos permite
seleccionar el elemento actual que queremos insertar en la parte ordenada.
● ÍNDICE j: La variable 'j' se utiliza como un índice secundario que siempre
estará una posición detrás de 'i' al comienzo, luego se irá decrementando. Se
lo usa para comparar el elemento en la posición 'j' con la 'CLAVE' y realizar
desplazamientos si es necesario.
● CLAVE: La variable 'CLAVE' almacena el valor del elemento en la posición 'i'.
Este valor se guarda temporalmente para poder realizar comparaciones con
elementos en la parte ordenada del arreglo.
11
Ciclo for:
● El algoritmo utiliza un ciclo "for" controlado por la variable 'i' para recorrer el
arreglo desde el segundo elemento (índice 1) hasta el último elemento (índice
n-1). Esto se debe a que queremos insertar el elemento en la posición 'i' en la
parte ordenada del arreglo.
Asignación de la CLAVE:
● En cada iteración del ciclo "for", la variable 'CLAVE' se asigna con el valor del
elemento en la posición 'i'. Esto se hace para que podamos comparar
'CLAVE' con los elementos en la parte ordenada del arreglo y decidir dónde
debe insertarse.
Ciclo while:
● Dentro del ciclo "for", hay un ciclo "while" que se utiliza para comparar
'CLAVE' con los elementos en la parte ordenada del arreglo. La condición de
repetición es que el índice 'j' sea mayor o igual a 0 (es decir, que sea una
posición válida) y que el elemento en la posición 'j' sea mayor (esto varía de
acuerdo al tipo de ordenamiento, sea ascendente o descendente, que se
quiera hacer) que 'CLAVE'.
Comparación y Desplazamiento:
● Si se cumplen ambas condiciones en el ciclo "while", se realiza un
desplazamiento hacia la derecha del elemento en la posición 'j' al espacio
siguiente (posición 'j+1'). Esto se hace para abrir espacio para el elemento
'CLAVE' que será insertado en la parte ordenada del arreglo.
Actualización de j:
● Luego de realizar un desplazamiento, se decrementa 'j' en 1 para que
podamos comparar 'CLAVE' con el siguiente elemento antecedente en el
arreglo.
Inserción de CLAVE:
● Cuando 'j' es menor que 0 o el elemento en la posición 'j' no es mayor que
'CLAVE' (vale decir, no se cumple la condición del anterior ciclo while) se
inserta el valor de 'CLAVE' en la posición 'j+1'. Esto coloca el elemento
'CLAVE' en su posición correcta en la parte ordenada del arreglo.
12
Finalización del algoritmo:
● El ciclo "for" continúa hasta que hayamos recorrido todos los elementos del
arreglo. En la primera vuelta del ciclo, solo se compara el elemento en 0 con
el elemento en 1 (clave). En la segunda vuelta, se compara el elemento en 1
con el elemento en 2 (clave), y luego el elemento en 0 con el elemento en 1
(por decremento de j). Y así sucesivamente (hasta terminar el ciclo for),
teniendo en cuenta las condiciones del ciclo while y todos los decrementos
que reciba j. Al final de la ejecución del algoritmo, el arreglo estará
completamente ordenado.
Método de Selección o SelectionSort:
Este método mejora el ordenamiento BubbleSort haciendo un sólo
intercambio por cada pasada a través de la lista. Para esto, se busca el
valor mayor/menor (según el tipo de ordenamiento) a medida que hace
una pasada y, después de completar la pasada, lo pone en la ubicación
correcta. Al igual que el BubbleSort, después de la primera pasada, el
ítem mayor está en la ubicación correcta. Después de la segunda pasada,
el siguiente mayor está en su ubicación. Este proceso continúa y requiere
n−1 pasadas para ordenar los n ítems, ya que el ítem final debe estar en
su lugar después de la (n−1)-ésima pasada. El resultado final es un
arreglo completamente ordenado.
13
En cuanto a su codificación, el método se compone de los siguientes elementos:
Variables Utilizadas:
● ÍNDICE i: la variable ‘i’ se utiliza como índice principal para recorrer el arreglo.
Comenzamos desde el primer elemento (índice 0) y avanzamos hasta el
penúltimo elemento (índice m-2) en el arreglo, pues se comparará el
elemento de la izquierda con el de la derecha, como en el BubbleSort. El
índice i nos permite seleccionar el elemento actual que se considerará como
el menor.
● ÍNDICE j: La variable 'j' se utiliza como un índice secundario para explorar los
elementos a la derecha del elemento en la posición 'i'. Se usa para comparar
el elemento en la posición 'j' con el elemento en la posición 'menor' y
determinar si es menor.
● MENOR/MAYOR (dependiendo del tipo de ordenamiento): suponiendo que
se quiere ordenar de manera ascendente, se utiliza la variable 'menor' para
almacenar la posición del elemento más pequeño encontrado hasta el
momento durante el proceso de selección.
14
● TEMP: La variable 'temp' se utiliza como almacenamiento temporal o auxiliar
para realizar las permutaciones entre el elemento en la posición 'i' y el
elemento en la posición 'menor'.
Ciclo For Externo:
● El algoritmo utiliza un ciclo "for" controlado por la variable 'i' para recorrer el
arreglo desde el primer elemento (índice 0) hasta el penúltimo elemento
(índice m-2). Esto se hace para seleccionar el elemento actual que se
considerará como el menor en la parte no ordenada del arreglo.
Asignación del Menor:
● En cada iteración del ciclo "for" externo, la variable 'menor' se inicializa con el
valor de 'i'. Esto se hace para indicar que el elemento en la posición 'i' es el
candidato a ser el menor en la parte no ordenada del arreglo.
Ciclo For Interno:
● Dentro del ciclo "for" externo, hay un segundo ciclo "for" controlado por la
variable 'j', que se utiliza para explorar los elementos a la derecha del
elemento en la posición 'i'. El objetivo es encontrar el elemento más pequeño
en la parte no ordenada del arreglo.
Comparación y Actualización del Menor:
● Si se encuentra un elemento en la posición 'j' que es menor que el elemento
en la posición 'menor', se actualiza la variable 'menor' con el valor de 'j'. Esto
se hace para mantener un seguimiento de la posición del elemento más
pequeño en la parte no ordenada del arreglo.
Permutación de Elementos:
● Una vez que se ha explorado toda la parte no ordenada del arreglo y se ha
encontrado el elemento más pequeño (cuya posición está en 'menor'), se
realiza una permutación entre el elemento en la posición 'i' y el elemento en
la posición 'menor' utilizando la variable 'temp'. Esto coloca el elemento más
pequeño en su posición correcta en la parte ordenada del arreglo.
Finalización del Algoritmo:
● El ciclo "for" externo continúa hasta que hayamos recorrido todos los
elementos del arreglo. En cada iteración, se encuentra y coloca el elemento
más pequeño en la posición adecuada. Al final de la ejecución del algoritmo,
el arreglo estará completamente ordenado de forma ascendente.
15
Método Rápido o QuickSort:
El algoritmo quicksort se basa en la estrategia divide-y-vencerás, porque divide el
problema en dos subproblemas, que se resuelven de manera individual e
independiente. Los resultados se unen después. Dado un conjunto de números a1,
a2,..., an, se escoge un elemento X para dividir dicho conjunto en dos listas:
Después de la división, el quicksort puede aplicarse en forma recursiva tanto a L1
como a L2, con lo cual se obtiene una lista ordenada, ya que L1 contiene a todos los
a¡ menores que o iguales a X y L2 contiene a todos los ai mayores que X.
Ciertamente, no debe usarse X para recorrer toda la lista y decidir si un a¡ es menor
que o igual a X. Hacer lo anterior provoca una gran cantidad de intercambio de
datos. Sino que se utilizan dos apuntadores que se mueven al centro y realizan
intercambios de datos según sea necesario. Ejemplo ilustrado:
16
En cuanto a su codificación, el método se compone de los siguientes elementos:
Variables Utilizadas:
● PIVOTE: la variable 'pivote' almacena el valor del último elemento en el
arreglo. Este valor se utiliza como punto de referencia para dividir el arreglo
en dos partes: elementos menores que el pivote a la izquierda y elementos
mayores que el pivote a la derecha (o viceversa, si se desea ordenar de
manera descendente).
● ÍNDICES I y J: se utilizan como índices para recorrer el arreglo y realizar
permutaciones. Al inicio, 'i' se establece en -1 y 'j' se mueve desde 0 hasta la
posición del pivote.
● TEMP: La variable 'temp' se utiliza como almacenamiento temporal o auxiliar
para realizar las permutaciones entre elementos del arreglo.
Caso Base:
● El algoritmo tiene un caso base que verifica si el tamaño del subarreglo es
menor o igual a 1. Si es así, no se requiere ordenamiento, y la función se
devuelve inmediatamente.
Ciclo For:
● El algoritmo utiliza un ciclo "for" controlado por la variable 'j' para recorrer el
arreglo desde 0 hasta la posición del pivote (m-1). Dentro de este ciclo,
compara el elemento en la posición 'j' con el valor del pivote. Si el elemento
17
en la posición 'j' es menor que el pivote, se incrementa 'i' y se realiza una
permutación entre el elemento en la posición 'j' y el elemento en la posición 'i'.
Esto coloca los elementos menores que el pivote a la izquierda.
Permutación con el Último Elemento:
● Después de completar el ciclo "for", se vuelve a incrementar el índice ‘i’, se
realiza una permutación entre el elemento en la posición 'i' y el elemento en
la posición del pivote (m-1). Esto coloca al pivote en su posición final, donde
todos los elementos a su izquierda son menores que él, y todos los
elementos a su derecha son mayores que él.
Recursión:
● Luego de la permutación, el algoritmo se llama a sí mismo recursivamente
dos veces:
1. La primera llamada se hace para ordenar los elementos menores que
el pivote, con el subarreglo que va desde el inicio hasta 'i'.
2. La segunda llamada se hace para ordenar los elementos mayores que
el pivote, con el subarreglo que va desde 'i+1' hasta el final.
Este proceso de partición y recursión se repite hasta que todo el arreglo esté
ordenado.
Por Mezcla o MergeSort:
Para comprender el MergeSort, partimos de una matriz sin ordenar como la
siguiente:
El método primero divide toda la matriz iterativamente en mitades iguales a menos
que se logren los valores atómicos. Una matriz de 8 elementos se divide en dos
matrices de tamaño 4.
18
Esto no cambia la secuencia de apariencia de los elementos en el original. Ahora
dividimos estas dos matrices en mitades.
Dividimos aún más estas matrices y alcanzamos un valor atómico que ya no se
puede dividir.
Ahora, los combinamos exactamente de la misma manera que se desglosaron.
Después, comparamos el elemento para cada lista y luego los combinamos en otra
lista de manera ordenada. Vemos que 14 y 33 están en posiciones ordenadas.
Comparamos 27 y 10 y en la lista de objetivos de 2 valores ponemos 10 primero,
seguido de 27. Cambiamos el orden de 19 y 35, mientras que 42 y 44 se colocan
secuencialmente.
En la siguiente iteración de la fase de combinación, comparamos listas de dos
valores de datos y los fusionamos en una lista de valores de datos encontrados
colocando todo ordenado.
Después de la fusión final, la lista sería esta:
19
El método sigue dividiendo la lista en mitades iguales hasta que ya no se pueda
dividir. Por definición, si es solo un elemento en la lista, se ordena. Luego, se
combinan las listas ordenadas más pequeñas manteniendo la nueva lista ordenada
también.
En cuanto a su codificación, el método se compone de los siguientes elementos:
Variables Utilizadas:
● ÍNDICES IZQ y DER: estos índices apuntan al primer y último elemento
respectivamente del subarreglo que se está ordenando.
● ÍNDICES I, J, y K: se utilizan como índices para recorrer los subarreglos y el
arreglo completo, así como para realizar permutaciones.
● MED: la variable 'med' se calcula como la mitad del subarreglo y se utiliza
para dividir el arreglo en dos partes.
● TAM_IZQ y TAM_DER: estas variables almacenan la cantidad de elementos
en la parte izquierda y derecha del subarreglo.
● VEC_IZQ y VEC_DER: estos son vectores temporales que almacenan los
elementos de las partes izquierda y derecha del subarreglo.
División del Arreglo:
● El algoritmo funciona con vectores ya ordenados. Se divide el vector en dos
partes: izquierda y derecha. Cuando 'izq' es menor que 'der', se continúa
dividiendo y mezclando el arreglo en subarreglos más pequeños hasta que
haya uno (se considera ordenado) o ningún elemento en cada subarreglo.
Cálculo de la Mitad:
● Se calcula la variable 'med' para encontrar la mitad del subarreglo.
Llamadas Recursivas:
● El algoritmo llama a sí mismo recursivamente dos veces:
20
1. La primera llamada se hace para ordenar los elementos desde 'izq'
hasta 'med'.
2. La segunda llamada se hace para ordenar los elementos desde
'med+1' hasta 'der'.
Carga de Vectores Temporales:
● Se copian los elementos de las partes izquierda y derecha del subarreglo en
vectores temporales 'vec_izq' y 'vec_der' para que puedan ser ordenados y
fusionados luego.
Algoritmo de Mezcla:
● Se realiza un bucle que compara el primer elemento de las partes izquierda
('vec_izq') y derecha ('vec_der') y los fusiona en el arreglo principal, en orden
ascendente (o descendente, según se prefiera). El bucle continúa mientras 'i'
sea menor que 'tam_izq' y 'j' sea menor que 'tam_der' o mientras haya
elementos en las partes izquierda o derecha para comparar. Se toma el
elemento más pequeño de las partes izquierda y derecha y se coloca en el
arreglo principal. Los índices 'i' y 'j' se incrementan en consecuencia. Este
proceso de división y mezcla se repite hasta que todo el arreglo esté
ordenado.
Diferencias entre los Métodos de Ordenamiento
Eficiencia:
● BubbleSort, InsertionSort y SelectionSort tienen una complejidad de
tiempo de O(n^2) en el peor caso, entonces pueden ser ineficientes para
listas muy grandes. Esto significa que el tiempo necesario para ejecutar el
algoritmo aumenta cuadráticamente a medida que aumenta el tamaño de los
datos. Por ejemplo, si tardan 1 segundo en ordenar una lista de 100
elementos, es probable que tome aprox. 4 segundos en ordenar una lista de
200 elementos, 9 segundos en ordenar una lista de 300 elementos y así
sucesivamente.
● QuickSort y MergeSort tienen una complejidad de tiempo de O(n log n) en
el peor caso, lo que los hace mucho más eficientes para listas grandes. Es
21
decir, tienen un crecimiento mucho más lento a medida que aumenta el
tamaño de los datos.
Uso de Memoria:
● BubbleSort, InsertionSort y Selection Sort requieren una cantidad
constante o fija de memoria adicional. Esto quiere decir que no depende del
tamaño de los datos de entrada. Es decir, no importa si se está ordenando
una lista de 10 elementos o una lista de 1,000 elementos, la cantidad de
memoria adicional requerida para realizar la clasificación es la misma.
● QuickSort puede requerir memoria adicional, dependiendo de la
implementación. La versión recursiva puede tener una alta carga en la pila de
llamadas. Esto significa que la cantidad de memoria adicional requerida
dependerá de la profundidad de la recursión. En el peor caso, donde la
recursión es muy profunda, podría consumir una cantidad significativa de
memoria.
● MergeSort requiere memoria adicional para la fusión, lo que puede hacer
que no sea la mejor opción para listas muy grandes con limitaciones de
memoria. Dado que este método divide la lista en subarreglos y luego los
fusiona en orden, se necesita espacio adicional para mantener
temporalmente estos subarreglos antes de la fusión.
Adaptabilidad:
● BubbleSort y InsertionSort son adaptables, lo que significa que funcionan
mejor en listas casi ordenadas, pues minimizan el número de comparaciones
y movimientos de elementos cuando la mayoría ya están en su lugar
correcto.
● Selection Sort, QuickSort y MergeSort no son particularmente adaptables.
Es decir, no ajustan su rendimiento en función del grado de desorden en la
lista. Realizarán aproximadamente el mismo número de comparaciones y
movimientos, independientemente de si la lista está ordenada o casi
ordenada.
22
Bibliografía:
Algoritmos Fundamentales (2021); Donald Knuth
[Link]
hl=es&lr=&id=4kUUEAAAQBAJ&oi=fnd&pg=PR5&dq=algoritmos+donald+knu
th&ots=hnp6OvQDK_&sig=H6F-
1_0lDmyjLmxttpyWrMAI09w#v=onepage&q&f=false
Introducción a la Complejidad Computacional (2004); Ing. Nestor Díaz
[Link]
Complejidad Algorítmica; Departamento de Informática, Universidad de
Valladolid, Campus de Segovia
[Link]
Teoría de la complejidad algorítmica; Ing. Rolf Manolo Pinto López
[Link]
complejidad-algoritmica
Bubble Sort en C++ (2014); Geek for Geeks
[Link]
Ordenamiento por Inserción (2023); Harshit Jindal
[Link]
Ordenamiento por Selección (2023); Harshit Jindal
[Link]
23