ASIGNATURA
Estructuras de Datos
Análisis de Algoritmos
Docente / Miryam Acosta
PROFESIONAL EN INGENIERÍA DE SISTEMAS
FACULTAD DE INGENIERÍA. DISEÑO E INNOVACIÓN
Ordenamiento
por inserción
(Insertion Sort)
Explicación
Este algoritmo construye la lista ordenada un
elemento a la vez. Comienza con el segundo
elemento y lo coloca en la posición correcta con
respecto al primer elemento, luego pasa al tercer
elemento, y así sucesivamente.
Pasos
1. Comienza con el segundo elemento de la lista.
2. Compara el elemento actual con los
anteriores.
3. Desplaza los elementos mayores a la derecha.
4. Inserta el elemento en su posición correcta
dentro de los elementos anteriores.
5. Repite el proceso hasta recorrer toda la lista.
Ejemplo:
Lista inicial:
[12, 11, 13, 5, 6]
Pasos
1. El primer elemento (12) está en su lugar.
2. Comparar 11 con 12, desplazar 12 y colocar 11 → [11, 12, 13, 5, 6]
3. Comparar 13 con 12, no hacer cambios.
4. Comparar 5 con los elementos anteriores, desplazar 12 y 11 → [5, 11, 12, 13, 6]
5. Comparar 6 con los elementos anteriores, desplazar 12 y 11 → [5, 6, 11, 12, 13]
Lista final:
[5, 6, 11, 12, 13]
Ejercicio
Práctico
Llama al método insertionSort que definimos
más abajo, pasando el array arr como
argumento para que se ordene utilizando el
algoritmo de inserción.
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
insertionSort(arr);
System.out.println("Array ordenado:");
for (int i : arr) {
System.out.print(i + " ");
}
} Este es un bucle for-each que recorre cada
uno de los elementos del array arr. En cada
iteración, el valor de i tomará el valor de
cada elemento del array (por ejemplo,
www.ilumno.com
Imprime cada elemento del array arr seguido primero 64, luego 34, etc.).
de un espacio. Esto permite que los números
se muestren en una línea, separados por
espacios.
Este es el método que implementa el algoritmo de ordenamiento por
inserción. Recibe como parámetro un array de enteros arr que será
ordenado. Es public para que sea accesible desde el main, static porque no
necesita una instancia de la clase para ser llamado, y void porque no
retorna ningún valor.
public static void insertionSort(int[] arr) {
int n = arr.length; Calcula la longitud del array arr y la
almacena en la variable n. Esto nos
dice cuántos elementos tiene el
for (int i = 1; i < n; i++) { array.
int key = arr[i]; // El elemento actual a ordenar
int j = i - 1;
Se asigna el valor del elemento actual (el
que está en el índice i) a la variable key.
Este será el elemento que intentaremos
insertar en la parte ordenada del array.
Se inicializa j en el índice anterior al elemento actual (i - 1). j
se usará para recorrer los elementos anteriores y moverlos si
son mayores que la key.
Inicia un bucle for que comenzará desde el índice 1 (el segundo
elemento del array) y se ejecutará hasta el final del array (hasta i < n).
Esto es porque el primer elemento (arr[0]) ya está considerado
ordenado en su lugar.
// Desplaza los elementos mayores que la clave hacia la
derecha
Este es un bucle while que continuará
ejecutándose mientras:
while (j >= 0 && arr[j] > key) { • j >= 0: Asegura que no se salga del
arr[j + 1] = arr[j]; rango del array.
j = j - 1;
} Si el elemento arr[j] es mayor
que key, lo movemos una posición
a la derecha. Esto crea espacio
// Coloca la clave en la posición correcta para insertar la key en su lugar
arr[j + 1] = key; correcto.
}
}
}
Disminuye j para continuar Una vez que el bucle while termina, j estará en la
comparando la key con el posición donde la key debe ser insertada.
siguiente elemento a la Colocamos la key en ese lugar (es j + 1 porque el
izquierda (por eso, j va índice j fue decrementado una vez de más durante
decreciendo). el bucle).
www.ilumno.com
Ordenamiento
rápido (Quick
Sort)
Explicación
Este es un algoritmo eficiente basado en el
enfoque "divide y vencerás". Elige un "pivote",
divide la lista en dos sublistas (menores y mayores
que el pivote), y ordena recursivamente cada
sublista.
Pasos
1. Selecciona un elemento como pivote.
2. Reorganiza la lista colocando los elementos menores que
el pivote a la izquierda y los mayores a la derecha.
3. Recursivamente aplica el mismo proceso a las sublistas
de izquierda y derecha.1
www.ilumno.com
Lista inicial: [10, 7, 8, 9, 1, 5]
1. Seleccionar 5 como pivote.
2. Reorganizar → [1, 5, 8, 9, 7, 10]
3. Ordenar las sublistas [1] y [8, 9, 7, 10].
4. Elegir 7 como pivote para la sublista → [1, 5, 7, 9, 8, 10]
5. Ordenar las sublistas [9, 8, 10].
6. Elegir 10 como pivote, que ya está en lugar correcto
Lista final:
www.ilumno.com
[1, 5, 7, 8, 9, 10]
Ejercicio
Práctico
www.ilumno.com
// Llamada al método quickSort para ordenar el array completo
(desde el índice 0 hasta el índice final)
www.ilumno.com
// La condición de parada es cuando low no es menor que high
(solo ordena si hay más de un elemento)
// Llamada al método partition para dividir el array en dos
sublistas y encontrar el índice del pivote
www.ilumno.com
// Inicializa la variable i (que rastrea el último índice de
elementos menores o iguales al pivote)
www.ilumno.com
// Incrementa i, porque el elemento arr[j] debe ir a la izquierda
del pivote
// Intercambia arr[i] con arr[j] para mantener los elementos
menores al pivote a la izquierda
www.ilumno.com
Parte 1: InsertionSort
Objetivo: Implementar y aplicar el algoritmo InsertionSort para ordenar arrays de diferentes tamaños y
distribuciones
Descripción:El algoritmo InsertionSort toma un elemento a la vez de un array y lo coloca en su posición correcta
dentro de la porción ordenada. Este proceso se repite hasta que todos los elementos estén ordenados.
Instrucciones:
Caso 1: Array pequeño, desordenado
Array: {64, 34, 25, 12, 22, 11, 90}
Implementa el algoritmo de InsertionSort y muestra el array antes y después del ordenamiento.
Caso 2: Array con elementos ya ordenados
Array: {1, 2, 3, 4, 5, 6, 7}Implementa InsertionSort para ordenar un array que ya está ordenado.
Discute el comportamiento del algoritmo cuando el array está casi ordenado.
Caso 3: Array con todos los elementos iguales
Array: {5, 5, 5, 5, 5, 5, 5}
Implementa InsertionSort y observa cómo maneja un array con elementos duplicados.
www.ilumno.com
Caso 4: Array con pocos elementos, pero desordenado
Array: {9, 7, 8, 5}
Implementa InsertionSort y observa cómo el algoritmo maneja arrays pequeños y desordenados.
Parte 2: QuickSort
Objetivo: Implementar y aplicar el algoritmo QuickSort para ordenar arrays con diferentes características.
Descripción:
El algoritmo QuickSort selecciona un pivote, divide el array en dos sublistas (menores y mayores que el pivote),
y aplica recursivamente el mismo proceso a las sublistas. Esto sigue hasta que todas las sublistas están ordenadas.
Instrucciones:
Caso 1: Array pequeño, desordenado
Array: {64, 34, 25, 12, 22, 11, 90}
Implementa QuickSort para ordenar este array y muestra el array antes y después del ordenamiento.
Caso 2: Array con elementos ya ordenados
Array: {1, 2, 3, 4, 5, 6, 7}
Implementa QuickSort y analiza cómo el algoritmo maneja un array que ya está ordenado. ¿Hay algún comportamiento
peculiar? ¿Cómo se comporta el algoritmo cuando el pivote ya está en la posición correcta?
Caso 3: Array con elementos en orden inverso
Array: {7, 6, 5, 4, 3, 2, 1}
Implementa QuickSort y observa el comportamiento del algoritmo cuando el array está en orden inverso. ¿Es este el peor
caso para QuickSort?
www.ilumno.com
Caso 4: Array con muchos elementos duplicados
Array: {9, 7, 7, 9, 8, 8, 7, 9}
Implementa QuickSort y analiza cómo maneja arrays con muchos elementos duplicados.
