Los algoritmos de clasificación y búsqueda son exactamente e intuitivamente lo que dicen que son. Hay un montón de algoritmos de clasificación diferentes: clasificación por inserción, clasificación por fusión, clasificación por burbujas, etc. Esencialmente clasifican una serie de elementos potencialmente desordenados (por ejemplo, como en una lista) en alguna noción de orden (por ejemplo, alfabético, numérico o alguna definición arbitraria de otro tipo de pedido). Por ejemplo, como ejemplo en un pseudocódigo aproximado de estilo ocaml:
clasificador rec (x: lista de enteros): lista de enteros =
si x = [], entonces []
de lo contrario si x = element1 :: element2 :: rest_of_list,
entonces si element1 <= element2, element1 :: sorter (element2 :: rest_of_list)
else element2 :: sorter (element1 :: rest_of_list)
Lo anterior es en realidad una iteración de clasificación de burbujas (donde el número más grande en una iteración dada ‘burbujea’ hasta el final). Como puede ver, esto no es * eficiente *, ya que necesitaría hacer varios pases para asegurarse de que la lista esté completamente ordenada. Se pueden lograr algoritmos de clasificación más eficientes con, por ejemplo, montones binarios.
- ¿Qué son las estructuras autorreferenciales?
- Cómo escribir una función recursiva usando Python que toma una cadena como entrada e imprime cada carácter en una línea separada
- Cómo implementar un hashing sensible a la localidad
- ¿Cómo se implementa Quora? ¿Qué estructuras de datos y algoritmos se usan internamente?
- Cómo mejorar un algoritmo para pseudo triangular un polígono
En cuanto a la búsqueda, probablemente hayas oído hablar de la búsqueda binaria. Esto funciona si algo ya está ordenado. Como pseudocódigo de estilo pseudo-python aproximado con una función recursiva:
rec binary_search (x: lista entera) (n: elemento): bool
si x [middle_of_list] = n entonces verdadero
más si x [middle_of_list] <n entonces binary_search (firsthalfof_x) (n)
else binary_search (secondhalfof_x) (n)
También hay otros algoritmos de búsqueda. Casi cualquier buen algoritmo se basa en la idea de ‘divide y vencerás’. También puede buscar ingenuamente a través de cada elemento de una matriz o lista u otra estructura de datos y verificar si el elemento es el elemento de interés, [math] n [/ math].
