Introducción a la clase
En esta clase exploraremos los principales algoritmos de ordenación, que permiten organizar datos en una secuencia específica. Compararemos sus ventajas, desventajas y su eficiencia en diferentes escenarios.
¿Qué obtendrás de esta clase?
- Comprender la importancia de la ordenación en estructuras de datos.
- Aprender e implementar Bubble Sort, Merge Sort y Quick Sort en C#.
- Comparar la eficiencia de cada algoritmo utilizando Big O Notation.
- Aplicar estos algoritmos en casos reales.
Bubble Sort
Bubble Sort es un algoritmo de ordenación simple pero ineficiente, que compara y intercambia elementos adyacentes hasta que toda la lista está ordenada.
Características de Bubble Sort
- Comparaciones repetidas en pares de elementos.
- Complejidad O(n²) en el peor caso.
- No es recomendado para listas grandes debido a su baja eficiencia.
Implementación en C#
using System;
class Program
{
static void BubbleSort(int[] arreglo)
{
int n = arreglo.Length;
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (arreglo[j] > arreglo[j + 1])
{
// Intercambiar elementos
int temp = arreglo[j];
arreglo[j] = arreglo[j + 1];
arreglo[j + 1] = temp;
}
}
}
}
static void Main()
{
int[] numeros = { 64, 34, 25, 12, 22, 11, 90 };
BubbleSort(numeros);
Console.WriteLine("Array ordenado con Bubble Sort: " + string.Join(", ", numeros));
}
}
Merge Sort
Merge Sort es un algoritmo de ordenación por división y conquista que divide el array en mitades, las ordena y luego las combina.
Características de Merge Sort
- Divide el array en subarrays más pequeños.
- Usa recursión para ordenar y fusionar los elementos.
- Complejidad O(n log n) en todos los casos.
Implementación en C#
using System;
class Program
{
static void Merge(int[] arreglo, int izquierda, int medio, int derecha)
{
int n1 = medio - izquierda + 1;
int n2 = derecha - medio;
int[] izquierdaArr = new int[n1];
int[] derechaArr = new int[n2];
for (int i = 0; i < n1; i++)
izquierdaArr[i] = arreglo[izquierda + i];
for (int j = 0; j < n2; j++)
derechaArr[j] = arreglo[medio + 1 + j];
int iL = 0, jR = 0, k = izquierda;
while (iL < n1 && jR < n2)
{
if (izquierdaArr[iL] <= derechaArr[jR])
arreglo[k++] = izquierdaArr[iL++];
else
arreglo[k++] = derechaArr[jR++];
}
while (iL < n1)
arreglo[k++] = izquierdaArr[iL++];
while (jR < n2)
arreglo[k++] = derechaArr[jR++];
}
static void MergeSort(int[] arreglo, int izquierda, int derecha)
{
if (izquierda < derecha)
{
int medio = izquierda + (derecha - izquierda) / 2;
MergeSort(arreglo, izquierda, medio);
MergeSort(arreglo, medio + 1, derecha);
Merge(arreglo, izquierda, medio, derecha);
}
}
static void Main()
{
int[] numeros = { 64, 34, 25, 12, 22, 11, 90 };
MergeSort(numeros, 0, numeros.Length - 1);
Console.WriteLine("Array ordenado con Merge Sort: " + string.Join(", ", numeros));
}
}
Quick Sort
Quick Sort selecciona un pivote, divide el array en elementos menores y mayores que el pivote y ordena recursivamente.
Características de Quick Sort
- Usa particionamiento para dividir y conquistar.
- Complejidad O(n log n) en promedio, pero O(n²) en el peor caso.
- Más eficiente que Merge Sort en arreglos pequeños.
Implementación en C#
using System;
class Program
{
static void QuickSort(int[] arreglo, int izquierda, int derecha)
{
if (izquierda < derecha)
{
int pivote = Particionar(arreglo, izquierda, derecha);
QuickSort(arreglo, izquierda, pivote - 1);
QuickSort(arreglo, pivote + 1, derecha);
}
}
static int Particionar(int[] arreglo, int izquierda, int derecha)
{
int pivote = arreglo[derecha];
int i = izquierda - 1;
for (int j = izquierda; j < derecha; j++)
{
if (arreglo[j] < pivote)
{
i++;
(arreglo[i], arreglo[j]) = (arreglo[j], arreglo[i]);
}
}
(arreglo[i + 1], arreglo[derecha]) = (arreglo[derecha], arreglo[i + 1]);
return i + 1;
}
static void Main()
{
int[] numeros = { 64, 34, 25, 12, 22, 11, 90 };
QuickSort(numeros, 0, numeros.Length - 1);
Console.WriteLine("Array ordenado con Quick Sort: " + string.Join(", ", numeros));
}
}
Comparación entre los algoritmos de ordenación
| Algoritmo | Mejor caso | Peor caso | Complejidad promedio | Estable |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Sí |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Sí |
| Quick Sort | O(n log n) | O(n²) | O(n log n) | No |
Caso de uso real
Un sistema de comercio electrónico usa un algoritmo de ordenación para organizar productos según precio, popularidad o relevancia. Merge Sort y Quick Sort son las mejores opciones debido a su eficiencia.
Ejemplo en C#: Ordenación de productos por precio con Quick Sort
using System;
class Program
{
static void QuickSort(decimal[] precios, int izquierda, int derecha)
{
if (izquierda < derecha)
{
int pivote = Particionar(precios, izquierda, derecha);
QuickSort(precios, izquierda, pivote - 1);
QuickSort(precios, pivote + 1, derecha);
}
}
static int Particionar(decimal[] precios, int izquierda, int derecha)
{
decimal pivote = precios[derecha];
int i = izquierda - 1;
for (int j = izquierda; j < derecha; j++)
{
if (precios[j] < pivote)
{
i++;
(precios[i], precios[j]) = (precios[j], precios[i]);
}
}
(precios[i + 1], precios[derecha]) = (precios[derecha], precios[i + 1]);
return i + 1;
}
static void Main()
{
decimal[] precios = { 299.99m, 149.99m, 79.99m, 499.99m, 199.99m };
QuickSort(precios, 0, precios.Length - 1);
Console.WriteLine("Productos ordenados por precio: " + string.Join(", ", precios));
}
}
Próxima clase: Programación Dinámica y Algoritmos de Backtracking
En la siguiente clase exploraremos programación dinámica y backtracking, dos técnicas avanzadas utilizadas en problemas de optimización y generación de combinaciones.
