8. Ordenamiento y Búsqueda de Datos
#estructuraDeDatos #universidad
a. Métodos de Ordenamiento
El ordenamiento es el proceso de reorganizar los elementos de una lista o arreglo en un orden específico (por ejemplo, ascendente o descendente). Es fundamental para optimizar la eficiencia de otras operaciones como la búsqueda y la manipulación de datos.
Principales Algoritmos de Ordenamiento:
-
Ordenamiento Burbuja (Bubble Sort):
- Descripción: Recorre repetidamente la lista, comparando pares adyacentes y permutándolos si están en el orden incorrecto.
- Complejidad: O(n²)
- Ventajas: Fácil de implementar.
- Desventajas: Ineficiente para listas grandes.
Implementación en C:
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Intercambiar arr[j] y arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void imprimirArreglo(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Arreglo original: ");
imprimirArreglo(arr, n);
bubbleSort(arr, n);
printf("Arreglo ordenado: ");
imprimirArreglo(arr, n);
return 0;
}
Salida:
Arreglo original: 64 34 25 12 22 11 90
Arreglo ordenado: 11 12 22 25 34 64 90
- Ordenamiento Selección (Selection Sort):
- Descripción: Divide la lista en dos partes: ordenada y no ordenada. Repetidamente selecciona el elemento mínimo de la parte no ordenada y lo mueve al final de la parte ordenada.
- Complejidad: O(n²)
- Ventajas: Menos intercambios que el burbuja.
- Desventajas: Sigue siendo ineficiente para listas grandes.
Implementación en C:
#include <stdio.h>
void selectionSort(int arr[], int n) {
int i, j, min_idx;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx])
min_idx = j;
}
// Intercambiar el elemento mínimo con el primero
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
void imprimirArreglo(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Arreglo original: ");
imprimirArreglo(arr, n);
selectionSort(arr, n);
printf("Arreglo ordenado: ");
imprimirArreglo(arr, n);
return 0;
}
Salida:
Arreglo original: 64 25 12 22 11
Arreglo ordenado: 11 12 22 25 64
- Ordenamiento Inserción (Insertion Sort):
- Descripción: Construye la lista ordenada de forma incremental, tomando cada elemento y colocándolo en su posición correcta dentro de la parte ya ordenada.
- Complejidad: O(n²)
- Ventajas: Eficiente para listas pequeñas o casi ordenadas.
- Desventajas: Ineficiente para listas grandes.
Implementación en C:
#include <stdio.h>
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// Mover los elementos de arr[0..i-1] que son mayores que key
// a una posición adelante de su posición actual
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void imprimirArreglo(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Arreglo original: ");
imprimirArreglo(arr, n);
insertionSort(arr, n);
printf("Arreglo ordenado: ");
imprimirArreglo(arr, n);
return 0;
}
Salida:
Arreglo original: 12 11 13 5 6
Arreglo ordenado: 5 6 11 12 13
- Ordenamiento Rápido (Quick Sort):
- Descripción: Algoritmo divide y vencerás que selecciona un pivote, particiona la lista en dos sublistas (elementos menores y mayores al pivote), y aplica recursivamente el mismo proceso a las sublistas.
- Complejidad: O(n log n) en promedio.
- Ventajas: Muy eficiente para grandes conjuntos de datos.
- Desventajas: Su peor caso es O(n²), aunque se puede mitigar con buenas estrategias de pivote.
Implementación en C:
#include <stdio.h>
// Función para intercambiar dos elementos
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// Función para particionar el arreglo
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Pivote
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// Si el elemento actual es menor o igual al pivote
if (arr[j] <= pivot) {
i++; // Incrementar índice del menor elemento
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// Implementación de QuickSort
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi es el índice de partición
int pi = partition(arr, low, high);
// Ordenar recursivamente los elementos antes y después de la partición
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void imprimirArreglo(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Arreglo original: ");
imprimirArreglo(arr, n);
quickSort(arr, 0, n - 1);
printf("Arreglo ordenado: ");
imprimirArreglo(arr, n);
return 0;
}
Salida:
Arreglo original: 10 7 8 9 1 5
Arreglo ordenado: 1 5 7 8 9 10
- Ordenamiento Mezcla (Merge Sort):
- Descripción: Algoritmo divide y vencerás que divide el arreglo en mitades, las ordena recursivamente y luego las fusiona en una lista ordenada.
- Complejidad: O(n log n) en todos los casos.
- Ventajas: Estable, eficiente para grandes conjuntos de datos.
- Desventajas: Requiere espacio adicional para la fusión.
Implementación en C:
#include <stdio.h>
#include <stdlib.h>
// Función para fusionar dos subarreglos
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Crear arreglos temporales
int* L = (int*)malloc(n1 * sizeof(int));
int* R = (int*)malloc(n2 * sizeof(int));
// Copiar datos a los arreglos temporales
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Fusionar los arreglos temporales de nuevo en arr[left..right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copiar los elementos restantes de L[], si los hay
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copiar los elementos restantes de R[], si los hay
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
// Liberar memoria
free(L);
free(R);
}
// Implementación de MergeSort
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Ordenar la primera y segunda mitad
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Fusionar las mitades ordenadas
merge(arr, left, mid, right);
}
}
void imprimirArreglo(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Arreglo original: ");
imprimirArreglo(arr, n);
mergeSort(arr, 0, n - 1);
printf("Arreglo ordenado: ");
imprimirArreglo(arr, n);
return 0;
}
Salida:
Arreglo original: 12 11 13 5 6 7
Arreglo ordenado: 5 6 7 11 12 13
Comparación de Algoritmos de Ordenamiento:
| Algoritmo | Complejidad Promedio | Complejidad Peor Caso | Estable | Espacio Adicional |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | Sí | O(1) |
| Selection Sort | O(n²) | O(n²) | No | O(1) |
| Insertion Sort | O(n²) | O(n²) | Sí | O(1) |
| Quick Sort | O(n log n) | O(n²) | No | O(log n) |
| Merge Sort | O(n log n) | O(n log n) | Sí | O(n) |
b. Métodos de Búsqueda
La búsqueda es el proceso de encontrar un elemento específico dentro de una estructura de datos. Es fundamental para operaciones como la recuperación de información y la verificación de la existencia de datos.
Principales Algoritmos de Búsqueda:
-
Búsqueda Lineal (Secuencial):
- Descripción: Recorre cada elemento de la lista hasta encontrar el elemento deseado o llegar al final.
- Complejidad: O(n)
- Ventajas: Simple, no requiere que la lista esté ordenada.
- Desventajas: Ineficiente para listas grandes.
Implementación en C:
#include <stdio.h>
int busquedaLineal(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x)
return i; // Retorna el índice donde se encontró el elemento
}
return -1; // Indicador de no encontrado
}
int main() {
int arr[] = {2, 4, 0, 1, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 1;
int resultado = busquedaLineal(arr, n, x);
if (resultado != -1)
printf("Elemento %d encontrado en el índice %d.\n", x, resultado);
else
printf("Elemento %d no encontrado en el arreglo.\n", x);
return 0;
}
Salida
Elemento 1 encontrado en el índice 3.
- Búsqueda Binaria (Binary Search):
- Descripción: Divide el arreglo ordenado en mitades, comparando el elemento medio con el objetivo y descartando la mitad donde el elemento no puede estar.
- Complejidad: O(log n)
- Ventajas: Muy eficiente para listas grandes.
- Desventajas: Requiere que la lista esté ordenada previamente.
Implementación en C:
#include <stdio.h>
int busquedaBinaria(int arr[], int l, int r, int x) {
while (l <= r) {
int mid = l + (r - l) / 2;
// Verificar si x está en el medio
if (arr[mid] == x)
return mid;
// Si x es mayor, ignorar la mitad izquierda
if (arr[mid] < x)
l = mid + 1;
else
r = mid - 1;
}
return -1; // Indicador de no encontrado
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int resultado = busquedaBinaria(arr, 0, n - 1, x);
if (resultado != -1)
printf("Elemento %d encontrado en el índice %d.\n", x, resultado);
else
printf("Elemento %d no encontrado en el arreglo.\n", x);
return 0;
}
Salida:
Elemento 10 encontrado en el índice 3.
- Búsqueda Interpolación:
- Descripción: Similar a la búsqueda binaria, pero estima la posición del elemento utilizando una fórmula de interpolación, especialmente útil cuando los elementos están uniformemente distribuidos.
- Complejidad: O(log log n) en el mejor caso.
- Ventajas: Puede ser más eficiente que la búsqueda binaria para ciertos tipos de datos.
- Desventajas: Menos eficiente si los datos no están uniformemente distribuidos.
- Búsqueda Exponencial:
- Descripción: Combina la búsqueda lineal y binaria. Primero encuentra un rango exponencial donde podría estar el elemento y luego aplica una búsqueda binaria dentro de ese rango.
- Complejidad: O(log n)
- Ventajas: Útil para listas muy grandes.
- Búsqueda por Hashing:
- Descripción: Utiliza una función hash para mapear claves a posiciones en una tabla, permitiendo búsquedas en tiempo constante promedio.
- Complejidad: O(1) en promedio.
- Ventajas: Muy eficiente para grandes conjuntos de datos.
- Desventajas: Requiere una buena función hash y manejo de colisiones.
Ejemplo de Búsqueda Binaria Recursiva en C:
#include <stdio.h>
int busquedaBinariaRecursiva(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
// Si el elemento está en el medio
if (arr[mid] == x)
return mid;
// Si el elemento es menor, está en la mitad izquierda
if (arr[mid] > x)
return busquedaBinariaRecursiva(arr, l, mid - 1, x);
// Si el elemento es mayor, está en la mitad derecha
return busquedaBinariaRecursiva(arr, mid + 1, r, x);
}
return -1; // Indicador de no encontrado
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int resultado = busquedaBinariaRecursiva(arr, 0, n - 1, x);
if (resultado != -1)
printf("Elemento %d encontrado en el índice %d.\n", x, resultado);
else
printf("Elemento %d no encontrado en el arreglo.\n", x);
return 0;
}
Salida:
Elemento 10 encontrado en el índice 3.
Ejercicios
-
Implementación de Ordenamiento Rápido (Quick Sort):
- Implementa el algoritmo Quick Sort en C.
- Modifica el programa para contar el número de intercambios realizados durante el ordenamiento.
-
Comparación de Algoritmos de Ordenamiento:
- Implementa Bubble Sort, Selection Sort e Insertion Sort.
- Crea un programa que mida y compare el tiempo de ejecución de cada algoritmo para arreglos de diferentes tamaños (puedes usar la función
clock()de<time.h>).
-
Búsqueda Binaria en un Arreglo Ordenado:
- Implementa una búsqueda binaria recursiva y una iterativa.
- Crea un programa que permita al usuario ingresar un número y busque su posición en el arreglo.
-
Ordenamiento Estable vs. No Estable:
- Define qué significa que un algoritmo de ordenamiento sea estable o no estable.
- Da ejemplos de algoritmos estables y no estables.
- Modifica un algoritmo de ordenamiento para que sea estable (por ejemplo, haciendo Bubble Sort estable si no lo es).