Algoritmos estándar: búsqueda lineal y binaria, ordenamiento, Bubblesort, Selection e Insertion
La búsqueda y el ordenamiento son operaciones fundamentales en el desarrollo de software. En este artículo conocerás cinco algoritmos esenciales: búsqueda lineal, búsqueda binaria, Bubblesort, Selection Sort e Insertion Sort. Para cada algoritmo explicaré cómo funciona, su complejidad temporal en notación Big-O y un ejemplo de código en Python.
Ya sea en una entrevista técnica, en tus estudios o en cualquier formación en programación, búsqueda y ordenamiento siempre aparecen. Normalmente se trata de implementaciones simples como Bubblesort o manejo básico de arrays.
Conviene que entiendas los algoritmos principales. Te harán la vida más fácil.
El tiempo es dinero, y aquí empieza el primer dilema de la programación: ¿cuándo es un algoritmo realmente bueno? ¿Cuándo es prácticamente inutilizable?
Con datasets pequeños casi no notas la diferencia entre esperar 0.2 segundos o 0.5. Pero con grandes volúmenes de datos, esos segundos se transforman en minutos. La elección correcta del algoritmo marca la diferencia.
Por eso medimos los algoritmos por velocidad. Nuestro objetivo siempre es encontrar el algoritmo más rápido. Ya hemos escrito sobre esto, pero como es relevante aquí, vale la pena mencionarlo de nuevo.
¿Qué significan O(1), O(n), O(log n) y O(n²)?
Antes de analizar cada algoritmo, debes entender cómo describimos su velocidad usando la notación Big-O. No te dice cuántos milisegundos tarda un algoritmo, sino cómo crece el tiempo de ejecución conforme aumentan los datos.
Aquí están las clases principales:
- O(1) – constante: El tiempo no cambia sin importar cuántos datos haya. Acceder a un elemento del array por índice es un ejemplo.
- O(log n) – logarítmica: El tiempo crece muy lentamente. La búsqueda binaria reduce el rango a la mitad en cada paso, por eso es O(log n).
- O(n) – lineal: El tiempo crece proporcionalmente con los datos. Con 1.000 elementos tarda aproximadamente el doble que con 500.
- O(n²) – cuadrática: El tiempo crece muy rápido. Con el doble de datos tarda aproximadamente cuatro veces más. Muchos algoritmos de ordenamiento simples tienen esta complejidad.
Big-O describe siempre el peor caso, el escenario más desfavorable. Te ayuda a estimar la peor ejecución posible de un algoritmo.
Encontrarás explicaciones más detalladas en Big-O Notation: Laufzeitkomplexität und Effizienz O(1), O(n), O(log n) y en la introducción a Komplexitätsanalyse, Big-O, Such- und Sortieralgorithmen. Para los siguientes algoritmos, basta con que mires nuestro análisis y puedas clasificarlos entre “BUENO” y “MENOS BUENO”.
Búsqueda lineal
La búsqueda lineal recorre una lista elemento por elemento hasta encontrar el buscado o llegar al final. Funciona tanto con datos ordenados como desordenados.
Empiezas al principio de la fila y avanzas hasta el final. Quizás tengas suerte y esté al inicio. Quizás sea el último elemento.
def lineare_suche(liste, ziel):
for index, wert in enumerate(liste):
if wert == ziel:
return index
return -1- Mejor caso: O(1) (el elemento está cerca del inicio)
- Peor caso: O(n) (está al final)
- Caso promedio: O(n)
La búsqueda lineal es simple pero lenta con grandes volúmenes.
Búsqueda binaria
La búsqueda binaria reduce el rango de búsqueda a la mitad en cada paso. Requiere que la lista esté ordenada. Comparada con búsqueda lineal, es mucho más rápida con grandes datasets.
def binaere_suche(liste, ziel):
links = 0
rechts = len(liste) - 1
while links <= rechts:
mitte = (links + rechts) // 2
if liste[mitte] == ziel:
return mitte
if liste[mitte] < ziel:
links = mitte + 1
else:
rechts = mitte - 1
return -1- Mejor caso: O(1)
- Peor caso: O(log n)
- Caso promedio: O(log n)
Con un millón de elementos, búsqueda binaria necesita solo unos 20 comparaciones en el peor caso.
¿Cuántas sería con búsqueda lineal?
Bubblesort
Bubblesort compara repetidamente elementos adyacentes e intercambia aquellos que están en el orden incorrecto. Los elementos mayores suben gradualmente.
Este algoritmo es muy popular en exámenes y tareas simples. Vale la pena que lo entiendas a fondo.
def bubblesort(liste):
n = len(liste)
while True:
vertauscht = False
for i in range(n - 1):
if liste[i] > liste[i + 1]:
liste[i], liste[i + 1] = liste[i + 1], liste[i]
vertauscht = True
n -= 1
if not vertauscht:
break
return liste- Mejor caso: O(n)
- Peor caso: O(n²)
- Caso promedio: O(n²)
Bubblesort es fácil de entender pero ineficiente con grandes volúmenes.
Selection Sort
Selection Sort busca el elemento más pequeño en cada pasada dentro del área desordenada e lo coloca al final del área ordenada.
def selection_sort(liste):
n = len(liste)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if liste[j] < liste[min_index]:
min_index = j
liste[i], liste[min_index] = liste[min_index], liste[i]
return liste- Mejor caso: O(n²)
- Peor caso: O(n²)
- Caso promedio: O(n²)
Selection Sort es simple pero siempre cuadrático. Realiza menos intercambios que Bubblesort.
Insertion Sort
Insertion Sort inserta cada elemento en su posición correcta dentro del área ya ordenada. Es similar a cómo ordenas las cartas en tu mano mientras juegas.
def insertion_sort(liste):
for i in range(1, len(liste)):
aktuelles = liste[i]
j = i - 1
while j >= 0 and liste[j] > aktuelles:
liste[j + 1] = liste[j]
j -= 1
liste[j + 1] = aktuelles
return liste- Mejor caso: O(n)
- Peor caso: O(n²)
- Caso promedio: O(n²)
Insertion Sort es particularmente eficiente cuando la lista ya está casi ordenada.
Comparación de algoritmos de búsqueda y ordenamiento
| Algoritmo | Tipo | Mejor caso | Peor caso | Cuándo usarlo |
|---|---|---|---|---|
| Búsqueda lineal | Búsqueda | O(1) | O(n) | Datos pequeños y desordenados |
| Búsqueda binaria | Búsqueda | O(1) | O(log n) | Datos grandes y ordenados |
| Bubblesort | Ordenamiento | O(n) | O(n²) | Solo para aprender |
| Selection Sort | Ordenamiento | O(n²) | O(n²) | Datos pequeños, pocos intercambios |
| Insertion Sort | Ordenamiento | O(n) | O(n²) | Datos casi ordenados, listas pequeñas |
Qué algoritmo usar en cada caso
Para la búsqueda:
- En datos sin ordenar, usa la búsqueda lineal.
- En datos ordenados, usa la búsqueda binaria.
Para la ordenación:
- Bubblesort solo sirve para aprender.
- Selection Sort es simple pero lento.
- Insertion Sort funciona bien con conjuntos pequeños o casi ordenados.
- Para grandes volúmenes de datos, es mejor usar Quicksort, Mergesort o Heapsort.
La búsqueda lineal, búsqueda binaria, Bubblesort, Selection Sort e Insertion Sort son la base para entender algoritmos y estructuras de datos. Son simples, educativos y muestran claramente cómo Big-O describe el tiempo de ejecución. En la práctica, para grandes volúmenes de datos se usan algoritmos más rápidos, pero comprender estos cinco algoritmos estándar es esencial para cualquier desarrollador.
Recomendaciones de libros sobre algoritmos y estructuras de datos
Si quieres profundizar en algoritmos y estructuras de datos, te recomendamos los siguientes libros:
Keine Bücher für Kategorie "algorithmen" gefunden.
FAQ: Algoritmos estándar, búsqueda y ordenación
1. ¿Qué es un algoritmo estándar?
2. ¿Cuál es la diferencia entre búsqueda y ordenación?
3. ¿Qué es la búsqueda lineal?
4. ¿Cuándo se usa la búsqueda lineal?
5. ¿Qué es la búsqueda binaria?
6. ¿Por qué la búsqueda binaria es más rápida que la lineal?
7. ¿Qué requisito necesita la búsqueda binaria?
8. ¿Qué es Bubblesort?
9. ¿Por qué Bubblesort casi nunca se usa en la práctica?
10. ¿Qué es Selection Sort?
11. ¿Qué es Insertion Sort?
12. ¿Cuál es el mejor caso de Insertion Sort?
13. ¿Qué significa O(1)?
14. ¿Qué significa O(n)?
15. ¿Qué significa O(log n)?
16. ¿Qué significa O(n²)?
17. ¿Qué es el peor caso?
Claro que también tenemos un artículo sobre búsqueda binaria. Con estas FAQs ya conoces cómo funciona.